Note on enumeration of labeled split graphs

Vladislav Bína; Jiří Přibil

Commentationes Mathematicae Universitatis Carolinae (2015)

  • Volume: 56, Issue: 2, page 133-137
  • ISSN: 0010-2628

Abstract

top
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.

How to cite

top

Bína, Vladislav, and Přibil, Jiří. "Note on enumeration of labeled split graphs." Commentationes Mathematicae Universitatis Carolinae 56.2 (2015): 133-137. <http://eudml.org/doc/270137>.

@article{Bína2015,
abstract = {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.},
author = {Bína, Vladislav, Přibil, Jiří},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {graph enumeration; labeled graph; split graph; graph enumeration; labeled graph; split graph},
language = {eng},
number = {2},
pages = {133-137},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Note on enumeration of labeled split graphs},
url = {http://eudml.org/doc/270137},
volume = {56},
year = {2015},
}

TY - JOUR
AU - Bína, Vladislav
AU - Přibil, Jiří
TI - Note on enumeration of labeled split graphs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2015
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 56
IS - 2
SP - 133
EP - 137
AB - 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.
LA - eng
KW - graph enumeration; labeled graph; split graph; graph enumeration; labeled graph; split graph
UR - http://eudml.org/doc/270137
ER -

References

top
  1. Bender E.A., Richmond L.B., Wormald N.C., 10.1017/S1446788700023077, J. Austral. Math. Soc. Ser. A 38 (2) (1985), no. 2, 214–221. Zbl0571.05026MR0770128DOI10.1017/S1446788700023077
  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., 10.1093/biomet/72.2.339, Biometrika 72 (1985), 339–351. Zbl0576.62067MR0801773DOI10.1093/biomet/72.2.339
  6. Gebhardt V., 10.1016/j.jcta.2012.08.003, J. Combin. Theory Ser. A 120 (2013), no. 1, 232–244. Zbl1253.05145MR2971709DOI10.1016/j.jcta.2012.08.003
  7. Hammer P.L., Simeone B., 10.1007/BF02579333, Combinatorica 1 (1981), no. 3, 275–284. Zbl0492.05043MR0637832DOI10.1007/BF02579333
  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. Zbl0953.05033MR1778996
  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. Zbl1092.05001MR1034250

NotesEmbed ?

top

You must be logged in to post comments.