Gallai theorems for graphs, hypergraphs, and set systems
\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.
- A matroid generalization of theorems of Lewin and Gallai
- Eulerian Walks in Graphs
- scientific article; zbMATH DE number 3154393 (Why is no real title available?)
- scientific article; zbMATH DE number 3873384 (Why is no real title available?)
- scientific article; zbMATH DE number 4137820 (Why is no real title available?)
- scientific article; zbMATH DE number 3929834 (Why is no real title available?)
- scientific article; zbMATH DE number 3970793 (Why is no real title available?)
- scientific article; zbMATH DE number 4087718 (Why is no real title available?)
- scientific article; zbMATH DE number 3720947 (Why is no real title available?)
- scientific article; zbMATH DE number 3895100 (Why is no real title available?)
- scientific article; zbMATH DE number 3400927 (Why is no real title available?)
- Total domination in graphs
- Two Bounds for the Domination Number of a Graph
- Critical hypergraphs and interesting set-pair systems
- t-expansive and t-wise intersecting hypergraphs
- On generalised minimal domination parameters for paths
- Extensions of Gallai's graph covering theorems for uniform hypergraphs
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- Gallai-type theorems and domination parameters
- Using maximality and minimality conditions to construct inequality chains
- Gallai's question and constructions of almost hypotraceable graphs
- Well irredundant graphs
- scientific article; zbMATH DE number 3871413 (Why is no real title available?)
- On vertex independence number of uniform hypergraphs
- scientific article; zbMATH DE number 1990679 (Why is no real title available?)
- Graphs with constant sum of domination and inverse domination numbers
- scientific article; zbMATH DE number 890667 (Why is no real title available?)
- scientific article; zbMATH DE number 894703 (Why is no real title available?)
- Some new results on Gallai theorem and perfect matching for \(k\)-uniform hypergraphs
- Matchability and \(k\)-maximal matchings
- Domination and edge-vertex domination in trees
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Variations on the Roy-Gallai theorem
- Independence-domination duality
This page was built for publication: Gallai theorems for graphs, hypergraphs, and set systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804601)
