[0, k i] 1^m -factorizations orthogonal to a subgraph

Applied Mathenmtie~ and Mech:mics (English Edition, Vol 22, No 5, May 2001)

Published by Shanghai University, Shanghai, China

Article ID: 0253-4827(2001)05-0593-04

[ 0 , ki ] ~n -FACTORIZATIONS ORTHOGONAL TO A SUBGRAPH * MA Run-nian ( Z ~ ) I ,

XU Jill (],~

~)1,

GAO Hang-shan ( ~ L L ] ) ~ -

(1 .Electronic Engineering Research Institute, Xidian University, Xi' an 710071, P R China; 2. Department of Engineering Mechanics, Northwestern Polyteclmical University, X_i'an 710072, P R China) (Communicated by ZHANG Ru-qing) AbsUmct : Let G be a graph, k 1 , " ' , k,, be positive integers. If the edges of graph G can be decomposed into some edge disjoint [ O, k I I-factor I t , " ' , [ 0, k~ ]-factor F,, , then we can say F = { F t ,..., F= } , is a [ O , ki ] ~-factorization of G . lf H is a subgraph with m edges in graphGand I E ( H ) f~ E(Fi) I = l f o r a l l l < i <. m , t h e n w e c a n c a l l t h a t F i s o r thogonal toll i lt is proved that if G is a [0,k t + "" + km- m+ 1J-graph, His a subgraph with m edges in G , then graph G has a [ O,k i ]~-factorizaffon orthogonal to H .

Key words: graph; factor; factorization| orthogonal factofization CLC number: O157.5 Document cede: A

1

Basic Definitions and Notations

We only deal with finite undirected simple graphs. Let G be a graph with vertex set V(G) and edge s e t E ( G ) . For each x E V ( G ) , we denote the degree o f x in G b y d e ( x ) . L e t g , f b e two integer-valued functions defined on V(G) such that g ( x ) ~< f ( x ) for all x E V ( G ) . A ( g , f ) - factor of G is a spanning subgraph F of G such that g ( x ) <~ dF ( x ) < f ( x ) for all x E V(G) and we call that F is a ( g , f ) - factor of G. If g ( x ) ~< dc ( x ) ~< f ( x ) for all x E V ( G ) , then we that G is a ( g , f ) - g r a p h . In particular, f i g ( x ) = a , f ( x ) --- b for all x E V ( G ) , then we call a ( g , f ) - factor as an [ a , b ]-factor and a ( g , f ) - g r a p h as an [ a , b l - g r a p h . Let k 1 , ' " , km be positive integers. If the edges of graph G can be decomposed into some edge disjoint [ 0 , k l ]-factor F1 , " ' , [0, km ]-factor F , ,

then we say ~" = { F1 , " ' , Fm } is a [0,

ki ] ~ - factorization of G and G itself is said to be [ 0, ki ] ~n_factorable. Let H be a subgraph of G with m edges and ~" = { F1 , ' " , F,, } be a [0, ki ]~" - factorization ofG. Ifl E(H)

~ E(Fi)

is, ~" is an orthogonal [ 0, For aUS C V ( G ) ,

I = 1 for a l l l ~< i ~< m, then we call that ~" is orthogonal to H, that ki

] ~n. faetorization of G.

setf(S)

= ~J(x),

de(S)

xES

= ~dc(x),

in particular, f ( ~ )

zE-Y

Received date: 1999-11-05; Revised date: 2000-12-13 Foundation item: the National Natural Science Foundation of China (69971018) Biography: MA Run-nian (1963 - ), Associate Professor, Doctor 593

=

594

MA Run-nian, XU Jin and GA0 Hang-shah = 0. For all set S , T C V ( G ) ,

de(C)

S N T = gl, we denote the edge set of joining S and

T by Ec ( S , T) and e c ( S , T) = I Ec ( S , T) I 9 Other definitions and notations can be found in [1,2,3]. Refs. [ 4 , 5 , 6 ] mainly study orthogonal [ 0, ki ] ~ - factorization of graph and this paper is an extension of it.

2

Main Results L p m m a 1 [3]

Let G be a graph, g a n d f b e two integer-valued functions defined on V ( G )

such that0 ~< g ( x )

< f(x)

for all x E V ( G ) . Then G has a ( g , f ) - f a e t o r

edge e if and only if da = da( T) - e c ( S , T) - g ( T ) V(C),

containing given

+ f ( S ) ~ e ( S , T) for all set S , T C_

S N T = 0 , where !

e(S,T)

ife

=

= uv and u , v E S;

ifthereis acomponent CofG

- ( S U T) such t h a t e E E c ( S ,

V(C);

otherwise. L e m m a 2 [4'5'6]

Let kl ,... , k . be positive integers. If G is a [ O, kl , + "" + k~ - m +

1J-graph and H is a subgraph in G with m edges but without isolated vertex sueh that I V ( H ) I~>1 E ( H )

I = m ( f o r example a tree, forest and cycle with m edges, denoted

respectively by m- tree, m- forest and m- c y c l e ) , then g r a p h G has a [ O, ki ] ~n_ factorization orthogonal to H . Theorem

Let kl , " ' , k .

be positive integers. If G is a [ 0 , k l + "'" +km - m + 1]-graph and

HIS a subgraph in G with m edges, then graph Ghas a [0, kj ]~'- factorizafion orthogonal to H. Proof

By induction on m , obviously, the theorem is true if m = 1. When m = 2 , by

Lemma 2, the theorem is also true. Now we assume m >I 3 and E ( H ) = { el , ' " , e,, } as follows. Obviously, we may assume each k~ ~> 2(1 ~< i ~< m ) . Otherwise, without loss of generality, we assume k., = 1, then, de(x)

<<. kl + "'" + k~ - m + 1 = kl + "'" + k . _ l - ( m - 1) + 1. Obviously, e,, is a [0,

k,~]-factor containing edge e.,, G - e., is a [ 0 , k 1 + . " + kin-1 - ( m - 1) + 1 ]-graph and W = H - e,, is a subgraph with m - 1 edges in G - e . . By induetion hypothesis, G - e,, has a [0, ki ] f' - 1 _ factorization orthogonal to H ' .

Hence,

graph G has a [ O, ki ] ~ - 1 _ factorization

orthogonal to H and we may assume each k i >>. 2(1 ~< i ~< m ) as follows. If H satisfies I V ( H ) I >~ I E ( H ) I = m , then, by L e m m a 2 , the conclusion holds. Hence, we suppose that H satisfies I V ( H ) I < I E ( H ) H , one of which we I_~tG' = G {el,'",e,~-l}. dtr(x),

might as

{el,"',e._1},H' Vx

and dH,(X)

max{0,da(x)

well suppose is e m

~V(H'),

dc,(x)

x.y.,

that is, e m

=

Xmym is not CUt edge.

e,~, obviously, V(/-/') = V ( H ) ,

= da(x);

+ kin_ 1 - ( m -

all x E V ( G ' ) .

edge e,, by Lemma 1. VS,

--

Vx

E

V(H'),

d~(x)

~> 1. We define two functions g and f on V ( G ' )

- (k 1 +'"

0 ~ g(x)
= H-

I , then H has at least one edge not cut edge of

TC_ V ( G ' ) ,

SN

T = r

1) + 1 ) , f ( x )

=

= da(x)by,

= k,, for all x E

We can prove that G' has a ( g , f ) -

E(It')

g(x)

V(G'),

= then

factor containing

[0, k~]7-Factorizafions Orthogonal to a Subgraph ~e(S,T)

= de(T)

- ee(S,T)

- g(T)

de(T)

- ee(S,T)

- dc(Tl)

(m-l)

+ 1 ) I T1 1 + k , .

w h e r e T 1 = {t E T I d e ( t ) -

kl + ' "

Denote T" = T 1 f] V ( W ) , t

+ f(S)

595

=

+ ( k l + "'" + k~,_l -

I S I, 1) + 1 > 0 } .

+ k~,_ 1 - ( m -

= k 1 + ...k~,_ 1 - ( m - 1) + 1. We consider three cases as

follows, where case 1 and case 2 are similar to the case 1 and case 2 in Refs. [ 4 , 5 , 6 ]. Case 1 If I S I >I I T1 I, then = k ~ ( I S I - I T1 l) + ( t + k~) I TI I . d e ( T 1 ) + d e ( T )

~e(S,T)

k,,(I S I - I T1 I) +1 T1 I+ d e ( T )

- ea,(S,T)

- ee(S,T)

>I

>~

k,,(I S I - I . T~ I) +1 TI I ~ > 1 S I - I TI I+1 T1 I = I S II> e ( S , T ) . Case2

I f l S I < I T1 I andl T1 I - I S 11>2, then = t(I T 1 I - I S I) + ( t + k,,) I S l - d e ( T 1 )

$e(S,T)

t ( I T 1 I - I S I) + d a ( S )

+1S l- ee(S,T)

m(I T 1 I - I S I) +l S I+ d e ( T ) m-2+l Case 3

S I-2(m-

If I 3 I < I

Subcase(D

- ee(S,T)

+ de(T)

- dc(Tl)

>>. >~

>~

I~> e ( S , T ) .

and I TI I - I S I = 1, w e consider three subcases as f o l l o w s .

If a l l k l , . . . , k ~ ,

I V(H') I - a o , ( V ( H ' ) ) t~e(S,T)

T1 I ,

1) > 1 S

de(T1)

+ de(T)

~> 3 , then obviously t ~> 2 m - 1,

dH,(T') >I

I T' I -

and

= t l T1 I+ km I S I - d e ( T 1 ) + d e ( T ) t+

( t + k~,) I S I - d e ( T 1 )

t+

de(S)

t

1 + de(S)

-

- ee(S,T)

=

- ee(S,T)

>.

+ de(T)

+1S I- ee(S,T)

+ de(T1)

- dc(Tl)

=

+1 T1 I - d t e ( T 1) ~>

- ee(S,T)

t - I +1 T' I - d o , ( / " ) ~> t-1

S u b c a s e ~)

+1 V(H') I- d~,,(V(H')) >>.

2m-2+1 V(W) I-2(m1) = I V ( W ) 1>>.2>I e ( S , T ) . If at least one of the kl , " " , k,, is equal to 2, without loss of generality, we

may assume k m = 2 and

I T1 I~> 4, then

~e ( S , T) = t I T1 I+ k~ I S I - d c ( T l )

S u b c a s e (~)

+ de(T)

(t+

kin) I T1 I - k~, - d e ( T 1 )

(t+

kin) I T 1 I - d e ( T 1 )

- ee(S,T)

+ de(T)

=

- ee(S,T)

- k,, >~1 Tt I - k., >>. 2 >I r

If at least one of the k l , " " , km is equal to 2, without loss of generality, we

may assume km = 2 and I T1 I<~ 3, then, obviouslyl T' I - d n , ( T ' ) ~> 3 4)) =- m+ land

(3 •

(m-

596

MA Run-nian, XU Jin and GAO Hang-shan ~e(S,T)

= t I T 1 I+ k., I S I - d e ( T 1 ) + d e ( T )

- ee(S,T)

t + ( t + k,~) I S I - d e ( T 1 ) + d e ( T )

- e~(S,T)

t + de( S) +1 S I - e e ( S , T )

=

+ d e ( T ) - de(T1) =

t-l+

d e ( S ) + d ~ ( S N V(H')) +

I Tll-

ee(S,T)

t-l+

dH,(S N V(H')) +1 T1 I+ d e ( T ) - de(T1) >.

t-l+

dH,(S N V(H')) +1 T1 I+ d e ( T 1 ) - de(T1) =

t-l+

dH,(S n V(H')) +1 T1 I - d~r(T1)

t-l+

dx,(S n V(H')) +1 T' I - dH,(T')

m-

+ d e ( T ) - de(T1) >.

1 + dn.(S n

V(H'))

- m + 1 >~

d,,,(S N V(H')). W h e n x ~ , y~ E S, t h e n d t e ( S N V ( H ' ) ~> 2 >~ e ( S , (S n

V ( l t , ) >I 1 ~ e ( S , T ) ;

As is proved above, V S , T

T ) ; whenx., ory,~ E S, then dte

w h e n x ~ , , y., ~ S , then d t r ( S n

V(W)

>~ 0 ~ e ( S , T ) .

C V ( G ' ) , S N T = 0 , we h a v e S e ( S , T )

>I e ( S , T ) .

Hence graph G' has a ( g , f ) - factor Fm containing given edge e.,, that is, graph G has a ( g , f ) factor F,, containing given edge e,,, but not containing edges e l , "'", e.,_l. Note that V x E V(G), f(x)

= k . , , s o F . , is a [ 0 , k . ] -

factor.

On the other hand, letG = G - E ( F . , ) , then0 ~< d e ( x ) - d e ( x ) da(x)-

d e ( x ) + kl + " " + k~,_l - ( m -

<<. d a ( x ) - g ( x )

1) + 1 = kl + " " + km_l - ( m -

S o G is a [ 0 , kl + " " + k m _ l - ( m - 1) + 1 ] - graph a n d / / '

1) + 1.

= H - em is a subgraph with m -

1 edges in G - e,~. By induction hypothesis, G - e,~ has a [ 0, ki ] ~' - 1 _ factorization orthogonal to H ' . Hence, graph G has a [0, k~ ] ~ - factorization orthogonal to H. The proof is completed. References:

[ 1] [2]

Bondy J A, Murty U S R. Graph Theory With Application [ M]. London: Macmillan, 1976. AkiyamaJ, KanoM. Factorsandfactorizationsofgraphs-asurvey[J]. Joumal of Graph Theory ,

[3]

1985,9(1) :1 -42. LIU Gui-zhen. A ( g ,f)-faetorization orth0gonal to a star[J]. Chinese Science Series A , 1995,25

[4]

(4) :367 - 373. (in Chinese) MA Run-nian. A [0, ki]~'-factodzation orthogonal to a tree[J]. Journal of Xidian University,

[5]

1996,23(4) (Graph Theory Issue) :66 - 69. (in Chinese) MA Run-nian, BAI Guo-qiang. On orthogonal [0, ki]~ - facto"nzations of graphs[J]. Acta Mathematica Scientia, 1998,18(4) : 114 -

[6] [7]

118.

GAO An-xi, MA Ran-nian. Orthogonal fac~rizations of graphs[J]. Journal of Shartxi Normal University ( Natural Science Edition ), 1999,27(2) :20 - 22. ( in Chinese) MA Run-nian, Gao Hang-shah. On ( g, f)-faetodzafions of Graphs[ J]. Applied Mathematics and Mechanics ( English Edition), 1997,18(4) :407 - 410.