Gallai theorems for graphs, hypergraphs, and set systems
type: Item
instance of: scholarly article
title: Gallai theorems for graphs, hypergraphs, and set systems
zbMATH Open document ID: 0728.05050
DOI: 10.1016/0012-365X(88)90192-6
author: E. J. Cockayne
author: Stephen T. Hedetniemi
author: Renu C. Laskar
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: \textit{T. Gallai} presented in [Ann. Univ. Sci. Budapest, Rolando Eötvös, Sect. Math. 2, 133-138 (1959; Zbl 0094.361)] his now classical theorem, involving the vertex covering number \(\alpha_ 0\), the vertex independence number \(\beta_ 0\), the edge covering number \(\alpha_ 1\), and the maximum matching (or edge independence) number \(\beta_ 1:\) Theorem. For any nontrivial, connected graph \(G=(V,E)\) with p vertices, \(\alpha_ 0+\beta_ 0=\alpha_ 1+\beta_ 1=p.\) Since then quite a large number of similar results and generalizations of this theorem have been obtained, which we will call `Gallai Theorems'. A typical Gallai theorem has the form: \(\alpha +\beta =p\), where \(\alpha\) and \(\beta\) are numerical maximum or minimum functions of some type defined on the class of connected graphs and p denotes the number of vertices in a graph. This paper is an attempt to collect and unify results of this type. In particular, we present two general theorems which encompass nearly all of the existing Gallai theorems. The first theorem is based on hereditary properties of set systems, while the second is based on partition of vertices into subgraphs having treelike properties. We also present a variety of new Gallai theorems (one of which is not a corollary of either of the two above mentioned generalizations), as well as a number of other new results.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05D15
Mathematics Subject Classification ID: 05A18
zbMATH DE Number: 4202307
zbMATH Keywords: vertex covering number
zbMATH Keywords: vertex independence number
zbMATH Keywords: edge covering number
zbMATH Keywords: Gallai Theorems
zbMATH Keywords: hereditary properties
zbMATH Keywords: partition of vertices
zbMATH Keywords: subgraphs
MaRDI profile type: Publication
cites work: Total domination in graphs
cites work: Q3270978
cites work: Q5187313
cites work: Q5668824
cites work: Eulerian Walks in Graphs
cites work: Q3340900
cites work: Q3816118
cites work: Q3470505
cites work: A matroid generalization of theorems of Lewin and Gallai
cites work: Q3702884
cites work: Q3910551
cites work: Two Bounds for the Domination Number of a Graph
cites work: Q3737461
full work available at URL: 0012-365x(88)90192-6
OpenAlex ID: W2010891937
description: scientific article; zbMATH DE number 4202307