Nonempty intersection of longest paths in a graph with a small matching number

Czechoslovak Mathematical Journal

Fuyuan Chen¹ 

[1] Center for Discrete Mathematics, Fuzhou University, Number 89-1, Ruanjiantongpandadao, Fuzhou, Gulou District, Fujian 350108, China, and Institute of Statistics an Applied Mathmatics, Anhui University of Finance and Economics, Number 962, Caoshanroad, Bengbu, Longzihu District, Anhui 233030, China

关键词: longest path;    matching number;   

DOI  :  

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

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'(G)$, 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 every connected graph $G$ with $\alpha'(G)\leq3$.

【 授权许可】

Unknown