Premium
Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1‐Sperner hypergraphs
Author(s) -
Boros Endre,
Gurvich Vladimir,
Milanič Martin
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22529
Subject(s) - combinatorics , mathematics , hypergraph , bipartite graph , clique , discrete mathematics , vertex (graph theory) , class (philosophy) , graph , computer science , artificial intelligence
A hypergraph is said to be 1‐ Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of 1 ‐Sperner hypergraphs to graphs. First, we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For each of them, we characterize graphs yielding 1 ‐Sperner hypergraphs. These results give new characterizations of threshold and domishold graphs. Second, we apply a characterization of 1 ‐Sperner hypergraphs to derive decomposition theorems for two classes of split graphs, a class of bipartite graphs, and a class of cobipartite graphs. These decomposition theorems, based on certain matrix partitions, lead to new classes of graphs of bounded clique‐width and new polynomially solvable cases of three basic domination problems: domination, total domination, and connected domination.