Geodesic
Minimum degree, leaf number and traceability
Czechoslovak Mathematical Journal, Tome 63 (2013) no. 2, pp. 539-545
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-013-0036-y
Classification : 05C45
Keywords: interconnection network; graph; leaf number; traceability; Hamiltonicity; Graffiti.pc 
@article{10_1007_s10587_013_0036_y,
     author = {Mukwembi, Simon},
     title = {Minimum degree, leaf number and traceability},
     journal = {Czechoslovak Mathematical Journal},
     pages = {539--545},
     year = {2013},
     volume = {63},
     number = {2},
     doi = {10.1007/s10587-013-0036-y},
     mrnumber = {3073977},
     zbl = {06236430},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0036-y/}
}
TY  - JOUR
AU  - Mukwembi, Simon
TI  - Minimum degree, leaf number and traceability
JO  - Czechoslovak Mathematical Journal
PY  - 2013
SP  - 539
EP  - 545
VL  - 63
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0036-y/
DO  - 10.1007/s10587-013-0036-y
LA  - en
ID  - 10_1007_s10587_013_0036_y
ER  - 
%0 Journal Article
%A Mukwembi, Simon
%T Minimum degree, leaf number and traceability
%J Czechoslovak Mathematical Journal
%D 2013
%P 539-545
%V 63
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0036-y/
%R 10.1007/s10587-013-0036-y
%G en
%F 10_1007_s10587_013_0036_y
Mukwembi, Simon. Minimum degree, leaf number and traceability. Czechoslovak Mathematical Journal, Tome 63 (2013) no. 2, pp. 539-545. doi: 10.1007/s10587-013-0036-y

[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 | MR | Zbl

[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 | Zbl

[4] Ding, G., Johnson, T., Seymour, P.: Spanning trees with many leaves. J. Graph Theory 37 (2001), 189-197. | DOI | MR | Zbl

[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 | Zbl

[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 | Zbl

[7] Goodman, S., Hedetniemi, S.: Sufficient conditions for a graph to be Hamiltonian. J. Comb. Theory, Ser. B 16 (1974), 175-180. | DOI | MR | Zbl

[8] Gould, R. J., Jacobson, M. S.: Forbidden subgraphs and Hamiltonian properties and graphs. Discrete Math. 42 (1982), 189-196. | DOI | MR | Zbl

[9] Griggs, J. R., Wu, M.: Spanning trees in graphs of minimum degree 4 or 5. Discrete Math. 104 (1992), 167-183. | MR | Zbl

[10] Kleitman, D. J., West, D. B.: Spanning trees with many leaves. SIAM J. Discrete Math. 4 (1991), 99-106. | DOI | MR | Zbl

[11] Li, H.: Hamiltonian cycles in 2-connected claw-free-graphs. J. Graph Theory 20 447-457 (1995). | DOI | MR | Zbl

[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 | MR | Zbl

[14] Storer, J. A.: Constructing full spanning trees for cubic graphs. Inf. Process Lett. 13 (1981), 8-11. | DOI | MR | Zbl

Cité par Sources :