World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

The Connectivity of a Bipartite Graph and Its Bipartite Complementary Graph

    This article is part of the issue:

    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 G and the same invariant in the complement Gc of G 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 G=G[X,Y] with bipartition (X,Y), its bipartite complementary graph Gbc is a bipartite graph with V(Gbc)=V(G) and E(Gbc)={xy: xX, yY and xyE(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.

    References

    • 1. N. Achuthan, N. R. Achuthan and L. Caccetta, On the Nordhaus-Gaddum class problems, Australas. J. Combin. 2 (1990) 5–27. Google Scholar
    • 2. Y. Alavi and J. Mitchem, 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. M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013) 466–546. Crossref, ISIGoogle Scholar
    • 4. J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, Vol. 244 (Springer, Berlin, 2008). CrossrefGoogle Scholar
    • 5. A. Hellwig and L. Volkmann, The connectivity of a graph and its complement, Discrete Applied Mathematics 156 (2008) 3325–3328. Crossref, ISIGoogle 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. W. Mader, Minimale n-fach kantenzusammenhängenden Graphen, Math. Ann. 191 (1971) 21–28. CrossrefGoogle Scholar
    • 8. E. A. Nordhaus and J. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175–177. CrossrefGoogle Scholar
    • 9. M. Y. Xu, Introduction of Finite Groups, Vol. II (Science Press, Beijing, 1999), pp. 384–386. Google Scholar