Split graphs and Nordhaus-Gaddum graphs

DOI10.1016/J.DISC.2016.04.001MaRDI QIDQ297938zbMATH OpenOpenAlexFDO

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

Publication date 20 June 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(6)

• scientific article; zbMATH DE number 2204095 (Why is no real title available?)
• Extremal decompositions for Nordhaus-Gaddum theorems
• Split graphs and block representations
• scientific article; zbMATH DE number 1696523 (Why is no real title available?)
• Split graphs: combinatorial species and asymptotics
• Finding balance: split graphs and related classes

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)