2017/06/09 by Collins, Karen L., Trenk, Ann N. · 1 citation
#05C17 #05C30 #06A07 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1706.03092
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.