The Connectivity of a Bipartite Graph and Its Bipartite Complementary Graph
Abstract
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, any bound on the sum and/or the product of an invariant in a graph and the same invariant in the complement of is called a Nordhaus-Gaddum type inequality or relation. The Nordhaus-Gaddum type inequalities for connectivity have been studied by several authors. For a bipartite graph with bipartition (), its bipartite complementary graph is a bipartite graph with and and . 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.
References
- 1. , On the Nordhaus-Gaddum class problems, Australas. J. Combin. 2 (1990) 5–27. Google Scholar
- 2. ,
Connectivity and line connetivity of complementary graphs , in Recent Trends in Graph Theory, eds. M. CapobiancoJ. B. FrenchenM. Krolik (1970), pp. 1–3. Google Scholar - 3. , A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013) 466–546. Crossref, ISI, Google Scholar
- 4. , Graph Theory,
Graduate Texts in Mathematics , Vol. 244 (Springer, Berlin, 2008). Crossref, Google Scholar - 5. , The connectivity of a graph and its complement, Discrete Applied Mathematics 156 (2008) 3325–3328. Crossref, ISI, Google Scholar
- 6. X. D. Liang and J. X. Meng, Connectivity of connected bipartite graphs with two orbitis, LNCS4489 (Springer, Heidelberg, Germany, 2007), pp. 334–337. Google Scholar
- 7. , Minimale n-fach kantenzusammenhängenden Graphen, Math. Ann. 191 (1971) 21–28. Crossref, Google Scholar
- 8. , On complementary graphs, Amer. Math. Monthly 63 (1956) 175–177. Crossref, Google Scholar
- 9. , Introduction of Finite Groups, Vol. II (Science Press, Beijing, 1999), pp. 384–386. Google Scholar


