Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
interconnection network; graph; leaf number; traceability; Hamiltonicity; Graffiti.pc
interconnection network; graph; leaf number; traceability; Hamiltonicity; Graffiti.pc
Summary:
Let $G$ be a finite connected graph with minimum degree $\delta $. The leaf number $L(G)$ of $G$ is defined as the maximum number of leaf vertices contained in a spanning tree of $G$. We prove that if $\delta \ge \frac {1}{2}(L(G)+1)$, then $G$ is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if $\delta \ge \smash {\frac {1}{2}}(L(G)+1)$, then $G$ contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaVi na and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin. 15 (2008), 1–16]. For $G$ claw-free, we show that if $\delta \ge \frac {1}{2}(L(G)+1)$, then $G$ is Hamiltonian. This again confirms, and even improves, the conjecture of Graffiti.pc for this class of graphs.
References:
[1] Čada, R., Flandrin, E., Kang, H.: A note on degree conditions for traceability in locally claw-free graphs. Math. Comput. Sci. 5 (2011), 21-25. DOI 10.1007/s11786-011-0074-5 | MR 2864050 | Zbl 1254.05085
[2] DeLaViña, E.: Written on the Wall II (Conjectures of Graffiti.pc). http://cms.dt.uh.edu/faculty/delavinae/research/wowII/
[3] DeLaViña, E., Waller, B.: Spanning trees with many leaves and average distance. Electron. J. Comb. 15 (2008), 16 p. MR 2383453 | Zbl 1181.05052
[4] Ding, G., Johnson, T., Seymour, P.: Spanning trees with many leaves. J. Graph Theory 37 (2001), 189-197. DOI 10.1002/jgt.1013 | MR 1834849 | Zbl 0986.05030
[5] Duffus, D., Jacobson, M. S., Gould, R. J.: Forbidden subgraphs and the Hamiltonian theme. The Theory and Applications of Graphs 4th int. Conf., Kalamazoo/Mich. 1980 Wiley, New York 297-316 (1981). MR 0634535 | Zbl 0466.05049
[6] Fernandes, L. M., Gouveia, L.: Minimal spanning trees with a constraint on the number of leaves. Eur. J. Oper. Res. 104 (1998), 250-261. DOI 10.1016/S0377-2217(96)00327-X | Zbl 0957.90010
[7] Goodman, S., Hedetniemi, S.: Sufficient conditions for a graph to be Hamiltonian. J. Comb. Theory, Ser. B 16 (1974), 175-180. DOI 10.1016/0095-8956(74)90061-6 | MR 0357222 | Zbl 0275.05126
[8] Gould, R. J., Jacobson, M. S.: Forbidden subgraphs and Hamiltonian properties and graphs. Discrete Math. 42 (1982), 189-196. DOI 10.1016/0012-365X(82)90216-3 | MR 0677052 | Zbl 0495.05039
[9] Griggs, J. R., Wu, M.: Spanning trees in graphs of minimum degree 4 or 5. Discrete Math. 104 (1992), 167-183. MR 1172845 | Zbl 0776.05031
[10] Kleitman, D. J., West, D. B.: Spanning trees with many leaves. SIAM J. Discrete Math. 4 (1991), 99-106. DOI 10.1137/0404010 | MR 1090293 | Zbl 0734.05041
[11] Li, H.: Hamiltonian cycles in 2-connected claw-free-graphs. J. Graph Theory 20 447-457 (1995). DOI 10.1002/jgt.3190200408 | MR 1358535 | Zbl 0841.05062
[12] Mukwembi, S., Munyira, S.: Radius, diameter and the leaf number. Quaest. Math. (Submitted).
[13] Ren, S.: A sufficient condition for graphs with large neighborhood unions to be traceable. Discrete Math. 161 (1996), 229-234. DOI 10.1016/0012-365X(95)00230-T | MR 1420535 | Zbl 0869.05041
[14] Storer, J. A.: Constructing full spanning trees for cubic graphs. Inf. Process Lett. 13 (1981), 8-11. DOI 10.1016/0020-0190(81)90141-1 | MR 0636311 | Zbl 0482.05031
Search
Partner of
