- . ..

16/2011


. .

: 1, 3 4

.- . .. , 27, 191023 -,
dvk0@yandex.ru
This preprint was accepted November 24, 2011

:
   ,       $G$,   $t$  
   4  $s$   1  3,    ,      
${1\over 3}t +{1\over 4}s+{3\over 2}$  .
    ,    .
 .
: , ,

D. V. Karpov

SPANNING TREES WITH MANY LEAVES: LOWER BOUNDS IN TERMS OF NUMBER OF VERTICES OF DEGREE 1, 3 AND AT LEAST 4

ABSTRACT:
We prove, that every connected graph with $s$ vertices of degree~1 and~3 and~$t$ vertices of degree at least~4
has a spanning tree  with   at least ${1\over 3}t +{1\over 4}s+{3\over 2}$  leaves.
We present infinite series of graphs,  for which this bound is tight.

Key words: spanning tree, leaves, number of leaves
[Full text: Preprint in Russian (.ps.gz)
Back to all preprints
Back to the Steklov Institute of Mathematics at St.Petersburg