Finding balance: split graphs and related classes (Q1753048)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6873117
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Finding balance: split graphs and related classes |
scientific article; zbMATH DE number 6873117 |
Statements
Finding balance: split graphs and related classes (English)
0 references
25 May 2018
0 references
Summary: 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. \textit{C. Cheng} et al. [Discrete Math. 339, No. 9, 2345--2356 (2016; Zbl 1338.05046)], 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.
0 references
split graph
0 references
set cover
0 references
bipartite graph
0 references
bipartite poset
0 references
bijection
0 references
0.8568835258483887
0 references
0.7763822674751282
0 references
0.7562841176986694
0 references
