Geodesic
Nonempty intersection of longest paths in a graph with a small matching number
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 2, pp. 545-553

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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)\leq 3$.
DOI : 10.1007/s10587-015-0193-2
Classification : 05C38, 05C70, 05C75
Keywords: longest path; matching number 
@article{10_1007_s10587_015_0193_2,
     author = {Chen, Fuyuan},
     title = {Nonempty intersection of longest paths in a graph with a small matching number},
     journal = {Czechoslovak Mathematical Journal},
     pages = {545--553},
     publisher = {mathdoc},
     volume = {65},
     number = {2},
     year = {2015},
     doi = {10.1007/s10587-015-0193-2},
     mrnumber = {3360444},
     zbl = {06486964},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0193-2/}
}
TY  - JOUR
AU  - Chen, Fuyuan
TI  - Nonempty intersection of longest paths in a graph with a small matching number
JO  - Czechoslovak Mathematical Journal
PY  - 2015
SP  - 545
EP  - 553
VL  - 65
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0193-2/
DO  - 10.1007/s10587-015-0193-2
LA  - en
ID  - 10_1007_s10587_015_0193_2
ER  - 
%0 Journal Article
%A Chen, Fuyuan
%T Nonempty intersection of longest paths in a graph with a small matching number
%J Czechoslovak Mathematical Journal
%D 2015
%P 545-553
%V 65
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0193-2/
%R 10.1007/s10587-015-0193-2
%G en
%F 10_1007_s10587_015_0193_2
Chen, Fuyuan. Nonempty intersection of longest paths in a graph with a small matching number. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 2, pp. 545-553. doi: 10.1007/s10587-015-0193-2

Cité par Sources :