Split graphs and Nordhaus-Gaddum graphs

DOI10.1016/J.DISC.2016.04.001zbMATH Open1338.05046arXiv1506.03746OpenAlexW2963206482MaRDI QIDQ297938FDOQ297938

Authors: Christine T. Cheng, Karen L. Collins, Ann Trenk 

Publication date: 20 June 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A graph G is an NG-graph if chi(G) + chi(G complement) = |V(G)| + 1. We characterize NG-graphs solely from degree sequences leading to a linear-time recognition algorithm. We also explore the connections between NG-graphs and split graphs. There are three types of NG-graphs and split graphs can also be divided naturally into two categories, balanced and unbalanced. We characterize each of these five classes by degree sequence. We construct bijections between classes of NG-graphs and balanced and unbalanced split graphs which, together with the known formula for the number of split graphs on n vertices, allows us to compute the sizes of each of these classes. Finally, we provide a bijection between unbalanced split graphs on n vertices and split graphs on n-1 or fewer vertices providing evidence for our conjecture that the rapid growth in the number of split graphs comes from the balanced split graphs.

Full work available at URL: https://arxiv.org/abs/1506.03746

Recommendations

• Nordhaus-Gaddum theorem for the distinguishing chromatic number
• Finding balance: split graphs and related classes
• Split graphs: combinatorial species and asymptotics
• Linear recognition of pseudo-split graphs
• Split graphs

zbMATH Keywords

split graphsdegree sequence characterizationNG-graphsNordhaus-Gaddum theorempseudo-split graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Linear recognition of pseudo-split graphs
• Decomposition of graphical sequences and unigraphs
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• On fractional realizations of graph degree sequences
• The splittance of a graph
• Complementary graphs and the chromatic number
• On Complementary Graphs
• Hereditary unigraphs and Erdős-Gallai equalities
• Nordhaus-Gaddum theorem for the distinguishing chromatic number
• Title not available (Why is that?)
• Covering a set by subsets

Cited In (6)

• Split graphs: combinatorial species and asymptotics
• Finding balance: split graphs and related classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Split graphs and block representations
• Extremal decompositions for Nordhaus-Gaddum theorems

This page was built for publication: Split graphs and Nordhaus-Gaddum graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q297938)