























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 $G^c$ 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 $G^{bc}$ is a bipartite graph with $V(G^{bc})=V(G)$ and $E(G^{bc})=\{xy:\ x\in X,\ y\in Y$ and $xy \notin 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。