Chen and Chvátal's conjecture in tournaments

DOI10.1016/J.EJC.2021.103374MaRDI QIDQ2048355zbMATH OpenOpenAlexWikidataFDO

Authors G. Araujo-Pardo, Martin Matamala

Publication date 5 August 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

strongly connected graphfinite quasi-metric spacesChen and Chvátal's conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Distance in graphs (05C12)

Abstract: In this work we present a version of the so called Chen and Chv'atal's conjecture for directed graphs. A line of a directed graph D is defined by an ordered pair (u, v), with u and v two distinct vertices of D, as the set of all vertices w such that u, v, w belong to a shortest directed path in D containing a shortest directed path from u to v. A line is empty if there is no directed path from u to v. Another option is that a line is the set of all vertices. The version of the Chen and Chv'atal's conjecture we study states that if none of previous options hold, then the number of distinct lines in D is at least its number of vertices. Our main result is that any tournament satisfies this conjecture as well as any orientation of a complete bipartite graph of diameter three.

Recommendations

• A new class of graphs that satisfies the Chen-Chvátal conjecture
• Solution of a conjecture of Volkmann on longest paths through an arc in strongly connected in-tournaments
• Hoàng-Reed conjecture holds for tournaments
• Lichiardopol's conjecture on disjoint cycles in tournaments
• scientific article; zbMATH DE number 4183436

Cites work

• A De Bruijn-Erdős theorem for \(1\)-\(2\) metric spaces.
• A de Bruijn-Erdős theorem and metric spaces
• A de Bruijn-Erdős theorem for chordal graphs
• A de Bruijn-Erdős theorem in graphs?
• A new class of graphs that satisfies the Chen-Chvátal conjecture
• Lines in bipartite graphs and in 2‐metric spaces
• Lines, betweenness and metric spaces
• Problems related to a de Bruijn-Erdös theorem
• The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs

Cited in

(4)

• On Convex Subsets in Tournaments
• Chen-Chvátal’s conjecture for graphs with restricted girth
• scientific article; zbMATH DE number 7731176 (Why is no real title available?)
• Erdös–Hajnal conjecture for new infinite families of tournaments

This page was built for publication: Chen and Chvátal's conjecture in tournaments

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