Domination in 3-tournaments

DOI10.1016/J.JCTA.2016.09.004MaRDI QIDQ346441zbMATH OpenOpenAlexFDO

Authors Dániel Korándi, Benny Sudakov

Publication date 29 November 2016

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.01697

zbMATH Keywords

dominationgirthgeneralized tournamentsproperty \(S_k\)

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: A 3-tournament is a complete 3-uniform hypergraph where each edge has a special vertex designated as its tail. A vertex set $X$ dominates $T$ if every vertex not in $X$ is contained in an edge whose tail is in $X$. The domination number of $T$ is the minimum size of such an $X$. Generalizing well-known results about usual (graph) tournaments, Gy'arf'as conjectured that there are 3-tournaments with arbitrarily large domination number, and that this is not the case if any four vertices induce two triples with the same tail. In this short note we solve both problems, proving the first conjecture and refuting the second.

Recommendations

• scientific article; zbMATH DE number 1416469
• Domination in tournaments
• scientific article; zbMATH DE number 2059945
• Domination in transitive colorings of tournaments
• scientific article; zbMATH DE number 1833085

Cites work

• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• A note on approximate Nash equilibria
• Difference covers which have small k ‐sums for any k
• Large Supports are required for Well-Supported Nash Equilibria
• Pair dominating graphs

Cited in

(8)

• Domination in tournaments
• The domination number of round digraphs
• Directed domination in oriented hypergraphs
• scientific article; zbMATH DE number 7057476 (Why is no real title available?)
• scientific article; zbMATH DE number 1416469 (Why is no real title available?)
• 3-uniform hypergraphs: modular decomposition and realization by tournaments
• A recurrence for bounds on dominating sets in \(k\)-majority tournaments
• Domination number of certain infinite tournaments

This page was built for publication: Domination in 3-tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q346441)