Upper Bounds on the Diameter of Bipartite and Triangle-Free Graphs with Prescribed Edge Connectivity

Abstract

Graph theory is used to study the mathematical structures of pairwise relations among objects. Mathematically, a pair G=(V,E) is a crisp graph, where V is a nonempty set and E is a relation on V[1]. -e order of a graph G is the number of vertices of G and is denoted by|V|=n. -e size of G,denoted by|E|=m, is the number of edges of G. -e distance,d G(u,v), between two vertices u,v of G is the length of a shortest u-v path in G. -e eccentricity, ec G(v), of a vertex v∈V is the maximum distance between v and any other vertex in G. -e maximum distance among all pairs of vertices [2], also known as the value of the maximum ec-centricity of the vertices of G, is called the diameter of G denoted by diam(G). -e degree, deg(v), of a vertex v of G is the number of edges incident with v. -e minimum degree,δ(G)=δ, of G is the minimum of the degrees of vertices in G. -e open neighborhood,N(v), of a vertex v is simply the set containing all the vertices adjacent to v. -e closed neighborhood, N[v], of a vertex v is simply the set containing the vertex v itself and all the vertices adjacent to v.We denote by E(V1,V2)the set {e=xy|x∈V1,y∈V2}of edges with one end inV1and the other end inV2.-e edge connectivity, λ(G)=λ, of G is the minimum number of edges whose deletion from G results in a disconnected or trivial graph. A complete graph,Kn, is a graph in which every vertex is adjacent to every other vertex. -e most likely antonym for a complete graph is a null graph,Nn, which is a graph containing only vertices and no edges. A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge in G connects a vertex in U to a vertex in V; furthermore, no two vertices in the same set are adjacent to each other. A graph is triangle-free if it does not contain C3 as a subgraphandC4-free if it does not containC4as a subgraph. It is important to observe from the above definitions that every bipartite graph is triangle free, but there are some triangle-free graphs which are not bipartite, for example, a cycle graph with five vertices(C5). For notions not defined here,we refer the reader to [3].