Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs

Endre Boros, Vladimir Gurvich, Martin Milanič

Research output: Contribution to journalArticle

Abstract

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 (Formula presented.) -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 (Formula presented.) -Sperner hypergraphs. These results give new characterizations of threshold and domishold graphs. Second, we apply a characterization of (Formula presented.) -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.

Original languageEnglish (US)
Pages (from-to)364-397
Number of pages34
JournalJournal of Graph Theory
Volume94
Issue number3
DOIs
StatePublished - Jul 1 2020

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • 1-Sperner hypergraph
  • and closed neighborhood hypergraphs
  • and cobipartite graphs
  • bipartite
  • bounded clique-width
  • clique
  • dominating set
  • split
  • threshold graphs
  • vertex cover

Fingerprint Dive into the research topics of 'Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs'. Together they form a unique fingerprint.

  • Cite this