D:\User\sbornik_38_pdf\26.DVI


Mathematical Problems of Computer Science 38, 66{67, 2012.

On a P r oper ty of the n-dimensional Cube

R a fa ye l K a m a lia n 1, A r p in e K h a c h a t r ya n 2

1 Institute for Informatics and Automation Problems,
National Academy of Sciences of the Republic of Armenia, 0014, Armenia,

email: rrkamalian@yahoo.com
2 Ijevan Branch of Yerevan State University, 4001, Armenia,

email: khachatryanarpine@gmail.com

W e s h o w t h a t in a n y s u b s e t o f ve r t ic e s o f t h e n-d im e n s io n a l c u b e wh ic h c o n t a in s a t le a s t
2 n¡1 +1 ve r t ic e s ( n ¸ 4 ) , t h e r e a r e fo u r ve r t ic e s t h a t in d u c e a c la w, o r t h e r e a r e e ig h t ve r t ic e s
t h a t in d u c e t h e c yc le o f le n g t h e ig h t .

W e c o n s id e r ¯ n it e g r a p h s G = ( V; E ) wit h ve r t e x s e t V a n d e d g e s e t E. Th e g r a p h s
c o n t a in n o m u lt ip le e d g e s o r lo o p s . Th e n-d im e n s io n a l c u b e is d e n o t e d b y Qn, a n d a c la w is
t h e c o m p le t e b ip a r t it e g r a p h K1;3. Mo r e o ve r , t h e ve r t e x o f a d e g r e e t h r e e in a c la w is c a lle d
a c la w-c e n t e r . N o n -d e ¯ n e d t e r m s a n d c o n c e p t s c a n b e fo u n d in [1 ].

Th e m a in r e s u lt o f t h e p a p e r is t h e fo llo win g :

T heor em 1. L et n ¸ 4 and let V 0 µ V ( Qn ) . If jV 0j ¸ 2 n¡1 + 1 , then at least one of the
following two conditions holds:

(a) there are four vertices in V 0 that induce a claw;

(b) there are eight vertices in V 0 that induce a simple cycle.

P r oof. Ou r p r o o f is b y in d u c t io n o n n. S u p p o s e t h a t n = 4 . Cle a r ly, wit h o u t lo s s o f
g e n e r a lit y, we c a n a s s u m e t h a t jV 0j = 9 . Co n s id e r t h e fo llo win g p a r t it io n o f t h e ve r t ic e s o f
Q4:

V1 = f( 0 ; ®2; ®3; ®4 ) : ®i 2 f0 ; 1 g; 2 · i · 4 g; V2 = f( 1 ; ®2; ®3; ®4 ) : ®i 2 f0 ; 1 g; 2 · i · 4 g:

Cle a r ly, t h e s u b g r a p h s o f Q4 in d u c e d b y V1 a n d V2 a r e is o m o r p h ic t o Q3. D e ¯ n e :

V 01 = V1 \ V 0; V 02 = V2 \ V 0:

W e s h a ll a s s u m e t h a t jV 01j ¸ jV 02j. W e s h a ll c o m p le t e t h e p r o o f o f t h e b a s e o f in d u c t io n b y
c o n s id e r in g t h e fo llo win g c a s e s :

Ca s e 1 : jV 01j = 8 a n d jV 02j = 1 . Cle a r ly, a n y ve r t e x fr o m V 01 is a c la w-c e n t e r .
Ca s e 2 : jV 01j = 7 a n d jV 02j = 2 . It is n o t h a r d t o s e e t h a t V 01 c o n t a in s a c la w-c e n t e r .
Ca s e 3 : jV 01j = 6 a n d jV 02j = 3 . A g a in , it is a m a t t e r o f d ir e c t ve r ī c a t io n t h a t V 0 c o n t a in s

a c la w-c e n t e r .
Ca s e 4 : jV 01j = 5 a n d jV 02j = 4 . Co n s id e r t h e s u b g r a p h G1 o f Q4 in d u c e d b y V 01 . Cle a r ly, if

G1 c o n t a in s a ve r t e x o f a d e g r e e t h r e e , t h e n t h is ve r t e x is a c la w-c e n t e r . Th e r e fo r e , wit h o u t

6 6



R. Kamalian, A. Khachatryan 6 7

lo s s o f g e n e r a lit y, we c a n a s s u m e t h a t a n y ve r t e x in G1 h a s a d e g r e e a t m o s t t wo . It is n o t
h a r d t o s e e t h a t t h is im p lie s t h a t G1 c o n t a in s n o is o la t e d ve r t e x. Mo r e o ve r , s in c e jV 01j = 5 ,
we c a n c o n c lu d e t h a t G1 is a c o n n e c t e d g r a p h , a n d , c o n s e qu e n t ly, it is t h e p a t h o f le n g t h
fo u r .

N o w, le t a1; a2; a3 b e t h e in t e r n a l ve r t ic e s o f G1, a n d le t b1; b2 b e t h e e n d -ve r t ic e s o f G1.
Cle a r ly, we c a n a s s u m e t h a t n e it h e r o f a1; a2; a3 h a s a n e ig h b o u r in V

0
2 . S in c e jV2j = 8 a n d

jV 02j = 4 , we h a ve t h a t t h e r e a r e ¯ ve p o s s ib ilit ie s fo r V 02 . W e in vit e t h e r e a d e r t o c h e c k t h a t
in fo u r o f t h e s e c a s e s o n e c a n ¯ n d a c la w-c e n t e r in V 02 , a n d in t h e ¯ n a l c a s e V

0 h a s a ve r t e x
z s u c h t h a t V 0nfzg in d u c e s a s im p le c yc le .

N o w, le t u s a s s u m e t h a t t h e s t a t e m e n t is t r u e fo r n ¡ 1 , a n d a s u b s e t V 0 o f t h e ve r t ic e s
o f Qn s a t is ¯ e s t h e in e qu a lit y jV 0j ¸ 2 n¡1 + 1 . Co n s id e r t h e fo llo win g p a r t it io n o f t h e ve r t ic e s
o f Qn:

V1 = f( 0 ; ®2; :::; ®n ) : ®i 2 f0 ; 1 g; 2 · i · ng; V2 = f( 1 ; ®2; :::; ®n ) : ®i 2 f0 ; 1 g; 2 · i · ng:

Cle a r ly, t h e s u b g r a p h s o f Qn in d u c e d b y V1 a n d V2 a r e is o m o r p h ic t o Qn¡1. Mo r e o ve r , it is
n o t h a r d t o s e e t h a t a t le a s t o n e o f t h e fo llo win g t wo in e qu a lit ie s is t r u e : jV1 \ V 0j ¸ 2 n¡2 + 1
a n d jV2 \ V 0j ¸ 2 n¡2 + 1 . Th u s t h e p r o o f fo llo ws fr o m t h e in d u c t io n h yp o t h e s is .

Fo r t h e c a s e o f n = 3 we h a ve :

P r oposition 1. L et V 0 µ V ( Q3 ) and let jV 0j ¸ 6 . Then at least one of the following two
conditions holds:

² there are four vertices in V 0 that induce a claw;

² there are six vertices in V 0 that induce a simple cycle.

Acknowledgement. W e wo u ld like t o t h a n k Zh o r a N iko g h o s ya n a n d V a h a n Mkr t c h ya n fo r
t h e ir a t t e n t io n t o t h is wo r k.

R e fe r e n c e s

[1 ] W e s t D .B . Introduction to Graph Theory. P r e n t ic e -H a ll, N e w Je r s e y, 1 9 9 6 .