Split graphs: combinatorial species and asymptotics

MaRDI QIDQ2001974zbMATH OpenFDO

Authors Justin M. Troyka

Publication date 11 July 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.07248, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p42

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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 B'ina and Pv{r}ibil (2015), Cheng, Collins, and Trenk (2016), and Collins and Trenk (2018). 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 Cheng, Collins, and Trenk (2016) that almost all split graphs are balanced.

Review text

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.

Recommendations

• Finding balance: split graphs and related classes
• Note on enumeration of labeled split graphs.
• On colorings of split graphs
• Split graphs
• Split graphs and Nordhaus-Gaddum graphs

Cites work

• Enumeration of bipartite graphs and bipartite blocks
• Finding balance: split graphs and related classes
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3910422 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 1522332 (Why is no real title available?)
• Note on enumeration of labeled split graphs.
• Split graphs and Nordhaus-Gaddum graphs
• The K -Connectedness of Bipartite Graphs
• The enumeration of bipartite graphs
• The splittance of a graph
• Une théorie combinatoire des séries formelles

Cited in

(16)

• Finding balance: split graphs and related classes
• Split graphs
• Advances in Aharoni-Hartman-Hoffman's conjecture for split digraphs
• Split graphs and Nordhaus-Gaddum graphs
• Almost all asters are splittable
• Countable splitting graphs
• Split Hypergraphs
• scientific article; zbMATH DE number 1522332 (Why is no real title available?)
• Underlying split multigraphs
• Bisplit graphs satisfy the Chen-Chvátal conjecture
• Note on enumeration of labeled split graphs.
• Counting and enumerating unlabeled split-indifference graphs
• Spanning trees of almost ideal proper split graphs
• The regularity of almost all edge ideals
• Split graphs and block representations
• The splitting number of complete bipartite graphs

This page was built for publication: Split graphs: combinatorial species and asymptotics

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