Split graphs: combinatorial species and asymptotics (Q2001974): Difference between revisions

Summary: A split graph is a graph whose vertices can be partitioned into a clique and a stable set. We investigate the combinatorial species of split graphs, providing species-theoretic generalizations of enumerative results due to \textit{V. Bína} and \textit{J. Přibil} [Commentat. Math. Univ. Carol. 56, No. 2, 133--137 (2015; Zbl 1349.05171)], \textit{C. Cheng} et al. [Discrete Math. 339, No. 9, 2345--2356 (2016; Zbl 1338.05046)], and \textit{K. L. Collins} and \textit{A. N. Trenk} [Electron. J. Comb. 25, No. 1, Research Paper P1.73, 14 p. (2018; Zbl 1390.05189)]. In both the labeled and unlabeled cases, we give asymptotic results on the number of split graphs, of unbalanced split graphs, and of bicolored graphs, including proving the conjecture of C. Cheng et al. [loc. cit.] that almost all split graphs are balanced.