A graph is a split graph if its vertex set can be partitioned into a clique and a stable set. A split graph is unbalanced if there exist two such partitions that are distinct. Cheng, Collins and Trenk (2016), discovered the following interesting counting fact: unlabeled, unbalanced split graphs on $n$ vertices can be placed into a bijection with all unlabeled split graphs on $n-1$ or fewer vertices. In this paper we translate these concepts and the theorem to different combinatorial settings: minimal set covers, bipartite graphs with a distinguished block and posets of height one.
@article{10_37236_7091,
author = {Karen L. Collins and Ann N. Trenk},
title = {Finding balance: split graphs and related classes},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {1},
doi = {10.37236/7091},
zbl = {1390.05189},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7091/}
}
TY - JOUR
AU - Karen L. Collins
AU - Ann N. Trenk
TI - Finding balance: split graphs and related classes
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/7091/
DO - 10.37236/7091
ID - 10_37236_7091
ER -
%0 Journal Article
%A Karen L. Collins
%A Ann N. Trenk
%T Finding balance: split graphs and related classes
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7091/
%R 10.37236/7091
%F 10_37236_7091
Karen L. Collins; Ann N. Trenk. Finding balance: split graphs and related classes. The electronic journal of combinatorics, Tome 25 (2018) no. 1. doi: 10.37236/7091
