Mathematical Problems of Computer Science 46, 18{25, 2016.

Spanning T r ees with few B r anch and End Ver tices

Institute for Informatics and Automation Problems of NAS RA

e-mail: zhora@ipia.sci.am

Abstract

For a graph G, let ¾2 be the minimum degree sum of two nonadjacent vertices in G.
A vertex of degree one in a tree is called an end vertex and a vertex of degree at least
three is called a branch vertex. We consider: (¤) connected graphs on n vertices such
that ¾2 ¸ n ¡ k + 1 for some positive integer k. In 1976, it was proved (by the author)
that every graph satisfying (¤), has a spanning tree with at most k end vertices. In
this paper we ¯rst show that every graph satisfying (¤), has a spanning tree with at
most k + 1 branch and end vertices altogether. The next result states that every graph
satisfying (¤), has a spanning tree with at most 1

2
(k ¡ 1) branch vertices. The third

result states that every graph satisfying (¤), has a spanning tree with at most 3
2
(k ¡ 1)

degree sum of branch vertices. All results are sharp.

Keywords: Spanning tree, End vertex, k-ended tree, Branch vertex, Degree sum
of the branch vertices, Ore-type condition.

1 . In t r o d u c t io n

Th r o u g h o u t t h is a r t ic le we c o n s id e r o n ly ¯ n it e u n d ir e c t e d g r a p h s wit h o u t lo o p s o r m u lt ip le
e d g e s . Th e s e t o f ve r t ic e s o f a g r a p h G is d e n o t e d b y V ( G ) a n d t h e s e t o f e d g e s b y - E ( G) .
A g o o d r e fe r e n c e fo r a n y u n d e ¯ n e d t e r m s is [1 ].

Fo r a g r a p h G, we u s e n a n d ® t o d e n o t e t h e o r d e r ( t h e n u m b e r o f ve r t ic e s ) a n d t h e
in d e p e n d e n c e n u m b e r o f G, r e s p e c t ive ly. If ® ¸ k fo r s o m e in t e g e r k, le t ¾k b e t h e m in im u m
d e g r e e s u m o f a n in d e p e n d e n t s e t o f k ve r t ic e s ; o t h e r wis e we le t ¾k = +1. Fo r a s u b s e t
S µ V ( G ) , we d e n o t e b y G[S] t h e s u b g r a p h o f G in d u c e d b y S. W e u s e dG ( v ) t o d e n o t e t h e
n u m b e r o f n e ig h b o r s o f a ve r t e x v in G, c a lle d t h e d e g r e e o f v in G. Th e m in im u m d e g r e e
in G is d e n o t e d b y ±.

If Q is a p a t h o r a c yc le in a g r a p h G, t h e n t h e o r d e r o f Q, d e n o t e d b y jQj, is jV ( Q) j.
Th e g r a p h G is h a m ilt o n ia n if G c o n t a in s a H a m ilt o n c yc le , i.e ., a c yc le c o n t a in in g e ve r y
ve r t e x o f G.

W e wr it e a p a t h Q wit h a g ive n o r ie n t a t io n b y
¡!
Q . Fo r x; y 2 V ( Q ) , we d e n o t e b y x¡!Q y

t h e s u b p a t h o f Q in t h e c h o s e n d ir e c t io n fr o m x t o y. W e u s e x+ t o d e n o t e t h e s u c c e s s o r , a n d
x¡ t h e p r e d e c e s s o r , o f a ve r t e x x 2 V ( Q ) . Fo r X µ V ( Q) , we d e ¯ n e X + = fx+ : x 2 Xg
a n d X¡ = fx¡ : x 2 Xg.

¤G.G. Nicoghossian (up to 1997)

1 8

Zh o r a G. N iko g h o s ya n ¤



Zh. Nikoghosyan 1 9

A ve r t e x o f d e g r e e o n e is c a lle d a n e n d -ve r t e x, a n d a n e n d -ve r t e x o f a t r e e is u s u a lly
c a lle d a le a f. Th e s e t o f e n d -ve r t ic e s o f G is d e n o t e d b y End ( G) . A b r a n c h ve r t e x o f a t r e e
is a ve r t e x o f d e g r e e a t le a s t t h r e e . Th e s e t o f b r a n c h ve r t ic e s o f a t r e e T will b e d e n o t e d
b y B ( T ) . Fo r a p o s it ive in t e g e r k, a t r e e T is s a id t o b e a k-e n d e d t r e e if jEnd( T ) j · k.
A H a m ilt o n p a t h is a s p a n n in g 2 -e n d e d t r e e . A H a m ilt o n c yc le c a n b e in t e r p r e t e d a s a
s p a n n in g 1 -e n d e d t r e e .

In 1 9 5 2 , D ir a c [2 ] p r o ve d t h a t e ve r y g r a p h wit h ± ¸ n=2 h a s a H a m ilt o n c yc le . Th e
d e g r e e s u m ve r s io n o f t h is r e s u lt wa s p r o ve d in 1 9 6 0 d u e t o Or e [3 ]: e ve r y g r a p h wit h ¾2 ¸ n
h a s a H a m ilt o n c yc le .

Th e a n a lo g s o f t h e s e t wo c la s s ic a l r e s u lt s fo r H a m ilt o n p a t h s fo llo w e a s ily.
T heor em A: [2 ]. E very graph with ± ¸ ( n ¡ 1 ) =2 has a Hamilton path.
T heor em B : [3 ]. E very graph with ¾2 ¸ n ¡ 1 has a Hamilton path.

Th e n e xt r e s u lt t o o k a d i®e r e n t a p p r o a c h d u e t o Ch v¶a t a l a n d E r d }o s [4 ] b a s e d o n c o n -
n e c t ivit y a n d in d e p e n d e n c e n u m b e r : e ve r y k-c o n n e c t e d ( k ¸ 1 ) g r a p h wit h ® · k h a s a
H a m ilt o n c yc le . Th e H a m ilt o n p a t h ve r s io n o f t h is r e s u lt c a n b e fo r m u la t e d a s fo llo ws .
T heor em C: [4 ]. E very k-connected ( k ¸ 1 ) graph with ® · k + 1 has a Hamilton path.

A H a m ilt o n p a t h c a n b e r e g a r d e d a s a s p a n n in g t r e e wit h e xa c t ly t wo le a ve s , a s p a n n in g
t r e e wit h n o b r a n c h ve r t e x, o r a s p a n n in g t r e e wit h m a xim u m d e g r e e t wo . Th e r e fo r e , a s
o n e o f g e n e r a liz e d p r o b le m s o f a H a m ilt o n p a t h p r o b le m , it is n a t u r a l t o lo o k fo r c o n d it io n s
wh ic h e n s u r e t h e e xis t e n c e o f a s p a n n in g t r e e wit h fe w le a ve s , fe w b r a n c h ve r t ic e s o r b o u n d e d
m a xim u m d e g r e e m o t iva t e d fr o m o p t im iz a t io n a s p e c t s wit h va r io u s a p p lic a t io n s .

In t h is p a p e r we c o n s id e r t r e e p r o b le m s a r is in g in t h e c o n t e xt o f o p t ic a l a n d c e n t r a liz e d
t e r m in a l n e t wo r ks : ( i) ¯ n d in g a s p a n n in g t r e e o f G wit h t h e m in im u m n u m b e r o f e n d ve r t ic e s ,
( ii) ¯ n d in g a s p a n n in g t r e e wit h t h e m in im u m n u m b e r o f b r a n c h ve r t ic e s a n d ( iii) ¯ n d in g a
s p a n n in g t r e e o f G s u c h t h a t t h e d e g r e e s u m o f t h e b r a n c h ve r t ic e s is m in im iz e d , m o t iva t e d
b y n e t wo r k d e s ig n p r o b le m s wh e r e ju n c t io n s a r e s ig n i¯ c a n t ly m o r e e xp e n s ive t h a n s im p le
e n d - o r t h r o u g h -n o d e s , a n d a r e , t h u s , t o b e a vo id e d .

A ll t h e s e p r o b le m s a r e N P -h a r d b e c a u s e t h e y c o n t a in t h e H a m ilt o n p a t h p r o b le m a s a
p a r t ic u la r c a s e .

Th e c o n s t r a in t o n t h e n u m b e r o f e n d ve r t ic e s a r is e s b e c a u s e t h e s o ft wa r e a n d h a r d wa r e
a s s o c ia t e d t o e a c h t e r m in a l d i®e r s a c c o r d in g ly wit h it s p o s it io n in t h e t r e e . U s u a lly, t h e
s o ft wa r e a n d h a r d wa r e a s s o c ia t e d t o a \ d e g r e e -l" t e r m in a l is c h e a p e r t h a n t h e s o ft wa r e a n d
h a r d wa r e u s e d in t h e r e m a in in g t e r m in a ls b e c a u s e fo r a n y in t e r m e d ia t e t e r m in a l j o n e n e e d s
t o c h e c k if t h e a r r iva l m e s s a g e is d e s t in e d t o t h a t n o d e o r t o a n y o t h e r n o d e lo c a t e d a ft e r
n o d e j. A s a c o n s e qu e n c e , t h a t p a r t ic u la r t e r m in a l n e e d s s o ft wa r e a n d h a r d wa r e fo r m e s s a g e
r o u t in g . On t h e o t h e r h a n d , s u c h e qu ip m e n t is n o t n e e d e d in " d e g r e e -l" t e r m in a ls . A s s u m in g
t h a t t h e h a r d wa r e a n d s o ft wa r e fo r m e s s a g e r o u t in g in t h e n o d e s is a lr e a d y a va ila b le , t h e
a b o ve d is c u s s io n m o t iva t e s a c o n s t r a in t s t a t in g t h a t a t r e e s o lu t io n h a s t o c o n t a in e xa c t ly a
c e r t a in n u m b e r o f \ d e g r e e -l" t e r m in a ls .

A d i®e r e n t s it u a t io n , r e s u lt in g fr o m a n e w t e c h n o lo g y a llo win g a s wit c h t o r e p lic a t e t h e
s ig n a l b y s p lit t in g lig h t . A lig h t -t r e e c o n n e c t s o n e n o d e t o a s e t o f o t h e r n o d e s in t h e n e t wo r k
- a llo win g m u lt ic a s t c o m m u n ic a t io n fr o m t h e s o u r c e t o a s e t o f d e s t in a t io n s ( in c lu d in g t h e
p o s s ib ilit y o f t h e s e t o f d e s t in a t io n s c o n s is t in g o f a ll o t h e r n o d e s ) . Th e s wit c h e s wh ic h
c o r r e s p o n d t o t h e n o d e s o f d e g r e e g r e a t e r t h a n t wo h a ve t o b e a b le t o s p lit lig h t ( e xc e p t
fo r t h e s o u r c e o f t h e m u lt ic a s t , wh ic h c a n t r a n s m it t o a n y n u m b e r o f n e ig h b o r s ) . Typ ic a l
o p t ic a l n e t wo r ks will h a ve a lim it e d n u m b e r o f t h e s e m o r e s o p h is t ic a t e d s wit c h e s , a n d o n e
h a s t o p o s it io n t h e m in s u c h a wa y t h a t a ll p o s s ib le m u lt ic a s t s c a n b e p e r fo r m e d . Th u s , we



2 0 Spanning Trees with few Branch and End Vertices

a r e le a d t o t h e p r o b le m o f ¯ n d in g s p a n n in g t r e e s wit h a s fe w b r a n c h ve r t ic e s a s p o s s ib le .
In 1 9 7 1 , L a s V e r g n a s [5 ] g a ve a d e g r e e c o n d it io n t h a t g u a r a n t e e s t h a t a n y fo r e s t in G o f

lim it e d s iz e a n d wit h a lim it e d n u m b e r o f le a ve s c a n b e e xt e n d e d t o a s p a n n in g t r e e o f G
wit h a lim it e d n u m b e r o f le a ve s in a n a p p r o p r ia t e s e n s e . Th is r e s u lt im p lie s a s a c o r o lla r y a
d e g r e e s u m c o n d it io n fo r t h e e xis t e n c e o f a t r e e wit h a t m o s t k le a ve s in c lu d in g Th e o r e m B
a s a s p e c ia l c a s e fo r k = 1 .
T heor em D: [6 ], [5 ], [7 ]. L et G be a connected graph with ¾2 ¸ n ¡ k + 1 for some positive
integer k. Then G has a spanning k-ended tree.

H o we ve r , Th e o r e m D wa s ¯ r s t o p e n ly fo r m u la t e d a n d p r o ve d in 1 9 7 6 b y t h e a u t h o r [6 ].
L a t e r , it wa s r e p r o ve d in 1 9 9 8 b y B r o e r s m a a n d Tu in s t r a [7 ].

Th e n e xt g e n e r a liz a t io n c o n t a in s Th e o r e m C a s a s p e c ia l c a s e ( k = 1 ) d u e t o W in [8 ].
T heor em E : [8 ]. L et G be an s-connected graph with ® · s + k ¡ 1 for some integer k ¸ 1 .
Then G has a spanning k-ended tree.

On e o f t h e in t e r e s t in t h e e xis t e n c e o f s p a n n in g t r e e s wit h b o u n d e d n u m b e r o f b r a n c h
ve r t ic e s a r is e s in t h e r e a lm o f m u lt ic a s t in g in o p t ic a l n e t wo r ks .

Ga r g a n o , H a m m a r , H e ll, S t a c h o a n d V a c c a r o [9 ] p r o ve d t h e fo llo win g .
T heor em F: [9 ]. E very connected graph with ¾3 ¸ n ¡ 1 has a spanning tree with at most
one branch vertex.

Fla n d r in e t a l. [1 0 ] p o s e d t h e fo llo win g c o n je c t u r e .
Conjectur e A: [1 0 ]. If G is a connected graph with ¾k+3 ¸ n ¡ k for some positive integer
k, then G has a spanning tree with at most k branch vertices.

R e c e n t ly, Ma t s u d a , Oz e ki a n d Y a m a s h it a [1 1 ] e s t a b lis h e d a n u p p e r b o u n d fo r t h e in d e -
p e n d e n c e n u m b e r ® wh ic h im p lie s t h e e xis t e n c e o f a s p a n n in g t r e e wit h b o u n d e d n u m b e r o f
b r a n c h ve r t ic e s in c o n n e c t e d c la w-fr e e g r a p h s .
T heor em G: [1 1 ]. L et k be a non-negative integer. A connected claw-free graph G has a
spanning tree with at most k branch vertices if ® · 2 k + 2 .

In t h is p a p e r we p r e s e n t a s h a r p Or e -t yp e c o n d it io n fo r t h e e xis t e n c e o f s p a n n in g t r e e s in
c o n n e c t e d g r a p h s wit h b o u n d e d t o t a l n u m b e r o f b r a n c h a n d e n d ve r t ic e s im p r o vin g Th e o r e m
D b y in c o r p o r a t in g t h e n u m b e r o f b r a n c h ve r t ic e s a s a p a r a m e t e r .
T heor em 1:. L et G be a connected graph of order n. If ¾2 ¸ n ¡ k + 1 for some positive
integer k, then G has a spanning tree T with at most k ¡ jB ( T ) j + 1 end vertices.

L e t G b e t h e c o m p le t e b ip a r t it e g r a p h K±;±+k¡1 o f o r d e r n = 2 ± + k ¡ 1 a n d m in im u m
d e g r e e ±, wh e r e k ¸ 3 . Cle a r ly, ¾2 ( G) = 2 ± = n¡k+1 . B y Th e o r e m 1 , G h a s a s p a n n in g t r e e
T wit h jEnd( T ) j · k ¡ b + 1 . Ob s e r vin g t h a t T is n o t ( k ¡ 1 ) -e n d e d , t h a t is jEnd ( T ) j ¸ k,
we h a ve b · 1 . On t h e o t h e r h a n d , we h a ve b ¸ 1 , s in c e jEnd( T ) j ¸ k ¸ 3 , wh ic h im p lie s
b = 1 . Th is m e a n s t h a t T is n o t ( k ¡ b ) -e n d e d a n d c o n s e qu e n t ly, Th e o r e m 1 is s h a r p fo r
e a c h k ¸ 3 .

Th e n e xt r e s u lt fo llo ws fr o m Th e o r e m 1 p r o vid in g a s h a r p Or e -t yp e c o n d it io n fo r t h e
e xis t e n c e o f s p a n n in g t r e e s in c o n n e c t e d g r a p h s wit h fe w b r a n c h ve r t ic e s .
T heor em 2: L et G be a connected graph of order n. If ¾2 ¸ n ¡ k + 1 for some positive
integer k, then G has a spanning tree with at most ( k ¡ 1 ) =2 branch vertices.

Th e t h ir d r e s u lt p r o vid e s a n Or e -t yp e c o n d it io n fo r t h e e xis t e n c e o f s p a n n in g t r e e s in
c o n n e c t e d g r a p h s wit h b o u n d e d d e g r e e s u m o f t h e b r a n c h ve r t ic e s .
T heor em 3: L et G be a connected graph of order n. If ¾2 ¸ n ¡ k + 1 for some positive
integer k, then G has a spanning tree with at most 3

2
( k ¡ 1 ) degree sum of the branch vertices.

L e t G b e a g r a p h ( t r e e ) o b t a in e d fr o m t h e p a t h v0v1:::vbvb+1 b y a d d in g n e w ve r t ic e s



Zh. Nikoghosyan 2 1

u1; :::; ub a n d t h e e d g e s uivi ( i = 1 ; :::; b) . Cle a r ly, n = 2 b + 2 a n d ¾2 = 2 = n ¡ ( 2 b + 1 ) + 1 .
S in c e jB ( G ) j = b, t h e b o u n d ( k ¡ 1 ) = 2 in Th e o r e m 2 is s h a r p . Fu r t h e r , s in c e Pbi=1 d ( vi ) =
3
2
( k ¡ 1 ) , t h e b o u n d 3

2
( k ¡ 1 ) in Th e o r e m 3 is s h a r p a s we ll.

Th e o r e m s 1 ,2 ,3 we r e a n n o u n c e d in 2 0 1 5 [1 2 ] a n d Th e o r e m 1 wa s p r o ve d in d e p e n d e n t ly
b y S a it o a n d S a n o [1 3 ].

2 . P r o o f o f Th e o r e m 1

P r oof of T heor em 1: L e t G b e a c o n n e c t e d g r a p h wit h ¾2 ¸ n ¡ k + 1 a n d le t T b e a
s p a n n in g t r e e in G. A s s u m e t h a t

( a 1 ) T is c h o s e n s o t h a t jEnd( T ) j is a s s m a ll a s p o s s ib le .
P u t End( T ) = f»1; :::; »f g. L e t

¡!
P2 = »1

¡!
P2 »2 b e t h e u n iqu e p a t h in T wit h e n d ve r t ic e s

»1 a n d »2. Fu r t h e r , a s s u m e t h a t

( a 2 ) T is c h o s e n s o t h a t P2 is a s lo n g a s p o s s ib le , s u b je c t t o ( a1 ) .

P u t jB ( T ) j = b. If f = 2 t h e n P2 is a 2 -e n d e d s p a n n in g t r e e ( H a m ilt o n p a t h ) in G wit h
jB ( P2 ) j = b = 0 , im p lyin g t h a t f = 2 · k + 1 = k ¡ b + 1 .

N o w le t f ¸ 3 , t h a t is b ¸ 1 .
Claim 1: If P is a Hamilton path in G[V ( P2 ) ] with end vertices x; y, then N ( x) [ N ( y ) µ
V ( P2 ) .

P r oof: A s s u m e t h e c o n t r a r y a n d a s s u m e w.l.o .g . t h a t N ( x) 6µ V ( P2 ) . P u t T 0 =
T ¡ E ( P2 ) + E ( P ) . Cle a r ly, T 0 is a n f -e n d e d s p a n n in g t r e e in G a n d xv 2 E ( G ) fo r
s o m e v 2 V ( G ¡ P ) . L e t C b e t h e u n iqu e c yc le in T 0 + xv a n d le t vv0 b e t h e u n iqu e e d g e
o n C wit h v0 6= x. Th e n T 0+xv¡vv0 is a n f-e n d e d s p a n n in g t r e e in G, c o n t r a d ic t in g ( a 2 ) . 4

B y Cla im 1 , N ( »1 ) [ N ( »2 ) µ V ( P2 ) . If N ( »1 ) \ N + ( »2 ) 6= ; t h e n c le a r ly, G[V ( P2 ) ] h a s
a H a m ilt o n c yc le . S in c e b ¸ 1 , G[V ( P2 ) ] h a s a H a m ilt o n p a t h wit h e n d ve r t e x x s u c h t h a t
N ( x ) 6µ V ( P2 ) , c o n t r a d ic t in g Cla im 1 . H e n c e , N ( »1 ) \ N + ( »2 ) = ;. Ob s e r vin g a ls o t h a t
»1 62 N ( »1 ) [ N + ( »2 ) a n d N + ( »2 ) µ V ( P2 ) , we g e t

jP2j ¸ jN ( »1 ) j + jN + ( »2 ) j + jf»1gj

= d( »1 ) + d ( »2 ) + 1 ¸ ¾2 + 1 : ( 1 )

Fo r e a c h i 2 f 3 ; :::; fg, le t ¡!Pi = »i
¡!
Pi zi b e t h e u n iqu e p a t h in T b e t we e n »i a n d t h e n e a r e s t

ve r t e x zi o f P2. Cle a r ly, zi 2 B ( T ) ( i = 3 ; :::; f ) .

Case 1: jPij = 2 ( i = 3 ; :::; f ) .
It fo llo ws t h a t B ( T ) µ V ( P2 ) . If b = 1 , t h e n b y ( 1 ) , jP2j ¸ ¾2 + b a n d t h e r e fo r e ,

f = jf»3; :::; »f gj + 2 = n ¡ jP2j + 2

· n ¡ ¾2 ¡ b + 2 · k ¡ b + 1 :
L e t b ¸ 2 a n d le t x1; :::; xb b e t h e e le m e n t s o f B ( T ) , o c c u r r in g o n

¡!
P2 in a c o n s e c u t ive

o r d e r . A s s u m e w.l.o .g . t h a t x1 = z3. Fu r t h e r , a s s u m e t h a t



( a 3 ) T is c h o s e n s o t h a t dT ( x1 ) is a s s m a ll a s p o s s ib le , s u b je c t t o ( a1 ) a n d ( a2 ) .

If »3v1 2 E ( G) fo r s o m e v1 2 V ( x+1
¡!
P2 »2 ) , t h e n T + »3v1 ¡ »3x1 is a n f-e n d e d t r e e ,

c o n t r a d ic t in g ( a 3 ) . H e n c e , we c a n a s s u m e t h a t N ( »3 ) µ V ( »1
¡!
P2 x1 ) , t h a t is

( N ( »3 ) ¡ z3 ) \ B ( T ) = ;: ( 2 )

N e xt , if N ¡ ( »1 ) \ ( N ( »3 ) ¡ z3 ) h a s a n e le m e n t v2, t h e n

v2
á
P2»1v

+
2

¡!
P2 »2

is a H a m ilt o n p a t h in G[V ( P2 ) ] wit h e n d ve r t e x v2 s u c h t h a t N ( v2 ) 6µ V ( P2 ) , c o n t r a d ic t in g
Cla im 1 . H e n c e ,

N¡ ( »1 ) \ ( N ( »3 ) ¡ z3 ) = ;: ( 3 )
Fin a lly, if N¡ ( »1 ) \ B ( T ) 6= ;, t h a t is »1z+i 2 E ( G ) fo r s o m e i 2 f 3 ; :::; fg, t h e n

zi
á
P2»1z

+
i

¡!
P2 »2

is a H a m ilt o n p a t h in G[V ( P2 ) ] wit h e n d ve r t e x zi s u c h t h a t N ( zi ) 6µ V ( P2 ) , a g a in c o n t r a -
d ic t in g Cla im 1 . H e n c e ,

N¡ ( »1 ) \ B ( T ) = ;: ( 4 )
U s in g ( 2 ) , ( 3 ) , ( 4 ) a n d o b s e r vin g t h a t »2 62 N¡ ( »1 ) [ ( N ( »3 ) ¡ z3 ) [ B ( T ) , we g e t

jV ( P2 ) j ¸ jN ¡ ( »1 ) j + jN ( »3 ) ¡ z3j + jB ( T ) j + jf»2gj

¸ d( »1 ) + d( »3 ) + b ¸ ¾2 + b;
im p lyin g t h a t

f = jf»3; :::; »f gj + 2 = n ¡ jV ( P2 ) j + 2
· n ¡ ¾2 ¡ b + 2 · k ¡ b + 1 :

Case 2: jPij ¸ 3 fo r s o m e i 2 f 3 ; :::; fg, s a y i = 3 .
Case 2.1: N¡ ( »1 ) \ N + ( »2 ) 6= ;.
It fo llo ws t h a t »1w

+; »2w
¡ 2 E ( G) fo r s o m e w 2 N ¡ ( »1 ) \ N + ( »2 ) . If z3 = w t h e n

w
á
P2 »1w

+¡!P2 »2

is a H a m ilt o n p a t h in G[V ( P2 ) ] wit h e n d ve r t e x w s u c h t h a t N ( w ) 6µ V ( P2 ) , c o n t r a d ic t in g
Cla im 1 . H e n c e z3 6= w. A s s u m e w.l.o .g . t h a t z3 2 V ( »1

¡!
P2 w

¡ ) . P u t

T 0 = T + »1w
+ + »2w

¡ ¡ z3z¡3 ¡ ww¡:

Cle a r ly, T 0 is a s p a n n in g f-e n d e d t r e e in G a n d

»3
¡!
P3z3

¡!
P2 w

¡»2
á
P2 w

+»1
¡!
P2 z

¡
3

is a p a t h in T 0 lo n g e r t h a n P2, c o n t r a d ic t in g ( a 2 ) .
Case 2.2: N¡ ( »1 ) \ N + ( »2 ) = ;.

P u t
B1 = V ( P2 ) \ B ( T ) ; B2 = B ( T ) ¡ B1:

2 2 Spanning Trees with few Branch and End Vertices



Zh. Nikoghosyan 2 3

U s in g Cla im 1 , it is e a s y t o s e e t h a t

N¡ ( »1 ) \ B1 = N + ( »2 ) \ B1 = ;:

Ob s e r vin g a ls o t h a t N¡ ( »1 ) [ N + ( »2 ) µ V ( P2 ) , we g e t

jP2j ¸ jN¡ ( »1 ) j + jN + ( »2 ) j + jB1j

= d( »1 ) + d( »2 ) + jB1j ¸ ¾2 + jB1j ¸ n ¡ k + 1 + jB1j:
Th e n

n ¸ jP2j + jB2j + jf»3; :::; »f gj
¸ n ¡ k + 1 + jB1j + jB2j + f ¡ 2 = n ¡ k + b + f ¡ 1 ;

im p lyin g t h a t f · k ¡ b + 1 .

P r oof of T heor em 2: B y Th e o r e m 1 , G h a s a s p a n n in g t r e e T wit h jEnd( T ) j · k ¡ b + 1 ,
wh e r e b = jB ( T ) j. On t h e o t h e r h a n d , it is n o t h a r d t o s e e t h a t jEnd ( T ) j ¸ b + 2 , im p lyin g
t h a t b · ( k ¡ 1 ) = 2 .

P r oof of T heor em 3: B y Th e o r e m 1 a n d Th e o r e m 2 , G h a s a s p a n n in g t r e e T wit h
f = jEnd ( T ) j · k ¡ b + 1 a n d b · ( k ¡ 1 ) =2 , wh e r e b = jB ( T ) j. L e t d1; d2; :::; db b e t h e
d e g r e e s o f b r a n c h ve r t ic e s o f T . Ob s e r vin g t h a t

f =
bX

i=1

( di ¡ 2 ) + 2 ;

we g e t
bX

i=1

di · k + b ¡ 1 ·
3

2
( k ¡ 1 ) :

Refer ences

[1 ] J. A . B o n d y a n d U . S . R . Mu r t y, Graph Theory with Applications, Ma c m illa n , L o n d o n
a n d E ls e vie r , N e w Y o r k, 1 9 7 6 .

[2 ] G. A . D ir a c , \ S o m e t h e o r e m s o n a b s t r a c t g r a p h s " , P roc. L ondon, M ath. Soc., vo l.2 , p p .
6 9 -8 1 , 1 9 5 2 .

[3 ] O. Or e , \ A n o t e o n h a m ilt o n ia n c ir c u it s " , Am. M ath. M onth., vo l. 6 7 , p a g e 5 5 , 1 9 6 0 .
[4 ] V . Ch v¶a t a l a n d P . E r d }o s , \ A n o e o n h a m ilt o n ia n c ir c u it s " , D iscrete M ath., vo l. 2 , p p .

1 1 1 -1 1 3 , 1 9 7 2 .
[5 ] M. L a s V e r g n a s , \ S u r u n e p r o p r i¶ e t ¶ e d e s a r b r e s m a xim a u x d a n s u n g r a p h e " , 1 9 7 2 C.R .

A c a d .S c i.P a r is S ¶ e r . A , vo l. 2 7 2 , p p . 1 2 9 7 -1 3 0 0 , 1 9 7 1 .
[6 ] Zh .G. N iko g h o s ya n , \ Two t h e o r e m s o n s p a n n in g t r e e s " , Uchenie Zapiski E GU (Scien-

ti¯c Transactions of the Yerevan State University), S e r . Ma t e m a t ika , ( in R u s s ia n ) , n o .
3 , p p . 3 { 6 , 1 9 7 6 .

[7 ] H . B r o e r s m a a n d H . Tu in s t r a , \ In d e p e n d e n c e t r e e s a n d H a m ilt o n c yc le s " , J . Graph
Theory, vo l. 2 9 , p p . 2 2 7 -2 3 7 , 1 9 9 8 .

[8 ] S . W in , \ On a c o n je c t u r e o f L a s V e r g n a s c o n c e r n in g c e r t a in s p a n n in g t r e e s in g r a p h s " ,
R esultate M ath., vo l. 2 , p p . 2 1 5 -2 2 4 , 1 9 7 9 .



[9 ] L . Ga r g a n o , P . H e ll, L . S t a c h o a n d U . V a c c a r o , \ S p a n n in g t r e e s wit h b o u n d e d n u m b e r
o f b r a n c h ve r t ic e s " , L ecture notes in Comput. Sci., vo l. 2 3 8 0 , p p . 3 5 5 -3 6 5 , 2 0 0 2 .

[1 0 ] E . Fla n d r in , T. K a is e r , R . K u · z e l, H . L i a n d Z. R yj¶a · c e k, \ N e ig h b o r h o o d u n io n s a n d
e xt r e m a l s p a n n in g t r e e s " , D iscrete M ath., vo l. 3 0 8 , p p . 2 3 4 3 -2 3 5 0 , 2 0 0 8 .

[1 1 ] H . Ma t s u d a , K . Oz e ki a n d T. Y a m a s h it a , \ S p a n n in g t r e e s wit h a b o u n d e d n u m b e r o f
b r a n c h ve r t ic e s in a c la w-fr e e g r a p h " , Graphs and Combin. vo l. 3 0 , p p . 4 2 9 -4 3 7 , 2 0 1 4 .

[1 2 ] Zh .N iko g h o s ya n , \ On s p a n n in g t r e e p r o b le m s a r is in g in o p t ic a l a n d t e r m in a l n e t wo r ks " ,
CSIT Conference 2015, Y e r e va n , A r m e n ia , S e p t e m b e r 2 8 - Oc t o b e r 2 , p p . 9 4 -9 5 , 2 0 1 5 .

[1 3 ] A . S a it o a n d K . S a n o , \ S p a n n in g t r e e s h o m e o m o r p h ic t o a s m a ll t r e e " , D iscrete M ath.,
vo l. 3 3 9 , p p . 6 7 7 -6 8 1 , 2 0 1 6 .

Submitted 01.07.2016, accepted 28.10.2016.

ÎÙ³Ëù³ÛÇÝ Í³é»ñ ùÇã ×ÛáõÕ³ÛÇÝ ¨ ϳËí³Í ·³·³ÃÝ»ñáí

Ä. ÜÇÏáÕáëÛ³Ý

²Ù÷á÷áõÙ

G ·ñ³ýÇ Ñ³Ù³ñ ¾2-áí Ý߳ݳÏíáõÙ ¿ G-Ç áã ѳñ¨³Ý ·³·³ÃÝ»ñÇ ³ëïÇ׳ÝÝ»ñÇ
Ýí³½³·áõÛÝ ·áõÙ³ñÁ: ̳éÇ Ù»Ï ³ëïÇ×³Ý áõÝ»óáÕ ·³·³ÃÁ ÏáãíáõÙ ¿ ϳËí³Í ·³·³Ã,
ÇëÏ ³éÝí³½Ý »ñ»ù ³ëïÇ×³Ý áõÝ»óáÕ ·³·³ÃÁ` ×ÛáõÕ³ÛÇÝ ·³·³Ã: ²ß˳ï³ÝùáõÙ
¹Çï³ñÏíáõÙ »Ý ÙdzÛÝ ( ¤ ) n ·³·³Ã³ÝÇ Ï³å³Ïóí³Í ·ñ³ýÝ»ñ, áñáÝù µ³í³ñ³ñáõÙ
»Ý ¾2 ¸ n ¡ k + 1 å³ÛÙ³ÝÇÝ ÇÝã-áñ ÙÇ k µÝ³Ï³Ý ÃíÇ Ñ³Ù³ñ: 1976-ÇÝ ³å³óáõóí»É
¿ (Ñ»ÕÇݳÏÇ ÏáÕÙÇó), áñ ( ¤ ) -ÇÝ µ³í³ñ³ñáÕ Ï³Ù³Û³Ï³Ý ·ñ³ý áõÝÇ ³Ù»Ý³ß³ïÁ
k ϳËí³Í ·³·³Ã áõÝ»óáÕ ÏÙ³Ëù³ÛÇÝ Í³é: Ü»ñϳ ³ß˳ï³ÝùáõÙ Ý³Ë óáõÛó ¿
ïñíáõÙ, áñ ( ¤ ) -ÇÝ µ³í³ñ³ñáÕ Ï³Ù³Û³Ï³Ý ·ñ³ý áõÝÇ ÏÙ³Ëù³ÛÇÝ Í³é, áñÇ Ï³Ëí³Í ¨
×ÛáõÕ³ÛÇÝ ·³·³ÃÝ»ñÇ ÁݹѳÝáõñ ù³Ý³ÏÁ ãÇ ·»ñ³½³ÝóáõÙ ( k+1 ) -Á: ºñÏñáñ¹ ³ñ¹ÛáõÝùÁ
åݹáõÙ ¿, áñ ( ¤ ) -ÇÝ µ³í³ñ³ñáÕ Ï³Ù³Û³Ï³Ý ·ñ³ý áõÝÇ ÏÙ³Ëù³ÛÇÝ Í³é ³Ù»Ý³ß³ïÁ
1
2
( k¡ 1 ) ×ÛáõÕ³ÛÇÝ ·³·³ÃÝ»ñáí: Àëï »ññáñ¹ ³ñ¹ÛáõÝùÇ, ( ¤ ) -ÇÝ µ³í³ñ³ñáÕ Ï³Ù³Û³Ï³Ý

·ñ³ý áõÝÇ ÏÙ³Ëù³ÛÇÝ Í³é, áñÇ ×ÛáõÕ³ÛÇÝ ·³·³ÃÝ»ñÇ ³ëïÇ׳ÝÝ»ñÇ ·áõÙ³ñÁ ãÇ
·»ñ³½³ÝóáõÙ 3

2
( k ¡ 1 ) -Á: ´áÉáñ »ñ»ù ·Ý³Ñ³ï³Ï³ÝÝ»ñÁ ѳë³Ý»ÉÇ »Ý:

Êàðêàñû ñ ìåíüøèì ÷èñëîì âèñÿ÷èõ è Br-âåðøèí
Æ. Íèêîãîñÿí

Àííîòàöèÿ

Äëÿ ãðàôà G ÷åðåç ¾2 îáîçíà÷àåòñÿ ìèíèìàëüíàÿ ñóììà ñòåïåíåé äâóõ
íåñìåæíûõ âåðøèí. Âåðøèíà â äåðåâå íàçûâàåòñÿ âèñÿ÷åé, åñëè èìååò ñòåïåíü
1; è íàçûâàåòñÿ Br-âåðøèíîé, åñëè èìååò ñòåïåíü ïî ìåíüøåé ìåðå 3. Â ðàáîòå
ðàññìàòðèâàþòñÿ òîëüêî ( ¤ ) n-âåðøèííûå ñâÿçíûå ãðàôû, óäîâëåòâîðÿþùèå
óñëîâèþ ¾2 ¸ n ¡ k + 1 äëÿ íåêîòîðîãî íàòóðàëüíîãî ÷èñëà k.  1976 ãîäó

2 4 Spanning Trees with few Branch and End Vertices



Zh. Nikoghosyan 2 5

áûëà äîêàçàíà (àâòîðîì), ÷òî ïðîèçâîëüíûé ãðàô óäîâëåòâîðÿþùèé óñëîâèþ
( ¤ ) , èìååò êàðêàñ ñ íå áîëåå ÷åì k âèñÿ÷èìè âåðøèíàìè.  íàñòîÿùåé ðàáîòå
äîêàçûâàåòñÿ, ÷òî âñÿêèé ãðàô óäîâëåòâîðÿþùèé óñëîâèþ ( ¤ ) , èìååò êàðêàñ,
ãäå îáùåå ÷èñëî âèñÿ÷èõ è Br-âåðøèí íå ïðåâîñõîäèò k + 1 . Âòîðîé ðåçóëüòàò
óòâåðæäàåò, ÷òî âñÿêèé ãðàô, óäîâëåòâîðÿþùèé óñëîâèþ ( ¤ ) , èìååò êàðêàñ, ãäå
÷èñëî Br-âåðøèí íå ïðåâîñõîäèò 1

2
( k ¡ 1 ) . Òðåòèé ðåçóëüòàò óòâåðæäàåò, ÷òî

âñÿêèé ãðàô, óäîâëåòâîðÿþùèé óñëîâèþ ( ¤ ) , èìååò êàðêàñ, ãäå ñóììà ñòåïåíåé
Br-âåðøèí íå ïðåâîñõîäèò 3

2
( k ¡ 1 ) . Âñå òðè îöåíêè äîñòèãàåìû.


	02.pdf (p.1-7)
	Zhora_Nikoghosyan_1.pdf (p.8)