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

Cité par Sources :