The Connectivity of a Bipartite Graph and Its Bipartite Complementary Graph
The Connectivity of a Bipartite Graph and Its Bipartite Complementary Graph
复制标题
二分图及其二分补图的连通性
DOI：
10.1142/s0129626420400058
复制
发表时间：
2019-09
影响因子：
0.4
通讯作者：
Liyun Wu
中科院分区：
文献类型：
--
作者：
Yingzhi Tian;Huaping Ma;Liyun Wu
1956年，Nordhaus和Gaddum根据图的阶，给出了图的色数与补的和与积的下界和上界。此后，图[公式：见文]中的一个不变量与[公式：见文]的补[公式：见文]中的同一个不变量的和和/或积的任何界称为诺德豪斯-加德姆型不等式或关系。关于连通性的Nordhaus-Gaddum型不等式已经被一些作者研究过。对于具有双分（[公式：见文]）的二部图[公式：见文]，其二部互补图[公式：见文]是具有[公式：见文]、[公式：见文]和[公式：见文]的二部图。本文得到了二部图及其二部补图的连通性的Nordhaus-Gaddum型不等式。进一步，我们证明了这些不等式是最佳可能的。
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 [Formula: see text] and the same invariant in the complement [Formula: see text] of [Formula: see text] 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 [Formula: see text] with bipartition ([Formula: see text]), its bipartite complementary graph [Formula: see text] is a bipartite graph with [Formula: see text] and [Formula: see text] and [Formula: see text]. 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.
登录
查看更多内容
影响因子：
1.1
作者：
Aouchiche, Mustapha;Hansen, Pierre
通讯作者：
Hansen, Pierre
DOI：
10.1016/j.dam.2008.05.012
发表时间：
2008-10
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Angelika Hellwig;L. Volkmann
通讯作者：
Angelika Hellwig;L. Volkmann
DOI：
10.1007/978-3-540-72588-6_55
发表时间：
2007-05
期刊：
--
影响因子：
--
作者：
Xiaodong Liang;J. Meng
通讯作者：
Xiaodong Liang;J. Meng
影响因子：
1.4
作者：
W. Mader
通讯作者：
W. Mader
DOI：
10.1007/bfb0059416
发表时间：
1971
期刊：
--
影响因子：
--
作者：
Y. Alavi;J. Mitchem
通讯作者：
Y. Alavi;J. Mitchem