| Title:
|
Nonempty intersection of longest paths in a graph with a small matching number (English) |
| Author:
|
Chen, Fuyuan |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
65 |
| Issue:
|
2 |
| Year:
|
2015 |
| Pages:
|
545-553 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
longest path |
| Keyword:
|
matching number |
| MSC:
|
05C38 |
| MSC:
|
05C70 |
| MSC:
|
05C75 |
| idZBL:
|
Zbl 06486964 |
| idMR:
|
MR3360444 |
| DOI:
|
10.1007/s10587-015-0193-2 |
| . |
| Date available:
|
2015-06-16T18:05:53Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144287 |
| . |
| Reference:
|
[1] Balister, P. N., Győri, E., Lehel, J., Schelp, R. H.: Longest paths in circular arc graphs.Comb. Probab. Comput. 13 (2004), 311-317. Zbl 1051.05053, MR 2056401, 10.1017/S0963548304006145 |
| Reference:
|
[2] Bondy, J. A., Murty, U. S. R.: Graph Theory.Graduate Texts in Mathematics 244 Springer, Berlin (2008). Zbl 1134.05001, MR 2368647, 10.1007/978-1-84628-970-5_1 |
| Reference:
|
[3] Rezende, S. F. de, Fernandes, C. G., Martin, D. M., Wakabayashi, Y.: Intersecting longest paths.Discrete Math. 313 (2013), 1401-1408. Zbl 1279.05041, MR 3061125, 10.1016/j.disc.2013.02.016 |
| Reference:
|
[4] Ehrenmüller, J., Fernandes, C. G., Heise, C. G.: Nonempty intersection of longest paths in series-parallel graphs.Preprint 2013, arXiv:1310.1376v2. |
| Reference:
|
[5] Gallai, T.: Problem 4.Theory of Graphs Proceedings of the Colloquium on Graph Theory, held at Tihany, Hungary, 1966 Academic Press, New York; Akadémiai Kiadó, Budapest (1968), P. Erdős et al. MR 0232693 |
| Reference:
|
[6] Harris, J. M., Hirst, J. L., Mossinghoff, M. J.: Combinatorics and Graph Theory.Undergraduate Texts in Mathematics Springer, New York (2008). Zbl 1170.05001, MR 2440898 |
| Reference:
|
[7] Klavžar, S., Petkovšek, M.: Graphs with nonempty intersection of longest paths.Ars Comb. 29 (1990), 43-52. Zbl 0714.05037, MR 1046093 |
| Reference:
|
[8] Shabbir, A., Zamfirescu, C. T., Zamfirescu, T. I.: Intersecting longest paths and longest cycles: A survey.Electron. J. Graph Theory Appl. (electronic only) 1 (2013), 56-76. Zbl 1306.05121, MR 3093252 |
| Reference:
|
[9] Voss, H.-J.: Cycles and Bridges in Graphs.Mathematics and Its Applications 49, East European Series Kluwer Academic Publishers, Dordrecht; VEB Deutscher Verlag der Wissenschaften, Berlin (1991). Zbl 0731.05031, MR 1131525 |
| Reference:
|
[10] Walther, H.: Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen.J. Comb. Theory 6 German (1969), 1-6. Zbl 0184.27504, MR 0236054, 10.1016/S0021-9800(69)80098-0 |
| Reference:
|
[11] Walther, H., Voss, H.-J.: Über Kreise in Graphen.VEB Deutscher Verlag der Wissenschaften Berlin German (1974). Zbl 0288.05101 |
| Reference:
|
[12] West, D. B.: Open Problems---Graph Theory and Combinatorics, Hitting All Longest Paths.http://www.math.uiuc.edu/ west/openp/pathtran.html, accessed in January 2013. |
| Reference:
|
[13] Zamfirescu, T.: On longest paths and circuits in graphs.Math. Scand. 38 (1976), 211-239. Zbl 0337.05127, MR 0429645, 10.7146/math.scand.a-11630 |
| . |
