| Title:
|
Minimum degree, leaf number and traceability (English) |
| Author:
|
Mukwembi, Simon |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
63 |
| Issue:
|
2 |
| Year:
|
2013 |
| Pages:
|
539-545 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
interconnection network |
| Keyword:
|
graph |
| Keyword:
|
leaf number |
| Keyword:
|
traceability |
| Keyword:
|
Hamiltonicity |
| Keyword:
|
Graffiti.pc |
| MSC:
|
05C45 |
| idZBL:
|
Zbl 06236430 |
| idMR:
|
MR3073977 |
| DOI:
|
10.1007/s10587-013-0036-y |
| . |
| Date available:
|
2013-07-18T15:08:55Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143331 |
| . |
| Reference:
|
[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. Zbl 1254.05085, MR 2864050, 10.1007/s11786-011-0074-5 |
| Reference:
|
[2] DeLaViña, E.: Written on the Wall II (Conjectures of Graffiti.pc).http://cms.dt.uh.edu/faculty/delavinae/research/wowII/. |
| Reference:
|
[3] DeLaViña, E., Waller, B.: Spanning trees with many leaves and average distance.Electron. J. Comb. 15 (2008), 16 p. Zbl 1181.05052, MR 2383453 |
| Reference:
|
[4] Ding, G., Johnson, T., Seymour, P.: Spanning trees with many leaves.J. Graph Theory 37 (2001), 189-197. Zbl 0986.05030, MR 1834849, 10.1002/jgt.1013 |
| Reference:
|
[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). Zbl 0466.05049, MR 0634535 |
| Reference:
|
[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. Zbl 0957.90010, 10.1016/S0377-2217(96)00327-X |
| Reference:
|
[7] Goodman, S., Hedetniemi, S.: Sufficient conditions for a graph to be Hamiltonian.J. Comb. Theory, Ser. B 16 (1974), 175-180. Zbl 0275.05126, MR 0357222, 10.1016/0095-8956(74)90061-6 |
| Reference:
|
[8] Gould, R. J., Jacobson, M. S.: Forbidden subgraphs and Hamiltonian properties and graphs.Discrete Math. 42 (1982), 189-196. Zbl 0495.05039, MR 0677052, 10.1016/0012-365X(82)90216-3 |
| Reference:
|
[9] Griggs, J. R., Wu, M.: Spanning trees in graphs of minimum degree 4 or 5.Discrete Math. 104 (1992), 167-183. Zbl 0776.05031, MR 1172845 |
| Reference:
|
[10] Kleitman, D. J., West, D. B.: Spanning trees with many leaves.SIAM J. Discrete Math. 4 (1991), 99-106. Zbl 0734.05041, MR 1090293, 10.1137/0404010 |
| Reference:
|
[11] Li, H.: Hamiltonian cycles in 2-connected claw-free-graphs.J. Graph Theory 20 447-457 (1995). Zbl 0841.05062, MR 1358535, 10.1002/jgt.3190200408 |
| Reference:
|
[12] Mukwembi, S., Munyira, S.: Radius, diameter and the leaf number.Quaest. Math. (Submitted). |
| Reference:
|
[13] Ren, S.: A sufficient condition for graphs with large neighborhood unions to be traceable.Discrete Math. 161 (1996), 229-234. Zbl 0869.05041, MR 1420535, 10.1016/0012-365X(95)00230-T |
| Reference:
|
[14] Storer, J. A.: Constructing full spanning trees for cubic graphs.Inf. Process Lett. 13 (1981), 8-11. Zbl 0482.05031, MR 0636311, 10.1016/0020-0190(81)90141-1 |
| . |
