close

Вход

Забыли?

вход по аккаунту

?

242

код для вставкиСкачать
A Necessary and Sufficient
Condition for the Star
Decomposition of Complete
Graphs
Chiang Lin
Tay-Woei Shyu
DEPARTMENT OF MATHEMATICS
NATlONAL CENTRAL UNIVERSITY
CHUNG-LI, TAIWAN, R.0.C.
E-marl: Ichiang@rnath.ncu.edu.tw
ABSTRACT
In this paper w e prove the following result. Let ml 2 m2 2 ... 2 ml be nonnegative integers. A necessary and sufficient condition for the complete graph K,, to be
decomposed into stars S,,, , S,,, . . . , S,,, is
k
1
Em2
- i) for
k = 1 , 2 , . . . , n - 1 and
i=l
i= 1
2=
x(n
k
m, 5
=
(;)
1
0 1996 John Wiley & Sons, Inc.
Let K , denote the complete graph with n vertices and S, the star with m edges. A necessary
and sufficient condition for K , to have an S,-decomposition was given in [2, 41. A sufficient
condition for K , to be decomposed into a given sequence of stars was obtained in [3]; in this
paper we give a necessary and sufficient condition for this decomposition.
We will use the following theorem of Landau and a technical lemma.
Let ml 2 m2 2 . . . 2 m, be nonnegative integers. A necessary and
Theorem 1 [1,3].
sufficient condition for the existence of an orientation of K , for which the outdegrees of the
Journal of Graph Theory Vol. 23, No. 4, 361-364 (1996)
0 1996 John Wiley & Sons, Inc.
CCC 0364-9024/96/040361-04
362 JOURNAL OF GRAPH THEORY
verticesareml,m2, . . . ,m, is
Em, 5 x(n- i) for 15 k 5 n
z=l
-
I
L=l
and
Lemma 2.
Suppose that
integers such that
k
ml
2 m2 2
...
2 m, 2
.. .
2 ml (I 2 n + 1) are nonnegative
k
and
. . . 2 mjpl bearearrangementofml, m2,. . . ,m7L-1,m,+ml,m,+l,. . . , m ~ - ~ .
z=l
i= 1
and
cfr:
Proof. The required equality follows from the fact that
m: = c , 1= l m,. Now we prove
the inequalities. Suppose mi = m, ml where t 5 n. We can see that
+
mL
m : = { m,-l
i = l , 2 ,.”, t - 1
i = t + l , ..., n.
Suppose, to the contrary of the conclusion,
such that t 5 j 5 n - 1. Then
ml,
7
a=l
But then
i=l
2 )(;
)’;,(
-
+ 1 for some integer j
STAR DECOMPOSITION OF COMPLETE GRAPHS 363
2
(;)
-
1
( " z j ) + l + - (2n - j + l ) ( n - j )
= (;)+n-j+l>(;).
This is impossible and the lemma is proved.
I
Now we state our main result.
Let ml 2 m2 2 . . . 2 ml be nonnegative integers. Then the complete graph
Theorem 3.
K,, can be decomposed into stars S,, ,S,, , . . . , S,, if and only if
k
k
i=l
i=l
and
Proof. (Necessity) Let V(K,) = ( ~ 1 ~ ~. .2,z1,}., . For j = 1 , 2 , . . . , n , let m, = Em,
where the summation is over the stars SmZwith center at v,(fi, = 0 if there is no star with
center at u,).We see that K , can be decomposed into stars S,, ,S,, , . . . ,S ~ ,, where
,
each
S ~ has
3 its center at u3. In an obvious way we can orient K, such that the outdegrees of
211, v2, . . . , z1,
are
m2,. . . , m, respectively. Let mi 2 mh 2 . . . 2 m i be a rearrangement of f i l , 6 2 , . . . ,
By Landau's Theorem,
*,.
and
Thus
k
k
i=l
2=1
i=l
and
(Sufficiency) We may suppose 1 2 n and prove the result by induction on 1. For 1 = n, by
Landau's Theorem, there exists an orientation of K, for which the outdegrees of the vertices
are ml, m2,. . . , m,. Obviously K,, can be decomposed into stars S,, , S,,, . . . , S,,, . Let 1 2
364 JOURNAL OF GRAPH THEORY
n + 1. Suppose the result holds for 1 - 1. Let mi 2 mi 2 . . . 2 mi-l be a rearrangement of
I,
ml ,m2,. . . , m,,-1, m,
mi, m,+l, . . . ,ml-1. By Lemma 2, C,=lmi 5 C,"=,
( n - 2 ) for
k = 1 , 2 , . . . , w - 1 and EfIim: = (;). By the induction hypothesis, K,, can be decomposed
into stars S,,,;, S,,,;, . . , S,,,;-,, and hence into stars S,, , S,,,,, . . . , S,,,,. This completes the
+
proof.
I
The following corollaries follow immediately.
I
Corollary 4 [3]. Let ml, m2, . . . , ml be nonnegative integers such that C,=l
m2 = (:) and
2m, 5 n for 1 5 i 5 1. Then K , can be decomposed into S,, , S,,,,, . . . , S,,,, .
Proof. Suppose that ml 2 m2 2 . . . 2 ml. For 1 5 k 5 n - 1,
k
k
The result follows from Theorem 3.
I
Corollary 5 [2,4]. K,, has an S,,,-decomposition if and only if 2m 5 n and ();
Proof. (Necessity) By Theorem 3, ( n- 1)m 5
(Sufficiency) This follows from Corollary 4.
C::;
= O(mod m ) .
( n - i ) .Thus 2m 5 n.
I
References
[I]
J. W. Moon, Topics on tournaments, Holt, Rinehart and Winston, New York (1968).
[2]
M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math. 26 (1979), 273-278.
[3]
M. Tarsi, On the decomposition of a graph into stars, Discrete Marh. 36 (19811, 299-304.
[4]
S. Yamamoto, H. Ikeda, S. Shige-eda, K. Ushio, and N. Hamada, On claw decomposition of complete
graphs and complete bigraphs, Hiroshima Math. J. 5 (1975), 33 4 2 .
Received June 8, 1995
Документ
Категория
Без категории
Просмотров
3
Размер файла
130 Кб
Теги
242
1/--страниц
Пожаловаться на содержимое документа