On The Connectivity Of Bipartite Graphs And The Number Of Edges In Graphs With Given Conditional Diameters

In 1956,Nordhaus and Gaddum gave lower and upper bounds on the sum and the product of the chromatic number of a graph and its complement,in terms of the order of the graph.Since then,The upper and lower bounds of the sum and/or the product of an invariant in a graph G and the same invariant in the complement Gc of G is called a Nordhaus-Gaddum type inequality or relation.For a bipartite graph G=G[X,Y]with vertex set V(G),edge set E(G)and bipartition(X,Y),its bipartite complementary graph Gbc is a bipartite graph with V(Gbc)=V(G)and E(Gbc)={xy:x?X,y?Y and xy(?)E(G)}.In this paper,we obtain the Nordhaus-Gaddum type inequalities for connectivity of bipartite graphs and its bipartite complementary graphs.Furthermore,we prove that these inequalities are best possible.The diameter D(G)of a graph G is the the maximum distance between two vertices in G.For given positive integers l and s,the conditional diameter D(G;l,s)of a graph G is the maximum distance between two subsets of vertices with cardinalities l and s.When l=s=1,the conditional diameter D(G;1,1)is just the diameter D(G)of G.In this paper,we obtain an asymptotically tight upper bound on the size of G in terms of order,minimum degree and conditional diameter,which extends the results in[Mukwembi S,On size,order,diameter and minimum degree,Indian J.Pure Appl.Math,2013,44(4):467-472.].