Zhora_26--31.DVI


Mathematical Problems of Computer Science 43, 26{31, 2015.

On k-E nded Spanning and Dominating T r ees

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

Institute for Informatics and Automation Problems of NAS RA

e-mail: zhora@ipia.sci.am

Abstract

A tree with at most k leaves is called a k-ended tree. Let tk be the order of a
largest k-ended tree in a graph. A tree T of a graph G is said to be dominating if
V (G ¡ T ) is an independent set of vertices. The minimum degree sum of any pair
(triple) of nonadjacent vertices in G will be denoted by ¾2 (¾3). The earliest result
concerning spanning trees with few leaves (by the author, 1976) states: (¤) if G is a
connected graph of order n with ¾2 ¸ n ¡ k + 1 for some positive integer k, then G has
a spanning k-ended tree. In this paper we show: (i) the connectivity condition in (¤)
can be removed; (ii) the condition ¾2 ¸ n ¡ k + 1 in (¤) can be relaxed by replacing
n with tk+1; (iii) if G is a connected graph with ¾3 ¸ tk+1 ¡ 2k + 4 for some integer
k ¸ 2, then G has a dominating k-ended tree. All results are sharp.

Keywords: Hamilton cycle, Hamilton path, Dominating cycle, Dominating path,
Longest path, k-ended tree.

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 in [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 ) , t h e
m in im u m d e g r e e 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. 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. 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.

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.
E a c h ve r t e x a n d e d g e in G c a n b e in t e r p r e t e d a s s im p le c yc le s o f o r d e r s 1 a n d 2 , r e s p e c t ive ly.
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. A c yc le C o f G is s a id t o b e d o m in a t in g if V ( G ¡ C ) is a n in d e p e n d e n t s e t o f
ve r t ic e s .

W e wr it e a c yc le 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. Fo r x 2 V ( Q) , we d e n o t e t h e s u c c e s s o r
a n d t h e p r e d e c e s s o r o f x o n

¡!
Q b y x+ a n d x¡, r e s p e c t ive ly.

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 ) . Fo r a p o s it ive in t e g e r k, a

¤G.G. Nicoghossian (up to 1997)

2 6

¤



Zh. Nikoghosyan 2 7

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 p a r t ic u la r , K2 is
H a m ilt o n ia n a n d a 1 -e n d e d t r e e . W e d e n o t e b y tk t h e o r d e r o f a la r g e s t k-e n d e d t r e e in G.
B y t h e d e ¯ n it io n , t1 is t h e o r d e r o f a lo n g e s t c yc le , a n d t2 is t h e o r d e r o f a lo n g e s t p a t h in
G.

Ou r s t a r t in g p o in t is t h e e a r lie s t s u ± c ie n t c o n d it io n fo r a g r a p h t o b e H a m ilt o n ia n d u e
t o D ir a c [2 ].

T heor em A ( [2 ]) : E very graph with ± ¸ n
2

is Hamiltonian.
In 1 9 6 0 , Or e [3 ] im p r o ve d Th e o r e m A b y r e p la c in g t h e m in im u m d e g r e e ± wit h t h e a r it h -

m e t ic m e a n 1
2
¾2 o f t wo s m a lle s t d e g r e e s a m o n g p a ir wis e n o n a d ja c e n t ve r t ic e s .

T heor em B ( [3 ]) : E very graph with ¾2 ¸ n is Hamiltonian.
Th e a n a lo g o f Th e o r e m B fo r H a m ilt o n p a t h s fo llo ws e a s ily.

T heor em C ( [3 ]) : E very graph with ¾2 ¸ n ¡ 1 has a Hamilton path.

In 1 9 7 1 , L a s V e r g n a s [4 ] 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 . A s a c o r o lla r y, t h is r e s u lt im p lie s
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 n d Th e o r e m C a s s p e c ia l c a s e s fo r k = 1 a n d k = 2 , r e s p e c t ive ly.

T heor em D ( [4 ], [5 ], [6 ]) : If G is 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 ]
a n d 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 [5 ]. Mo r e o ve r , t h e fu ll c h a r a c t e r iz a t io n
o f c o n n e c t e d g r a p h s wit h o u t s p a n n in g k-e n d e d t r e e s wa s g ive n in [7 ] wh e n ¾2 ¸ n ¡ k
in c lu d in g t h e we ll-kn o wn c h a r a c t e r iz a t io n o f c o n n e c t e d g r a p h s wit h o u t H a m ilt o n c yc le s wh e n
¾2 ¸ n ¡ 1 . Th is p a r t ic u la r r e s u lt wa s r e p r o ve d in 1 9 8 0 b y N a r a Ch ie [8 ].

Th e n e xt t wo r e s u lt s o n t h is s u b je c t a r e n o t in c lu d e d in t h e r e c e n t s u r ve y p a p e r [9 ]. W e
c a ll a g r a p h G h yp o -k-e n d e d if G h a s n o s p a n n in g k-e n d e d t r e e , b u t fo r a n y v 2 V ( G) , G ¡v
h a s a s p a n n in g k-e n d e d t r e e .

T heor em E ( [1 0 ]) : F or each k ¸ 3 , the minimum number of vertices (edges, faces, respec-
tively) of a simple 3-polytope without a spanning k-ended tree is 8 + 3 k ( 1 2 + 6 k, 6 + 3 k,
respectively).

T heor em F ( [1 1 ]) : F or each n ¸ 1 7 k and k ¸ 2 , except possible for n = 1 7 k + 1 , 1 7 k + 2 ,
1 7 k + 4 and 1 7 k + 7 , there exist hypo-k-ended graphs of order n.

In t h is p a p e r we p r o ve t h a t t h e c o n n e c t ivit y c o n d it io n in Th e o r e m D c a n b e r e m o ve d ,
a n d t h e c o n c lu s io n c a n b e s t r e n g t h e n e d .

T heor em 1: If G is a graph with ¾2 ¸ n ¡ k + 1 for some positive integer k, then G has a
spanning k-ended forest.

N e xt , we s h o w t h a t Th e o r e m D c a n b e im p r o ve d b y r e la xin g t h e c o n d it io n ¾2 ¸ n¡k + 1
t o ¾2 ¸ tk+1 ¡ k + 1 .



2 8 On k-Ended Spanning and Dominating Trees

T heor em 2: L et G be a connected graph with ¾2 ¸ tk+1 ¡ k + 1 for some positive integer k.
Then G has a spanning k-ended tree.

Th e g r a p h ( ± + k ) K1 + K± s h o ws t h a t t h e b o u n d tk+1 ¡ k + 1 in Th e o r e m 2 c a n n o t b e
r e la xe d t o tk ¡ k + 1 . Fin a lly, we g ive a d o m in a t in g a n a lo g o f Th e o r e m D .

T heor em 3: If G is a connected graph with ¾3 ¸ tk+1 ¡ 2 k + 4 for some integer k ¸ 2 , then
G has a dominating k-ended tree.

Th e g r a p h ( ± + k ¡ 1 ) K2 + K±¡1 s h o ws t h a t t h e b o u n d tk+1 ¡ 2 k + 4 in Th e o r e m 3 c a n n o t
b e r e la xe d t o tk ¡ 2 k + 4 .

Th e fo llo win g c o r o lla r y fo llo ws im m e d ia t e ly.

Cor ollar y 1: If G is a connected graph with ¾3 ¸ n ¡ 2 k + 4 for some integer k ¸ 2 , then
G has a dominating k-ended tree.

Th e g r a p h ( ± + k ¡ 1 ) K2 + K±¡1 s h o ws t h a t t h e b o u n d ¾3 ¸ tk+1 ¡ 2 k + 4 in Th e o r e m 3
c a n n o t b e r e la xe d t o ¾3 ¸ tk+1 ¡ 2 k + 3 .

2 . P r o o fs

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

¡!
P = x

¡!
P y b e a lo n g e s t p a t h in H1. If jP j ¸ n ¡ k + 2

t h e n jG ¡ P j = n ¡ jP j · k ¡ 2 , im p lyin g t h a t G h a s a s p a n n in g k-e n d e d fo r e s t . N o w
le t jP j · n ¡ k + 1 . S in c e P is e xt r e m e , we h a ve N ( x ) [ N ( y ) µ V ( P ) . R e c a llin g a ls o
t h a t ¾2 ¸ n ¡ k + 1 , we h a ve ( b y s t a n d a r d a r g u m e n t s ) N ( x) \ N + ( y ) 6= ;, im p lyin g t h a t
G[V ( P ) ] is H a m ilt o n ia n . Fu r t h e r , if jV ( P ) j < jV ( H1 ) j t h e n we c a n fo r m a p a t h lo n g e r t h a n
P , c o n t r a d ic t in g t h e m a xim a lit y o f P . H e n c e , jV ( P ) j = jV ( H1 ) j, t h a t is H1 is H a m ilt o n ia n
a s we ll. B y a s im ila r a r g u m e n t , Hi is H a m ilt o n ia n fo r e a c h i 2 f 1 ; :::; mg a n d t h e r e fo r e , h a s
a s p a n n in g t r e e wit h e xa c t ly o n e le a f. Th u s , G h a s a s p a n n in g fo r e s t wit h e xa c t ly m le a ve s .

It r e m a in s t o s h o w t h a t m · k. If m = 1 t h e n G h a s a s p a n n in g 1 -e n d e d t r e e a n d
t h e r e fo r e , h a s a s p a n n in g k-e n d e d t r e e . L e t m ¸ 2 a n d le t xi 2 V ( Hi ) ( i = 1 ; :::; m ) . Cle a r ly,
fx1; x2; :::; xmg is a n in d e p e n d e n t s e t o f ve r t ic e s . S in c e d( xi ) · jV ( Hi ) j ¡ 1 , we h a ve

¾2 · ¾m ·
mX

i=1

d( xi ) ·
mX

i=1

jV ( Hi ) j ¡ m = n ¡ m:

On t h e o t h e r h a n d , b y t h e h yp o t h e s is , ¾2 ¸ n ¡ k + 1 , im p lyin g t h a t m · k ¡ 1 .

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

Case 1: G is Hamiltonian.
B y t h e d e ¯ n it io n , G h a s a s p a n n in g 1 -e n d e d t r e e T1. S in c e k ¸ 1 , T1 is a s p a n n in g

k-e n d e d t r e e .

Case 2: G is not Hamiltonian.
L e t T2 b e a lo n g e s t p a t h in G.

Case 2.1: ¾2 ¸ t2.



Zh. Nikoghosyan 2 9

B y s t a n d a r d a r g u m e n t s , G[V ( T2 ) ] is H a m ilt o n ia n . If t2 < n t h e n r e c a llin g t h a t G is c o n -
n e c t e d , we c a n fo r m a p a t h lo n g e r t h a n T2, c o n t r a d ic t in g t h e m a xim a lit y o f T2. Ot h e r wis e
G is H a m ilt o n ia n a n d we c a n a r g u e a s in Ca s e 1 .

Case 2.2: ¾2 · t2 ¡ 1 .
If k = 1 t h e n b y t h e h yp o t h e s is , ¾2 ¸ t2, im p lyin g t h a t G is H a m ilt o n ia n a n d we c a n

a r g u e a s in Ca s e 1 . L e t k ¸ 2 . E xt e n d T2 t o a k-e n d e d t r e e Tk a n d a s s u m e t h a t Tk is a s
la r g e a s p o s s ib le . If Tk is a s p a n n in g t r e e t h e n we a r e d o n e . L e t Tk b e n o t s p a n n in g . Th e n
jEnd( Tk ) j = k s in c e o t h e r wis e we c a n fo r m a n e w k-e n d e d t r e e la r g e r t h a n Tk, c o n t r a d ic t in g
t h e m a xim a lit y o f Tk. N o w e xt e n d Tk t o a la r g e s t ( k + 1 ) -e n d e d t r e e Tk+1. R e c a llin g t h a t
Tk is a la r g e s t k-e n d e d t r e e , we g e t jEnd( Tk+1 ) j = k + 1 a n d t h e r e fo r e ,

tk+1 ¸ jTk+1j = jT2j + jTk+1 ¡ T2j:

Ob s e r vin g t h a t jT2j = t2 a n d jTk+1 ¡ T2j ¸ jEnd( Tk+1 ) j ¡ 2 = k ¡ 1 , we g e t

tk+1 ¸ t2 + k ¡ 1 ¸ ¾2 + k;

c o n t r a d ic t in g t h e h yp o t h e s is .

P r oof of T heor em 3: L e t G b e a c o n n e c t e d g r a p h wit h ¾3 ¸ tk+1 ¡ 2 k + 4 fo r s o m e
in t e g e r k ¸ 2 , a n d le t ¡!T2 = x

¡!
T2 y b e a lo n g e s t p a t h in G. If T2 is a d o m in a t in g p a t h t h e n

we a r e d o n e . Ot h e r wis e , s in c e G is c o n n e c t e d , we c a n c h o o s e a p a t h
¡!
Q = w

¡!
Q z s u c h t h a t

V ( T2 \ Q ) = fwg a n d jQj ¸ 3 . A s s u m e t h a t jQj is a s la r g e a s p o s s ib le . P u t T3 = T2 [ Q.
S in c e T2 a n d Q a r e e xt r e m e , we h a ve N ( x) [ N ( y ) µ V ( T2 ) a n d N ( z ) µ V ( T3 ) . L e t w+
b e t h e s u c c e s s o r o f w o n T2. If xy 2 E t h e n T3 + xy ¡ w+w is a p a t h lo n g e r t h a n T2, a
c o n t r a d ic t io n . L e t xy 62 E. B y t h e s a m e r e a s o n , we h a ve xz; yz 62 E. Th u s , fx; y; zg is a n
in d e p e n d e n t s e t o f ve r t ic e s .

Claim 1: N¡ ( x ) \ N + ( y ) \ N ( z ) = ;.
P r oof: A s s u m e t h e c o n t r a r y.

Case 1: v 2 N¡ ( x) \ N + ( y ) .
If v = w t h e n xv+ 2 E a n d T3 + xv+ ¡ vv+ is a p a t h lo n g e r t h a n T2, a c o n t r a d ic t io n .

S u p p o s e wit h o u t lo s s o f g e n e r a lit y t h a t v 2 V ( w+¡!T2 y ) . If v = w+ t h e n T3 + xv+ ¡ wv ¡ vv+
is a p a t h lo n g e r t h a n T2, a c o n t r a d ic t io n . Fin a lly, if v 2 V ( w+2

¡!
T2 y ) t h e n

T3 + xv
+ + yv¡ ¡ vv¡ ¡ vv+ ¡ ww+

is a p a t h lo n g e r t h a n T2, a c o n t r a d ic t io n .

Case 2: v 2 N¡ ( x) \ N ( z ) .
If v 2 V ( x¡!T2 w¡2 ) t h e n

T2 + xv
+ + zv ¡ vv+ ¡ ww¡

is a p a t h lo n g e r t h a n T2, a c o n t r a d ic t io n . N e xt , if v = w
¡ t h e n T2 + zw

¡ ¡ ww¡ is a p a t h
lo n g e r t h a n T2, a c o n t r a d ic t io n . Fu r t h e r , if v = w t h e n T2 + xv

+ ¡ ww+ is a p a t h lo n g e r
t h a n T2, a c o n t r a d ic t io n . Fin a lly, if v 2 V ( w+

¡!
T2 y ) t h e n

T2 + xv
+ + zv ¡ ww+ ¡ vv+



3 0 On k-Ended Spanning and Dominating Trees

is a p a t h lo n g e r t h a n T2, a c o n t r a d ic t io n .

Case 3: v 2 N + ( y ) \ N ( z ) .
B y a s ym m e t r ic a r g u m e n t , we c a n a r g u e a s in Ca s e 2 . Cla im 1 is p r o ve d .

B y Cla im 1 ,
t3 ¸ jT3j ¸ jN¡ ( x ) j + jN + ( y ) j + jN ( z ) j + jfzgj

= d( x ) + d( y ) + d( z ) + 1 ¸ ¾3 + 1 : ( 1 )
If k = 2 t h e n b y t h e h yp o t h e s is , ¾3 ¸ tk+1 ¡ 2 k + 4 = t3, c o n t r a d ic t in g ( 1 ) . L e t k ¸ 3 . If T3
is a d o m in a t in g 3 -e n d e d t r e e t h e n c le a r ly we a r e d o n e . Ot h e r wis e G ¡ T3 c o n t a in s a n e d g e
a n d we c a n e xt e n d T3 t o a la r g e s t 4 -e n d e d t r e e T4 wit h jT4j ¸ jT3j + 2 . If k = 3 , t h e n b y t h e
h yp o t h e s is , ¾3 ¸ tk+1¡ 2 k+4 = t4¡ 2 . On t h e o t h e r h a n d , b y ( 1 ) , t4 ¸ jT4j ¸ jT3j+2 ¸ ¾3 +3 ,
a c o n t r a d ic t io n . H e n c e , k ¸ 4 . If T4 is d o m in a t in g , t h e n we a r e d o n e . Ot h e r wis e we c a n
e xt e n d T4 t o a la r g e s t 5 -e n d e d t r e e T5 wit h jT5j ¸ jT4j + 2 ¸ jT3j + 4 . Th is p r o c e d u r e m a y
b e r e p e a t e d u n t il a d o m in a t in g ( r + 1 ) -e n d e d t r e e Tr+1 is fo u n d . If r + 1 · k t h e n we a r e
d o n e . L e t r ¸ k. Th e n

tk+1 ¸ jTk+1j ¸ jT3j + 2 ( k ¡ 2 )
¸ ¾3 + 2 k ¡ 3 ¸ tk+1 + 1 ;

a c o n t r a d ic t io n . Th e p r o o f is c o m p le t e .

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 roceedings of the L ondon M athe-
matical Society, vo l. 2 , n o . 3 , 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 " , American M athematical M onthly, vo l. 6 7 , p .
5 5 , 1 9 6 0 .

[4 ] 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 " , Comptes
R endus de l'Acad¶emie des sciences P aris S¶er. A 272, p p . 1 2 9 7 -1 3 0 0 , 1 9 7 1 .

[5 ] 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 , n o . 4 , p p . 2 2 7 -2 3 7 , 1 9 9 8 .

[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 StatUniversity), 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 ] Zh . G. N iko g h o s ya n , \ Th e o r e m s o n H a m ilt o n c yc le s a n d s p a n n in g t r e e s " ,M olodoi nauch-
nii rabotnik, S e r . N a t u r a l S c ie n c e s , Y e r e va n S t a t e U n ive r s it y, ( in R u s s ia n ) , vo l. 2 4 , n o .
2 , p p . 1 5 -2 0 , 1 9 7 6 .

[8 ] N . Ch ie , \ On s u ± c ie n t c o n d it io n s fo r a g r a p h t o b e h a m ilt o n ia n " , Natural Science,
Oc h a n o m iz u U n ive r s it y, vo l. 3 1 , n o . 2 , p p . 7 5 -8 0 , 1 9 8 0 .

[9 ] 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 - A s u r ve y" , Graphs Combinatorics, vo l.
2 7 , n o . 1 , p p . 1 -2 6 , 2 0 1 1 .

[1 0 ] Zh . G. N iko g h o s ya n , \ S p a n n in g t r e e s o n 3 -p o lyt o p e s " , K ibernetika, ( in R u s s ia n ) , n o . 4 ,
p p . 3 5 -4 2 , 1 9 8 2 .



Zh. Nikoghosyan 3 1

[1 1 ] Zh . G. N iko g h o s ya n , \ n -s p a n n in g a n d h yp o -n -s p a n n in g g r a p h s " , Tanulmanyok, B u -
d a p e s t , ( in R u s s ia n ) , n o . 1 3 5 , p p . 1 5 3 -1 6 7 , 1 9 8 2 .

Submitted 06.11.2014, accepted 28.01.2015.

¶ñ³ýáõÙ k-³í³ñï ÏÙ³Ëù³ÛÇÝ ¨ ¹áÙÇݳÝï ͳé»ñÇ Ù³ëÇÝ

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

²Ù÷á÷áõÙ

̳éÇ Ù»Ï ³ëïÇ×³Ý áõÝ»óáÕ ·³·³ÃÁ ÏáãíáõÙ ¿ ï»ñ¨: ¶ñ³ýáõÙ k-Çó áã ³í»É
ï»ñ¨ áõÝ»óáÕ Í³éÁ ÏáãíáõÙ ¿ k-³í³ñï ͳé: ¶ñ³ýáõÙ ³Ù»Ý³Ù»Í k-³í³ñï ͳéÇ
·³·³ÃÝ»ñÇ ù³Ý³ÏÁ Ý߳ݳÏíáõÙ ¿ tk-áí: G ·ñ³ýÇ T ͳéÁ ÏáãíáõÙ ¿ ¹áÙÇݳÝï,
»Ã» V(G-T)-Ý ·³·³ÃÝ»ñÇ ³ÝÏ³Ë µ³½ÙáõÃÛáõÝ ¿: ¸Çóáõù, ¾2-Á (¾3 -Á) ·ñ³ýáõÙ áã
ѳñ¨³Ý ½áõÛ· (»éÛ³Ï) ·³·³ÃÝ»ñÇ ³ëïÇ׳ÝÝ»ñÇ Ñݳñ³íáñ ³Ù»Ý³÷áùñ ·áõÙ³ñÝ ¿:
øÇã ï»ñ¨Ý»ñáí ÏÙ³Ëù³ÛÇÝ Í³é»ñÇÝ ³éÝãíáÕ ³Ù»Ý³í³Õ ³ñ¹ÛáõÝùÁ (áñÁ ëï³óí»É ¿
Ñ»ÕÇݳÏÇ ÏáÕÙÇó 1976-ÇÝ) åݹáõÙ ¿` ( ¤) »Ã» n ·³·³Ã³ÝÇ G ϳå³Ïóí³Í ·ñ³ýÁ
µ³í³ñ³ñáõÙ ¿ ¾2 ¸ n ¡ k + 1 å³ÛÙ³ÝÇÝ ÇÝã- áñ ÙÇ k ¹ñ³Ï³Ý ³ÙµáÕç ÃíÇ Ñ³Ù³ñ,
³å³ G-Ý áõÝÇ k-³í³ñï ÏÙ³Ëù³ÛÇÝ Í³é: Ü»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ ¿,
áñ ( ¤ ) -áõ٠ϳå³Ïóí³ÍáõÃÛ³Ý å³ÛÙ³ÝÁ ϳñ»ÉÇ ¿ µ³ó ÃáÕÝ»É: ºñÏñáñ¹ ³ñ¹ÛáõÝùÁ
( ¤ ) -Ç áõŻճóáõÙÝ ¿` n-Á ÷á˳ñÇÝ»Éáí tk+1-áí (ÁݹѳÝñ³å»ë tk+1 · n): ºññáñ¹
³ñ¹ÛáõÝùÁ »ñÏñáñ¹Ç ï³ñµ»ñ³ÏÝ ¿` ¹áÙÇݳÝï k-³í³ñï ͳé»ñÇ Ñ³Ù³ñ: ´»ñí³Í
µáÉáñ ³ñ¹ÛáõÝùÝ»ñÁ »Ýóϳ ã»Ý µ³ñ»É³íÙ³Ý:

Î k-âèñÿ÷èõ îñòîâíûõ è äîìèíàíòíûõ äåðåâüÿõ
Æ. Íèêîãîñÿí

Àííîòàöèÿ

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