Split graphs and Nordhaus-Gaddum graphs

详细信息    查看全文

• 作者：Christine Cheng^a ; ^{ccheng@uwm.edu" class="auth_mail" title="E-mail the corresponding author} ; Karen L. Collins^b ; ^{kcollins@wesleyan.edu" class="auth_mail" title="E-mail the corresponding author} ; Ann N. Trenk^c ; ^{atrenk@wellesley.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Nordhaus&ndash ; Gaddum theorem ; NG-graphs ; Split graphs ; Pseudo-split graphs ; Degree sequence characterization
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 September 2016
• 年：2016
• 卷：339
• 期：9
• 页码：2345-2356
• 全文大小：447 K

文摘

A graph G$G$ is an NG-graph if $\chi \left(G\right)+\chi \left(\overline{G}\right)=\left|V\left(G\right)\right|+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$n$ vertices, allows us to compute the sizes of each of these classes. Finally, we provide a bijection between unbalanced split graphs on n$n$ vertices and split graphs on n−1$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.