Name
Abstract | ||
|---|---|---|
In 1966, Gallai asked whether all longest paths in a connected graph have a nonempty intersection. The answer to this question is not true in general and various counterexamples have been found. However, there is a positive solution to Gallai's question for many well-known classes of graphs such as split graphs, series-parallel graphs, and 2K(2)-free graphs. Split graphs, series-parallel graphs and 2K(2)-free graphs were all proven to be Hamiltonian under given toughness conditions. This observation motivates us to investigate Gallai's question in graphs that are close to have certain Hamiltonicity properties. Let {R, S} be a pair of connected graphs. In particular, in this paper, we show that Gallai's question has an affirmative answer for all connected {R, S}-free graphs such that every 2-connected {R, S}-free graph is Hamiltonian. These pairs {R, S} were completely characterized in the 1990s. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.dam.2021.07.029 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Longest path, Forbidden pairs, Hamiltonian cycle | Journal | 304 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuping Gao | 1 | 0 | 1.35 |
| Songling Shan | 2 | 20 | 9.16 |