| Title:
|
Note on enumeration of labeled split graphs (English) |
| Author:
|
Bína, Vladislav |
| Author:
|
Přibil, Jiří |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
56 |
| Issue:
|
2 |
| Year:
|
2015 |
| Pages:
|
133-137 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
graph enumeration |
| Keyword:
|
labeled graph |
| Keyword:
|
split graph |
| MSC:
|
05A15 |
| MSC:
|
05C30 |
| idZBL:
|
Zbl 06433812 |
| idMR:
|
MR3338727 |
| DOI:
|
10.14712/1213-7243.2015.112 |
| . |
| Date available:
|
2015-04-25T16:55:46Z |
| Last updated:
|
2017-08-07 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144234 |
| . |
| Reference:
|
[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. Zbl 0571.05026, MR 0770128, 10.1017/S1446788700023077 |
| Reference:
|
[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. |
| Reference:
|
[3] Bína V.: Sequence A179534 in The On-Line Encyclopedia of Integer Sequences.http://oeis.org/A179534 (2010). |
| Reference:
|
[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. |
| Reference:
|
[5] Edwards D., Havránek T.: A fast procedure for model search in multidimensional contingency tables.Biometrika 72 (1985), 339–351. Zbl 0576.62067, MR 0801773, 10.1093/biomet/72.2.339 |
| Reference:
|
[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. Zbl 1253.05145, MR 2971709, 10.1016/j.jcta.2012.08.003 |
| Reference:
|
[7] Hammer P.L., Simeone B.: The splittance of a graph.Combinatorica 1 (1981), no. 3, 275–284. Zbl 0492.05043, MR 0637832, 10.1007/BF02579333 |
| Reference:
|
[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. Zbl 0953.05033, MR 1778996 |
| Reference:
|
[9] Sloane N.J.A.: Sequence A047864 in The On-Line Encyclopedia of Integer Sequences.http://oeis.org/A047864 (1999). |
| Reference:
|
[10] Wilf H.S.: Generatingfunctionology.Academic Press, San Diego, 1990, p. 80, Equation 3.11.5. Zbl 1092.05001, MR 1034250 |
| . |
