Spiders everywhere. (English) Zbl 1454.05068

Wiener, Gábor; Yokota, Maho; Zamfirescu, Carol T.

Discrete Appl. Math. 289, 516-522 (2021).

Summary: A spider is a tree with at most one branch (a vertex of degree at least 3) centred at the branch if it exists, and centred at any vertex otherwise. A graph \(G\) is arachnoid if for any vertex \(v\) of \(G\), there exists a spanning spider of \(G\) centred at \(v\) – in other words: there are spiders everywhere! Hypotraceable graphs are non-traceable graphs in which all vertex-deleted subgraphs are traceable. L. Gargano et al. [Discrete Math. 285, No. 1–3, 83–95 (2004; Zbl 1044.05048)] defined arachnoid graphs as natural generalisations of traceable graphs and asked for the existence of arachnoid graphs that are (i) non-traceable and non-hypotraceable, or (ii) in which some vertex is the centre of only spiders with more than three legs. An affirmative answer to (ii) implies an affirmative answer to (i). While non-traceable, non-hypotraceable arachnoid graphs were described in [G. Wiener, J. Graph Theory 84, No. 4, 443–459 (2017; Zbl 1359.05072)], (ii) remained open. In this paper we give an affirmative answer to this question and discuss spanning spiders whose legs must have some minimum length.

MSC:

05C45	Eulerian and Hamiltonian graphs
05C05	Trees

Keywords:

spanning tree; Hamiltonian path; hypotraceable

Citations:

Zbl 1044.05048; Zbl 1359.05072

References:

[1]	Balister, P. N.; Győri, E.; Lehel, J.; Schelp, R. H., Longest paths in circular arc graphs, Combin. Probab. Comput., 13, 311-317 (2004) · Zbl 1051.05053
[2]	Bondy, J. A., (Graham, R. L.; Grötschel, M.; Lovász, L., HandBook of Combinatorics, Vol. 1 (1995), North-Holland) · Zbl 0833.05001
[3]	Clark, L.; Entringer, R., Smallest maximally nonhamiltonian graphs, Period. Math. Hung., 14, 57-68 (1983) · Zbl 0489.05038
[4]	Gallai, T., Problem 4, (Erdős, P.; Katona, G., Theory of Graphs, Proc. Tihany 1966 (1968), Academic Press: Academic Press New York), 362 · Zbl 0155.00201
[5]	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
[6]	Thomassen, C., Hypohamiltonian and hypotraceable graphs, Discrete Math., 9, 91-96 (1974) · Zbl 0278.05110
[7]	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
[8]	Wiener, G., On non-traceable, non-hypotraceable, arachnoid graphs, Electron. Notes Discrete Math., 49, 621-627 (2015), J. Nešetřil, O. Serra, J.A. Telle (Eds.), Proc. EuroComb 2015 · Zbl 1346.05138
[9]	Wiener, G., Leaf-critical and leaf-stable graphs, J. Graph Theory, 84, 443-459 (2017) · Zbl 1359.05072
[10]	Wiener, G.; Zamfirescu, C. T., Gallai’s question and constructions of almost hypotraceable graphs, Discrete Appl. Math., 243, 270-278 (2018) · Zbl 1387.05072