Minimum degree, leaf number and traceability

Mukwembi, Simon. "Minimum degree, leaf number and traceability." Czechoslovak Mathematical Journal 63.2 (2013): 539-545. <http://eudml.org/doc/260602>.

@article{Mukwembi2013,
abstract = {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.},
author = {Mukwembi, Simon},
journal = {Czechoslovak Mathematical Journal},
keywords = {interconnection network; graph; leaf number; traceability; Hamiltonicity; Graffiti.pc; interconnection network; leaf number; traceability; Hamiltonicity; Graffiti.pc},
language = {eng},
number = {2},
pages = {539-545},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Minimum degree, leaf number and traceability},
url = {http://eudml.org/doc/260602},
volume = {63},
year = {2013},
}

TY - JOUR
AU - Mukwembi, Simon
TI - Minimum degree, leaf number and traceability
JO - Czechoslovak Mathematical Journal
PY - 2013
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 63
IS - 2
SP - 539
EP - 545
AB - 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.
LA - eng
KW - interconnection network; graph; leaf number; traceability; Hamiltonicity; Graffiti.pc; interconnection network; leaf number; traceability; Hamiltonicity; Graffiti.pc
UR - http://eudml.org/doc/260602
ER -