The connectivity of a bipartite graph and its bipartite complementary graph

2019/09/26 by Huaping Ma, Ma, Huaping, Yingzhi Tian +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1909.11982

arxiv created 2019/09/26 · arxiv updated 2019/09/27

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 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∈ 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.

Related

• Degrees and Connectivities of a Graph and Its δ-Complement
• The Sum and Product of Chromatic Numbers of Graphs and their Line Graphs
• Nordhaus-Gaddum inequalities for the number of cliques in a graph
• Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number
• Operations on Covering Numbers of Certain Graph Classes