Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
longest path; matching number
longest path; matching number
Summary:
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 '(G)\leq 5$, which implies that Zamfirescu's conjecture is true.
References:
[1] Balister, P., Györi, E., Lehel, J., Schelp, R.: Longest paths in circular arc graphs. Comb. Probab. Comput. 13 (2004), 311-317. DOI 10.1017/S0963548304006145 | MR 2056401 | Zbl 1051.05053
[2] Brinkmann, G., Cleemput, N. Van: Private communication.
[3] Chen, F.: Nonempty intersection of longest paths in a graph with a small matching number. Czech. Math. J. 65 (2015), 545-553. DOI 10.1007/s10587-015-0193-2 | MR 3360444 | Zbl 1363.05129
[4] Chen, G., Ehrenmüller, J., Fernandes, C. G., Heise, C. G., Shan, S., Yang, P., Yates, A. N.: Nonempty intersection of longest paths in series-parallel graphs. Discrete Math. 340 (2017), 287-304. DOI 10.1016/j.disc.2016.07.023 | MR 3584816 | Zbl 1351.05123
[5] Rezende, S. F. de, Fernandes, C. G., Martin, D. M., Wakabayashi, Y.: Intersecting longest paths. Discrete Math. 313 (2013), 1401-1408. DOI 10.1016/j.disc.2013.02.016 | MR 3061125 | Zbl 1279.05041
[6] Gallai, T.: Problem 4. Theory of Graphs. Proceedings of the colloquium held at Tihany, Hungary, September 1966 P. Erdös, G. Katona Academic Press, New York (1968). MR 0232693 | Zbl 0155.00201
[7] Klavžar, S., Petkovšek, M.: Graphs with nonempty intersection of longest paths. Ars Comb. 29 (1990), 43-52. MR 1046093 | Zbl 0714.05037
[8] Petersen, J.: Die Theorie der regulären graphs. Acta Math. 15 (1891), 193-220 German \99999JFM99999 23.0115.03. DOI 10.1007/BF02392606 | MR 1554815
[9] Walther, H.: Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen. J. Comb. Theory 6 (1969), 1-6 German. DOI 10.1016/S0021-9800(69)80098-0 | MR 0236054 | Zbl 0184.27504
[10] Walther, H., Voss, H. J.: Über Kreise in Graphen. VEB Deutscher Verlag der Wissenschaften, Berlin (1974), German. MR 0539852 | Zbl 0288.05101
[11] Zamfirescu, T. I.: L'histoire et l'etat présent des bornes connues pour $P_k^j$, $C_k^j$, $\bar{P}_k^j$ et $\bar{C}_k^j$. Cah. Cent. Étud. Rech. Opér. 17 (1975), 427-439 French. MR 0401544 | Zbl 0313.05117
[12] Zamfirescu, T. I.: On longest paths and circuits in graphs. Math. Scand. 38 (1976), 211-239. DOI 10.7146/math.scand.a-11630 | MR 0429645 | Zbl 0337.05127
Search
Partner of
