Advanced Search

A maximum matching of a graph $G$ is a matching of $G$ with the largest number of edges. The matching number of a graph $G$, denoted by ${\alpha }^{\text{'}}\left(G\right)$, is the number of edges in a maximum matching of $G$. In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Although this conjecture has been disproved, finding some nice classes of graphs that support this conjecture is still very meaningful and interesting. In this short note, we prove that Gallai’s conjecture is true for...

In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Zamfirescu conjectured that the smallest counterexample to Gallai’s conjecture is a graph on 12 vertices. We prove that Gallai’s conjecture is true for every connected graph $G$ with ${\alpha }^{\text{'}}\left(G\right)\le 5$, which implies that Zamfirescu’s conjecture is true.