Finding Balance: Split Graphs and Related Classes | Zendy

Karen L. Collins | Zendy; Ann N. Trenk | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Finding Balance: Split Graphs and Related Classes

Author(s) -

Karen L. Collins,

Ann N. Trenk

Publication year - 2018

Publication title -

the electronic journal of combinatorics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.703

H-Index - 52

eISSN - 1097-1440

pISSN - 1077-8926

DOI - 10.37236/7091

Subject(s) - combinatorics , mathematics , bijection , bipartite graph , vertex (graph theory) , split graph , cograph , discrete mathematics , graph , clique , chordal graph , 1 planar graph

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research