Chen and Chvátal's conjecture in tournaments

DOI10.1016/J.EJC.2021.103374zbMATH Open1469.05062arXiv1912.00814OpenAlexW3172748103WikidataQ113875499 ScholiaQ113875499MaRDI QIDQ2048355FDOQ2048355

Authors: G. Araujo-Pardo, Martin Matamala 

Publication date: 5 August 2021

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

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.

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

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

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)

Cites Work

• A de Bruijn-Erdős theorem for chordal graphs
• A De Bruijn-Erdős theorem for \(1\)-\(2\) metric spaces.
• Lines, betweenness and metric spaces
• The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs
• A de Bruijn-Erdős theorem and metric spaces
• Problems related to a de Bruijn-Erdös theorem
• 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

Cited In (4)

• On Convex Subsets in Tournaments
• Chen-Chvátal’s conjecture for graphs with restricted girth
• Title not available (Why is that?)
• 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)