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

Fuyuan Chen

Czechoslovak Mathematical Journal (2015)

  • Volume: 65, Issue: 2, page 545-553
  • ISSN: 0011-4642

Abstract

top
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 α ' ( 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 α ' ( G ) ≤ 3 .

How to cite

top

Chen, Fuyuan. "Nonempty intersection of longest paths in a graph with a small matching number." Czechoslovak Mathematical Journal 65.2 (2015): 545-553. <http://eudml.org/doc/270121>.

@article{Chen2015,
abstract = {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 ^\{\prime \}(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 ^\{\prime \}(G)\le 3$.},
author = {Chen, Fuyuan},
journal = {Czechoslovak Mathematical Journal},
keywords = {longest path; matching number},
language = {eng},
number = {2},
pages = {545-553},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Nonempty intersection of longest paths in a graph with a small matching number},
url = {http://eudml.org/doc/270121},
volume = {65},
year = {2015},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 2
SP - 545
EP - 553
AB - 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 ^{\prime }(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 ^{\prime }(G)\le 3$.
LA - eng
KW - longest path; matching number
UR - http://eudml.org/doc/270121
ER -

References

top
  1. Balister, P. N., Győri, E., Lehel, J., Schelp, R. H., 10.1017/S0963548304006145, Comb. Probab. Comput. 13 (2004), 311-317. (2004) Zbl1051.05053MR2056401DOI10.1017/S0963548304006145
  2. Bondy, J. A., Murty, U. S. R., 10.1007/978-1-84628-970-5_1, Graduate Texts in Mathematics 244 Springer, Berlin (2008). (2008) Zbl1134.05001MR2368647DOI10.1007/978-1-84628-970-5_1
  3. Rezende, S. F. de, Fernandes, C. G., Martin, D. M., Wakabayashi, Y., 10.1016/j.disc.2013.02.016, Discrete Math. 313 (2013), 1401-1408. (2013) Zbl1279.05041MR3061125DOI10.1016/j.disc.2013.02.016
  4. Ehrenmüller, J., Fernandes, C. G., Heise, C. G., Nonempty intersection of longest paths in series-parallel graphs, Preprint 2013, arXiv:1310.1376v2. 
  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. (1968) MR0232693
  6. Harris, J. M., Hirst, J. L., Mossinghoff, M. J., Combinatorics and Graph Theory, Undergraduate Texts in Mathematics Springer, New York (2008). (2008) Zbl1170.05001MR2440898
  7. Klavžar, S., Petkovšek, M., Graphs with nonempty intersection of longest paths, Ars Comb. 29 (1990), 43-52. (1990) Zbl0714.05037MR1046093
  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. (2013) Zbl1306.05121MR3093252
  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). (1991) Zbl0731.05031MR1131525
  10. Walther, H., 10.1016/S0021-9800(69)80098-0, J. Comb. Theory 6 German (1969), 1-6. (1969) Zbl0184.27504MR0236054DOI10.1016/S0021-9800(69)80098-0
  11. Walther, H., Voss, H.-J., Über Kreise in Graphen, VEB Deutscher Verlag der Wissenschaften Berlin German (1974). (1974) Zbl0288.05101
  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. 
  13. Zamfirescu, T., 10.7146/math.scand.a-11630, Math. Scand. 38 (1976), 211-239. (1976) Zbl0337.05127MR0429645DOI10.7146/math.scand.a-11630

NotesEmbed ?

top

You must be logged in to post comments.