Nonempty intersection of longest paths in \(2K_2\)-free graphs (Q1640209)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Nonempty intersection of longest paths in \(2K_2\)-free graphs |
scientific article |
Statements
Nonempty intersection of longest paths in \(2K_2\)-free graphs (English)
0 references
14 June 2018
0 references
Summary: \textit{T. Gallai} [``Problem 4'', in: P. Erdős and G. Katona (eds.), Theory of graphs. Proceedings of the Colloquium held at Tihany, Hungary, September 1966. New York: Academic Press (1966)] asked whether all longest paths in a connected graph share a common vertex. Counterexamples indicate that this is not true in general. However, Gallai's question is positive for certain well-known classes of connected graphs, such as split graphs, interval graphs, circular arc graphs, outerplanar graphs, and series-parallel graphs. A graph is \(2K_2\)-free if it does not contain two independent edges as an induced subgraph. In this short note, we show that, in nonempty \(2K_2\)-free graphs, every vertex of maximum degree is common to all longest paths. Our result implies that all longest paths in a nonempty \(2K_2\)-free graph have a nonempty intersection. In particular, it strengthens the result on split graphs, as split graphs are \(2K_2\)-free.
0 references
\(2K_2\)-free graphs
0 references
longest paths
0 references
dominating paths
0 references