In 1966, Gallai 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.
@article{10_37236_7487,
author = {Gili Golan and Songling Shan},
title = {Nonempty intersection of longest paths in {\(2K_2\)-free} graphs},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {2},
doi = {10.37236/7487},
zbl = {1388.05099},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7487/}
}
TY - JOUR
AU - Gili Golan
AU - Songling Shan
TI - Nonempty intersection of longest paths in \(2K_2\)-free graphs
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/7487/
DO - 10.37236/7487
ID - 10_37236_7487
ER -
%0 Journal Article
%A Gili Golan
%A Songling Shan
%T Nonempty intersection of longest paths in \(2K_2\)-free graphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7487/
%R 10.37236/7487
%F 10_37236_7487
Gili Golan; Songling Shan. Nonempty intersection of longest paths in \(2K_2\)-free graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7487
