3K2-decomposition of a graph

A c t a M a t h . A c a d . Sei. H u n g a r .

40 O---4), (1982), 201--208.

3K~-DECOMPOSITION OF A GRAPH A. BIALOSTOCKI and Y. RODITTY (Tel-Aviv)

1. Introduction

Graphs in this paper are finite, have no multiple edges and loops. DEFINITION 1. A graph G=G(V,E) is said to have an H-decomposition if it is the union of edge-disjoint isomorphic copies of the graph H. Necessary and sufficient conditions for H-decomposition have been determined mostly for the complete graph Kn, see [1, 2], but also for complete bipartite [2] and complete multipartite graphs [2, 5]. However only for particular graphs H. Recently Y. Caro and J. SchSnheim considered H-decomposition of a general graph where H is 2K~ or Pe (two-bars or a path of length 2). This problem was completely solved [3, 4]. This paper determines the graph G which have 3K~-decomposition. It is proved that the necessary conditions are also sufficient excluding a list of 26 graphs. 2. Preliminary results

The following two conditions for are obviously necessary: (1)

G=G(V, E) to have a 3K2-decomposition

E(G)=3k,

(2) deg

(v)<=k,for all vEV(G).

By a simple computation one could easily see that (1) and (2) imply IV[>--6. In the course of this paper we shall deal with the sufficiency problem. DEFINITION 2. If U is a subset of vertices of the graph will denote the degree of v in the graph induced by U U {v}.

G(V, E) then degv(v)

DEFINITION 3. Let G=G(V,E) satisfy (1) and (2) for a certain k. Denote VI={v[vEV(G), deg(v)=k}, and its cardinality by ~. DEFINITION 4. Let G=G(V, E) be a graph and H a subgraph of G. Denote by G',,,H the graph whose set of vertices is the same as that of G and its set of edges is the set E(G)\E(H). DEFINITION 5. Let G=G(V, E) satisfy (1) and (2) for a certain k. Define X = ~/~ degv~ (v), Y= ~, d e g v \ v I (v), where V1 is as in Definition 3. vEV a

vEV a A c t a M a t h e m a t i c a A c a c l e m i a e S e i e n ~ i a r u m H u n g a r i c a e 40, 1982

202

A. BIALSTOCKI A N D Y. RODITTY

THEOREM l. Let G=G(V, E) satisfy (l) and (2)for k. Then, (a)

X ~ 2(~-3)k

(b)

a<=6,

(c)

for all k for all k >=7.

~3,

PROOF. Summing degrees in G implies

(3)

X + Y = ~k.

Counting edges implies X ~ - + Y N 3k,

(4) or

(4')

X + 2Y ~ 6k.

Subtracting (4) from (3) implies (a). Subtracting (3) from

(5)

(4') implies

Y <= ( 6 - ~ ) k .

Since Y is a non-negative integer, e<=6 for all k, and (b) is proved. By definition of X,

(6)

x <= ~ ( ~ - 1).

Substituting (5) and (6) in (3) we obtain:

(7)

( 6 - - a ) k + e ( c ~ - l ) => ak,

or

(7")

a2-ct-2ak+6k

=> 0.

(s)

Substituting

~= 6

in (7') implies

k <= 5.

(9)

Substituting

a = 5 in (T) implies

k ~ 5.

(10)

Substituting

~= 4

k N 6.

in (7') implies

Hence k->-7 implies e<-3. Thus (c) is proved.

3. Main theorem

DEFINITION 6. Ex (k) will denote the set of graphs satisfying (1) and (2) for k, but having no 3K~-decomposition. DEFINITION 7. E x (k) will denote the set of graphs which satisfy (1) and (2) for k + 1 and whose edges are the disjoint union of 3//2 and some element of Ex (k). Acta Mathematica

Academiae

Sctentiarum

Hungaricae

,!-0, i982

3K2-D:ECOMPOSITION OF A G R A P H

203

DEFINITION 8. EXX (4) will denote the set of graphs which satisfy (1) and (2) for k = 4 and contain/(5 as a subgraph. THEOREM 2. (a) For k = 2 and k > 3 , E x ( k + l ) c E x ( k ) , (b) Ex (4) c Ex (3) U Exx (4), PROOF. Let G=G(V,E)EEx(k+I). By Theorem 1 (b), 0<=c~_-<6. We shall deal with the various cases of c~.

Case 1. ~=6. Theorem 1 (a) and (4') imply X=6k and V=V~. Moreover G ~K~. We shall introduce here the only graphs which satisfy (1) and (2) for various values of k + 1. For k + 1 =3 we obtain the following two graphs:

For k + l = 4

we obtain the following graph:

and for k + l = 5 we obtain/(6. One can easily see that none of the listed graphs belongs to Ex (3), Ex (4), Ex (5), respectively. Hence, the case c~=6 is settled.

Case 2. c~=5. Let Vl={vl, v2, vs; v~, vs}. We shall deal with the various cases ofk+l. Let k + l = 3 .

Since

3X5 ~ is not an integer, we may assume without loss of

generality that there is an edge (vl, x) where v~CV1 and xr V~. By Theorem 1 (a) there are at least six edges in the graph induced by/11. Since degv~ (vl)~2 there are at least four edges in the graph induced by Vx\{va} and one can find there 2K~. Adding the edge (v~, x) to 2/(2 we have found 3/(2 as a subgraph of G. Consider now the graph G\3K2 which has six edges and the degree of its vertices does not exceed 2. Since GEEx (k+ 1), G\3K2CEx (k). Hence GEEx (k). Let k + l =4. If Y = 0 then KscG and we are through. Otherwise, we apply the same arguments as for k + l = 3 . Without loss of generality, there is an edge (V~, x), x ~ V~. By Theorem 1 (a) there are at least 8 edges in the graph induced by V~. Since degv, (v0~3, there are at least 5 edges in the graph induced by V~\{vl}. One can see that G contains 3/(2 obtained by taking (v~, x) and 2K2 from the graph A e t a M a t h e m a t i c a A c a d e m i a e S c i e n t i a r u m H u n g a r i c a e 40, 1982

204

A. BIALSTOCKI A N D Y. R O D I T T Y

induced by V~\{v~}. G'x,3K2 has 9 edges and the degree of its vertices does not exceed 3. Since GEEx (k+l), G\3KzEEx (k), Hence GEEx (k). Let k + l = 5 . By Theorem 1 (a), X_->20. Hence the graph induced by V~ is Ks. Take v~EV~ then there exists x q V~ such that (vl, x) is an edge of G. Now taking (vl, x) and (v~, v3) and (v4, %) we certainly obtain 3K~. G'-,,3K~ has 12 edges and the degree of each vertex does not exceed 4. Since GEEx (k+ 1), G\3K~EEx (k). Hence, GEEx (k). By (9), k + l < 6 . Thus Case 2 is settled.

Case 3. ct=4. Let V~= {v1, v~, v3, v4}. Following (10), obviously we have 3Nk+l<=6. Then, the graph induced by V~ has 3, 4, 5 or 6 edges [Theorem 1 (a)], and it is one of the following:

%

~ H1

v3

v~

/"/2

% ~_,

v4

H3

v v2 vl/ov2 vI 12 He

Hs

H6

Iv I47

If k + l = 6 the only possible graph is H~. If k + l =5 the possible graphs are//1 and Hz. If k + 1 = 4 the possible graphs are//1, H2, Ha, and//4. In any of the above cases we choose {(v~,x), (v2, y), (va, v4)}, where x, y ([ V1, to be the set of edges of 3K2. An easy computation shows that such a choice is always possible. If k + 1 =3 the possible graphs are H1, Ha, Ha, Ha, I:fs, H6 or HT. If the graph induced by V1 is HI, H~ or Ha we choose {(vl, v~), (va, v~), (x, y)}, where x, y r Vx, to be the set of edges of 3K~. If the graph induced by V1 is//4, Hs, H6 or/-/7 we choose {(vl, x), (vz, y), (vs, v4)} where x, y ~ V~, to be the set of edges of 3K~. Again, such a choice is always posA c t a rdathema$ica A c a d e m ~ a e S c i e n t ~ a r u m HungarLcae 40, I9~2

3K~-DECOMPOSITION

205

OF A GRAPH

then G\3K~EEx(k). Hence GEEx(k). Thus the case

sible. Since G E E x ( k + I ) a = 4 is settled.

Case 4. aN3. In order to prove this case, we shall prove the following statement:

Let G=G(V,E) be a graph satisfying (I) and (2)for k + l ~ 3 . Then we can find 3K~ in G. Moreover, if there exist a, bE V(G) such that deg (a)~3 or deg (b)=>3 then a, bEV(3K2). PROOF. The only graph that does not contain 2//2 are K3 and a star. But K3 and a star do not satisfy- (1) and (2) for any k. Hence our graph contains 2K2. If there are a, bEV(G) such that d e g ( a ) ~ 3 or deg(b)=>3 then there exist vertices x,yr b such that (x, a), (y, b)EE(G). In any case we shall take 2K2 as (x, a) and (y, b). Let zl, ..., z, (n~2) be the vertices left in G. If there is any edge (z~, zj), we are through. Otherwise all the vertices zl, i r . . . . , n are adjacent only to {a,b,x,y}. Let G2=G2(Vz,E~,) be a graph such that V2= {a, b, x, y} and E2={(s, t)EG]s, tEV2, (s, t);~(x, a), (y, b)}. Denote fl=]E(G2)]. Then obviously 0-<_/~4. Denote by ?(a) and ?;(b) the degrees of a and b in G2, respectively. Then 0<-7(a), ?(b)~=2. If there exist edges (zt, a), (zm,x) for zz#a,, [or (zl, b), (z~,y) where ztr then we shall choose the set of edges of 3K2 to be {(z~, a), (zm, x), (b, y)} [or {(zt, b), (z~, y), (a, x)}]. Otherwise, without loss of generality the possible G\G~ graphs are:

o z1

Zk

~

--ox

x

a ox

Zl

Z1

z2

z2

Z2

Zk

zk

Zk

9

,

Z1

Zk+l zrt-1

Zn -1 ~ C ~

ZD

yO.- zn

YO"

b A

b B

y

b C

Then, in cases A and B either the vertex a or the vertex b has degree at least 3 ( k + l ) - f l +V where ~ is either ?(a) or 7(b). Hence if G satisfies (2) then 2 3 ( k + l ) - f l ~-?_- deg (a) => 3 (k + 1) - 3 - fl + ? where ? = ? (a) and G satisfying (2). The last inequality implies 2 (k + 1) ~ fl + 3 - ?, or k + 1 <: f l - ? + 3 =

2

"

Again using definitions of fl and ,~ we obtain that k + 1 <3. Thus, these graphs do not satisfy (2). A c t a M a t h e m a t i c a A e a d e m i a e S e i e n t i a r u m H u n g a r i c a e 40, I982

206

A. BIALSTOCKI AND Y. RODITrY

We note that in case IV(G)]=6 we can also have that G~G2 is of the form

Calculations for a or b as above show that k-t-1 <3. Hence our statement is proved in all cases. Now, returning to the case c~<=3, the statement guarantees the existence of 3K~ in our graph. In order to complete the proof of the theorem, we have to point out, in each case of e, which edges to choose for 3K~. For e = 0 the statement ensures us that there exist 3/(2 in G. For e---1 again we have 3K2 in G, but since there is a vertex tl such that deg (tl)~3 we choose the 3//2 such that tlEV(3K2). For e = 2 , there exist t~ and t~ vertices in G such that deg(h)=~3, and deg(t~)~3. We take 3K~ such that h, t2CV(3K~). If G ~ E x ( k + l ) then Gx..3K2EEx (k), implying GCEx(k) and we are through if e = 0 , 1, or 2. Let e=3. As before we define VI= {v~, v2, va}. We shall deal with the two cases X = 0 and X_->I. In the former case there exist x,y, zCV(G)\V~, x # y r We choose the set of edges of 3//2 to be {(vl, x), (v~, y), (v~, z)}. Hence we can find 3K2 such that V~cV(3K2). If X ~ I we shall take an edge, say (v~, v2), and an edge (v~, t) It exists since deg (v~)=>3]. From deg (v~)~3, i=1, 2, 3 and ]E(G)]=>9 it is easy to see that there must be vertices u, wEV(G)\V1U {t} such that (u, w)~E(G). Then we shall choose the set of edges of 3//2 to be {(vl, v2), (%, t), (u, w)}. Thus case 4 is proved and the proof of the theorem is complete. Using Definition 6 above, it is easy to see that Ex (1)= O. In addition, if GCEx (2) then either C3 or Ca are subgraphs of G. Hence by checking we obtain: PROPOSITION 1. Ex (2)= {2Ka,

QUK2, K3UK2UP2, K3U3K2, KaUPa}.

Using Theorem 2 and Proposition 1 we obtain: PROPOSITION2. Ex (3) consists of the following graphs:

Ac~a Mathematica

Aeaclemiae

Scien$iarum

Hu~garicae

40, 1982

3K2-DECOMPOSITIONOFA GRAPH

207

Using Theorem 2 and Proposition 2 we obtain: PROPOSITION3. Ex (4) consists of the following graphs."

0 0

0

O

~ O O

o--o

o I

Using Theorem 2 and Proporsition 3 we obtain: PROPOSITION4. Ex (5)= | THEOREM 3 (Main Theorem)~ Let G=G(V, E) be a graph such that G is none of the listed graphs in Propositions 1, 2, 3. Then (1) and (2) are necessary and su~cient for G to have 3K2-decomposition. PROOF. The necessity is obvious. By Theorem 2 and Proposition 4 it follows that Ex (k)= O for all k ~ 5 . Hence (1) and (2) are sufficient. 2

A c t a M a t h e m a t i c a A c a d e m i a e S c i e n t i a r u m H u n g a r i c a e 40, 1982

208

A. BIALSTOCKI AND Y. RODITTY: 3Ka-DECOMPOSITION OF A G R A P H

Acknowledgement. The authors wish to express their appreciation to Professor J. SchSnheim for stimulating them in writing this paper and also for his efforts and attempts to bring them closer to solving many other problems in graph theory. The authors thank also the referee for his constructive remarks.

References [I] J. C. Bermond and J. SchSnheim, G-decomposition of Kn, where G has four vertices or less, Discrete Math., 19 (1977), 113--130. [2] J. C. Bermond and D. Sotteau, Graph decomposition and G-designs. In: Proc. 5th British Combinatorial Conf. (1975), 53--72. [3] Y. Caro, The decomposition of graphs into graphs having two edges. (Unpublished paper.) [4] Y. Caro and J. SchSnheim, Decomposition of trees into isomorphic subtrees, Ars. Combinatoria, 9 (1980), 119--130. [5] E. J. Cockayne and B. L. Hartnell, Edge partition of complete multipartite graphs into equal length circuits. In: Proc. 5th British Combinatorial Conf. (1975), 131--134. (Received August 28, 1980) TEL-AVIV UNIVERSITY DEPARTMENT OF MATHMETICS RAMAT-AVIV, TEL-AVIV ISRAEL

Ac~a Mathematica Academiae Sctentiarum Hungaricar 40, 1982