×
Wiener, Gábor; Zamfirescu, Carol T.

Gallai’s question and constructions of almost hypotraceable graphs. (English) Zbl 1387.05072

Discrete Appl. Math. 243, 270-278 (2018).
Summary: Consider a graph \(G\) in which the longest path has order \(| V(G) | - 1\). We denote the number of vertices \(v\) in \(G\) such that \(G - v\) is non-traceable with \(\mathfrak{t}_G\). Gallai asked in 1966 whether, in a connected graph, the intersection of all longest paths is non-empty. H. Walther [J. Comb. Theory 6, 1–6 (1969; Zbl 0184.27504)] showed that, in general, this is not true. In a graph \(G\) in which the longest path has \(| V(G) | - 1\) vertices, the answer to Gallai’s question is positive iff \(\mathfrak{t}_G \neq 0\). In this article we study almost hypotraceable graphs, which constitute the extremal case \(\mathfrak{t}_G = 1\). We give structural properties of these graphs, establish construction methods for connectivities 1 through 4, show that there exists a cubic 3-connected such graph of order 28, and draw connections to works of C. Thomassen [Discrete Math. 9, 91–96 (1974; Zbl 0278.05110); ibid. 14, 377–389 (1976; Zbl 0322.05130)] and L. Gargano et al. [ibid. 285, No. 1–3, 83–95 (2004; Zbl 1044.05048)].

Cited in 4 Documents

MSC:

05C12 Distance in graphs
05C38 Paths and cycles

Keywords:

Gallai’s problem; traceable; hypotraceable; almost hypotraceable

Citations:

Zbl 0184.27504; Zbl 0278.05110; Zbl 0322.05130; Zbl 1044.05048

Software:

GenHypohamiltonian
PDF BibTeX XML Cite
\textit{G. Wiener} and \textit{C. T. Zamfirescu}, Discrete Appl. Math. 243, 270--278 (2018; Zbl 1387.05072)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Araya, M.; Wiener, G., On cubic planar Hypohamiltonian and hypotraceable graphs, Electron. J. Combin., #P85, 1-11, (2011) · Zbl 1217.05065
[2] Balister, P.; Győri, E.; Lehel, J.; Schelp, R., Longest paths in circular arc graphs, Combin. Probab. Comput., 13, 311-317, (2004) · Zbl 1051.05053
[3] G. Brinkmann, N. Van Cleemput, Private communication, 2012.
[4] Chen, G.; Ehrenmüller, J.; Fernandes, C. G.; Heise, C. G.; Shan, S.; Yang, P.; Yates, A., Nonempty intersection of longest paths in series-parallel graphs, Discrete Math., 340, 287-304, (2017) · Zbl 1351.05123
[5] Chvátal, V., Flip-flops in Hypohamiltonian graphs, Canad. Math. Bull., 16, 33-41, (1973) · Zbl 0253.05142
[6] Collier, J. B.; Schmeichel, E. F., Systematic searches for Hypohamiltonian graphs, Networks, 8, 193-200, (1978) · Zbl 0384.05046
[7] Gallai, T., Problem 4, (Erdős, P.; Katona, G., Theory of Graphs, Proc. Tihany, 1966, (1968), Academic Press New York), 362
[8] Gargano, L.; Hammar, M.; Hell, P.; Stacho, L.; Vaccaro, U., Spanning spiders and light-splitting switches, Discrete Math., 285, 83-95, (2004) · Zbl 1044.05048
[9] J. Goedgebeur, C.T. Zamfirescu, On almost hypohamiltonian graphs, submitted for publication. See Section 3 of arXiv:1606.06577 [math.CO]. · Zbl 1391.05153
[10] Goedgebeur, J.; Zamfirescu, C. T., Improved bounds for Hypohamiltonian graphs, Ars Math. Contemp., 13, 235-257, (2017) · Zbl 1380.05034
[11] Grünbaum, B., Vertices missed by longest paths or circuits, J. Combin. Theory, Ser. A, 17, 31-38, (1974) · Zbl 0259.05120
[12] Holton, D. A.; Sheehan, J., Hypohamiltonian graphs, (The Petersen Graph, (1993), Cambridge University Press New York), (Chapter 7)
[13] Horton, J. D., A hypotraceable graph, research report CORR 73-4, (1973), Dept. Combin. and Optim., Univ. Waterloo
[14] Jooyandeh, M.; McKay, B. D.; Östergård, P. R.J.; Pettersson, V. H.; Zamfirescu, C. T., Planar Hypohamiltonian graphs on 40 vertices, J. Graph Theory, 84, 121-133, (2017) · Zbl 1356.05029
[15] Kapoor, S. F.; Kronk, H. V.; Lick, D. R., On detours in graphs, Canad. Math. Bull., 11, 195-201, (1968) · Zbl 0167.22002
[16] Klavžar, S.; Petkovšek, M., Graphs with nonempty intersection of longest paths, Ars Combin., 29, 43-52, (1990) · Zbl 0714.05037
[17] Kronk, H. V.; Klee, V., Does there exist a hypotraceable graph?, Research Problems, Amer. Math. Monthly, 76, 809-810, (1969)
[18] B.D. McKay, Private communication, 2015.
[19] Rautenbach, D.; Sereni, J.-S., Transversals of longest paths and cycles, SIAM J. Discrete Math., 28, 335-341, (2014) · Zbl 1293.05183
[20] Schmitz, W., Über längste wege und kreise in graphen, Rend. Semin. Mat. Univ. Padova, 53, 97-103, (1975) · Zbl 0326.05114
[21] Shabbir, A.; Zamfirescu, C. T.; Zamfirescu, T., Intersecting longest paths and longest cycles: A survey, Electron. J. Graph Theory Appl., 1, 56-76, (2013) · Zbl 1306.05121
[22] Sousselier, R., Problème no. 29: le cercle des irascibles, Rev. Franç. Rech. Opérat., 7, 405-406, (1963)
[23] Steffen, E., Measurements of edge-uncolorability, Discrete Math., 280, 191-214, (2004) · Zbl 1041.05031
[24] Thomassen, C., Hypohamiltonian and hypotraceable graphs, Discrete Math., 9, 91-96, (1974) · Zbl 0278.05110
[25] Thomassen, C., On Hypohamiltonian graphs, Discrete Math., 10, 383-390, (1974) · Zbl 0286.05122
[26] Thomassen, C., Planar and infinite Hypohamiltonian and hypotraceable graphs, Discrete Math., 14, 377-389, (1976) · Zbl 0322.05130
[27] Thomassen, C., Hypohamiltonian graphs and digraphs, (Theory and Applications of Graphs, Lecture Notes in Mathematics, vol. 642, (1978), Springer Berlin), 557-571 · Zbl 0371.05015
[28] Thomassen, C., Planar cubic Hypohamiltonian and hypotraceable graphs, J. Combin. Theory, Ser. B, 30, 36-44, (1981) · Zbl 0388.05033
[29] Walther, H., Über die nichtexistenz eines knotenpunktes, durch den alle längsten wege eines graphen gehen, J. Combin. Theory, 6, 1-6, (1969) · Zbl 0184.27504
[30] Walther, H.; Voss, H.-J., Über kreise in graphen, (1974), VEB Deutscher Verlag der Wissenschaften Berlin · Zbl 0288.05101
[31] Wiener, G.; Nešetřil, J.; Serra, O.; Telle, J. A., On non-traceable, non-hypotraceable, arachnoid graphs, Proc. EuroComb, 2015, Electron. Notes Discrete Math., 49, 621-627, (2015) · Zbl 1346.05138
[32] Wiener, G., On constructions of hypotraceable graphs, Electron. Notes Discrete Math., 54, 127-132, (2016) · Zbl 1356.05078
[33] Wiener, G., Leaf-critical and leaf-stable graphs, J. Graph Theory, 84, 443-459, (2017) · Zbl 1359.05072
[34] Wiener, G., New constructions of Hypohamiltonian and hypotraceable graphs, J. Graph Theory, 87, 526-535, (2018) · Zbl 1386.05102
[35] Wiener, G.; Araya, M., On planar Hypohamiltonian graphs, J. Graph Theory, 67, 55-68, (2011) · Zbl 1223.05168
[36] Zamfirescu, C. T., On hypohamiltonian and almost Hypohamiltonian graphs, J. Graph Theory, 79, 63-81, (2015) · Zbl 1312.05076
[37] Zamfirescu, C. T., Hypohamiltonian and almost Hypohamiltonian graphs, (2016), Ghent University, (PhD thesis) · Zbl 1376.05081
[38] Zamfirescu, C. T.; Zamfirescu, T. I., A planar Hypohamiltonian graph with \(48\) vertices, J. Graph Theory, 55, 338-342, (2007) · Zbl 1120.05054
[39] Zamfirescu, T., On longest paths and circuits in graphs, Math. Scand., 38, 211-239, (1976) · Zbl 0337.05127
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.