Gallai theorems for graphs, hypergraphs, and set systems

DOI10.1016/0012-365X(88)90192-6zbMath0728.05050OpenAlexW2010891937MaRDI QIDQ804601

E. J. Cockayne, Stephen T. Hedetniemi, Renu C. Laskar

Publication date: 1988

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(88)90192-6

zbMATH Keywords

hereditary propertiesvertex independence numbersubgraphsedge covering numberGallai Theoremspartition of verticesvertex covering number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Partitions of sets (05A18) Hypergraphs (05C65) Permutations, words, matrices (05A05) Enumeration in graph theory (05C30) Transversal (matching) theory (05D15)

Related Items (11)

Gallai-type theorems and domination parameters ⋮ Well irredundant graphs ⋮ Using maximality and minimality conditions to construct inequality chains ⋮ On vertex independence number of uniform hypergraphs ⋮ Matchability and \(k\)-maximal matchings ⋮ Some new results on Gallai theorem and perfect matching for \(k\)-uniform hypergraphs ⋮ Graphs with constant sum of domination and inverse domination numbers ⋮ 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 ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• A matroid generalization of theorems of Lewin and Gallai
• Total domination in graphs
• Two Bounds for the Domination Number of a Graph
• Eulerian Walks in Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Gallai theorems for graphs, hypergraphs, and set systems