Dominating sets in k-majority tournaments.

DOI10.1016/J.JCTA.2005.05.009MaRDI QIDQ2490838zbMATH OpenOpenAlexFDO

Authors Noga Alon, Graham Brightwell, H. A. Kierstead, Alexandr Kostochka, Peter Winkler

Publication date 18 May 2006

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

Full work available at URL https://doi.org/10.1016/j.jcta.2005.05.009

Mathematics Subject Classification ID

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

Review text

The \(k\)-majority tournament determined by \(2k-l\) linear orderings of a finite vertex set \(V\) is the directed graph \(T\) on \(V\) in which \(uv\) is an arc if and only if \(u\) precedes \(v\) in at least \(k\) of the orderings. Let \(F(k)\) denote the maximum of the size of a minimum dominating set of \(T\) over all \(k\)-majority tournaments \(T\) (with no restriction on the size of \(V)\). The authors' main results are that \(F(2)=3\), \(F(3)\geq 4\), and that \(F(k)=\Omega(k/\log k)\) for \(k\geq 3\).

Recommendations

• A recurrence for bounds on dominating sets in k-majority tournaments
• Dominant tournament families
• Acyclic sets in k-majority tournaments
• scientific article; zbMATH DE number 1416469
• A Problem on Tournaments

Cited in

(33)

• Domination and fractional domination in digraphs
• Domination in tournaments
• Dominant tournament families
• Hereditary classes of graphs: a parametric approach
• Orientable domination in product-like graphs
• Covering small subgraphs of (hyper)tournaments with spanning acyclic subgraphs
• A proof of the Erdös-Sands-Sauer-Woodrow conjecture
• \(k\)-majority digraphs and the hardness of voting with a constant number of voters
• VC-dimension and Erdős-Pósa property
• A Simple Construction for Tournaments with Every k Players Beaten by a Single Player
• Domination in digraphs
• Identifying codes in hereditary classes of graphs and VC-dimension
• Domination in transitive colorings of tournaments
• scientific article; zbMATH DE number 2077654 (Why is no real title available?)
• Maximally nontransitive dice
• The complexity of finding (approximate sized) distance-d dominating set in tournaments
• scientific article; zbMATH DE number 1416469 (Why is no real title available?)
• Realizing small tournaments through few permutations
• scientific article; zbMATH DE number 2192183 (Why is no real title available?)
• Acyclic sets in k-majority tournaments
• Graph functionality
• Ranking graphs through hitting times of Markov chains
• On the kernel and related problems in interval digraphs
• A recurrence for bounds on dominating sets in k-majority tournaments
• Approval gap of weighted k-majority tournaments
• Approximating multiobjective optimization problems: how exact can you be?
• First order logic and twin-width in tournaments and dense oriented graphs
• Zarankiewicz's problem via -t-nets
• Computing diameter+2 in truly-subquadratic time for unit-disk graphs
• Some results and problems on tournament structure
• Polychromatic coloring of tuples in hypergraphs
• Extreme score distributions in countable-outcome round-robin tournaments of equally strong players
• Efron's coins and the linial arrangement

This page was built for publication: Dominating sets in \(k\)-majority tournaments.

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