Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
graph enumeration; labeled graph; split graph
graph enumeration; labeled graph; split graph
Summary:
The paper brings explicit formula for enumeration of vertex-labeled split graphs with given number of vertices. The authors derive this formula combinatorially using an auxiliary assertion concerning number of split graphs with given clique number. In conclusion authors discuss enumeration of vertex-labeled bipartite graphs, i.e., a graphical class defined in a similar manner to the class of split graphs.
References:
[1] Bender E.A., Richmond L.B., Wormald N.C.: Almost all chordal graphs split. J. Austral. Math. Soc. Ser. A 38 (2) (1985), no. 2, 214–221. DOI 10.1017/S1446788700023077 | MR 0770128 | Zbl 0571.05026
[2] Bína V.: Enumeration of labeled split graphs and counts of important superclasses. in Proceedings of 10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW'11), Frascati (2011), pp. 72–75.
[3] Bína V.: Sequence A179534 in The On-Line Encyclopedia of Integer Sequences. http://oeis.org/A179534 (2010).
[4] Bína V.: Multidimensional probability distributions: Structure and learning. Ph.D. Thesis, Faculty of Management in Jindřichův Hradec, Univ. of Economics in Prague, 2011.
[5] Edwards D., Havránek T.: A fast procedure for model search in multidimensional contingency tables. Biometrika 72 (1985), 339–351. DOI 10.1093/biomet/72.2.339 | MR 0801773 | Zbl 0576.62067
[6] Gebhardt V.: Computing growth functions of braid monoids and counting vertex-labelled bipartite graphs. J. Combin. Theory Ser. A 120 (2013), no. 1, 232–244. DOI 10.1016/j.jcta.2012.08.003 | MR 2971709 | Zbl 1253.05145
[7] Hammer P.L., Simeone B.: The splittance of a graph. Combinatorica 1 (1981), no. 3, 275–284. DOI 10.1007/BF02579333 | MR 0637832 | Zbl 0492.05043
[8] Royle G.F.: Counting set covers and split graphs. J. Integer Seq. 3 (2000), https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html MR 1778996 | Zbl 0953.05033
[9] Sloane N.J.A.: Sequence A047864 in The On-Line Encyclopedia of Integer Sequences. http://oeis.org/A047864 (1999).
[10] Wilf H.S.: Generatingfunctionology. Academic Press, San Diego, 1990, p. 80, Equation 3.11.5. MR 1034250 | Zbl 1092.05001
Search
Partner of
