University of Ljubljana
Institute of Mathematics, Physics and Mechanics Department of Mathematics
Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series, Vol. 47 (2009), 1087
INDEPENDENT DOMINATING SETS AND IDOMATIC PARTITIONS IN DIRECT PRODUCTS OF FOUR COMPLETE GRAPHS
Sandi Klavzar Gasper Mekis
ISSN 1318-4865
Ljubljana, April 14, 2009
Independent dominating sets and idomatic partitions in direct products of four complete graphs
Sandi Klavzar*	Gasper Mekis^
Abstract
Independent dominating sets in the direct product of four complete graphs are considered. Possible types of such sets are classified. The sets in which every pair of vertices agree in exactly one coordinate, called T\-sets, are explicitly described. It is proved that the direct product of four complete graphs admits a partition into T\-sets if and only if each factor has at least three vertices and the orders of at least two factors are divisible by 3.
Key words: independent set; dominating set; idomatic partition; direct product of graph; complete graph
1 Introduction
A fall coloring of a graph G is a partition of V(G) into color classes that are (as usual) independent sets, and every vertex u has at least one neighbor in each of the other color classes. Not every graph contains a fall coloring, consider for instance the 5-cycle, so the basic question here is which graphs admit such colorings. It is not difficult to see that fall colorings of G coincide with partitions of the vertex of G into independent dominating sets. Such a partition is in this context known as an idomatic partition.
Fall colorings were introduced in [2], but a closely related concept was studied back in 1976 by Cockayne and Hedetniemi [1]: they were interested in the largest number of independent dominating sets contained in a given graph. Fall colorings were further studied in [4] where it is proved that a strongly chordal graph G has a fall coloring if and only if the clique number of G equals the minimum degree in G plus one.
'Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia; Faculty of Natural Sciences and Mathematics, University of Maribor, Koroska 160, 2000 Maribor, Slovenia; Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana. E-mail: sandi.klavzar@fmf.uni-lj.si.
^Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana. E-mail: gasper.mekis@gmail.com.
In [2] fall colorings of the Cartesian product of graphs were studied. It was further proved that the only idomatic partitions of the direct product of two complete graphs consist from parts in which one coordinate is fixed and the other arbitrary. The authors also posed the problem of characterizing idomatic partitions of direct products of at least three complete graphs. The problem for three factors was solved in [6]. Roughly speaking, there are only two types of independent dominating sets that can be combined into idomatic partitions. The first type has analogous structure as for two factors (that is, fixing one coordinate and having arbitrary the other two coordinates), the other type consists of sets of size four. While the first type always gives idomatic partitions, there are certain restrictions on the size of factors that guarantee such partitions in the second case. Moreover, the two types can also be combined to obtain additional idomatic partitions. There are no other such partitions.
In this paper we focus on independent dominating sets and idomatic partitions of direct products of four complete graphs. Now the variety of types (see the next section for the definition of a type) is already bigger, there are seven possible types. In Section 2 we first fix the notation and terminology and then show that among the seven possible types, three are not possible and for three there exist independent dominating sets. We don't know, however, about the existence in the remaining case. In Section 3 we characterize independent dominating T1-sets, that is, sets in which every pair of vertices agree in exactly one coordinate. Each such set necessary contains nine vertices whose coordinates can be explicitly described. Then, in Section 4, we prove that the direct product of four complete graphs has an idomatic partition into Ti-sets if and only if the order of at least two factors is divisible by 3.
2 Preliminaries
The direct product G x H of graphs G = (V(G),E(G)) and H = (V(H),E(H)) has the vertex set V(G) x V(H) and edges (g1 ,h1)(g2,h2), where g1g2 E E(G) and h1h2 E E(H). This graph product is commutative and associative, hence it extends naturally to more than two factors. The direct product of graphs G1,...,Gn will be denoted x™=1Gi. It is well-known (cf. [3]) that the direct product of vertex-transitive graphs is vertex-transitive. In the rest we will frequently and implicitly use this fact.
For a complete graph Kn, n > 1, we will always assume V(Kn) = [n] = {0,1,..., n — 1}. Let G = xk=1Kni and let u = (u1,..., uk) and v = (v1,..., vk) be vertices of G. Then let
e(u, v) = |{i | Ui = vi}|
be the number of coordinates in which u and v coincide. With this notation we can state that u and v are adjacent in G = xk=1 Kni if and only if e(u, v) = 0.
Therefore I C V(G) is independent if and only if e(u, v) > 0 for any u, v e I. Note also that e(u, v) < k — 1 holds for any u = v.
Now comes the key definition. Let X C V(G), where G = xk=1 Kni, and let
{e(u, v) | u, v e X, u = v} = {ji,...,jr} .
Then we say that X is a Tj1,...,jr-set.
Let I C G = x33=1Kni be an independent and dominating set of G. Then I can only be a T1-set, a T2-set, or a T1;2-set. Valencia-Pabon [6] showed that there is no such T2-set and described the other two types as well as determined when they form idomatic partitions. We also wish to add that the sporadic example from [2] is a T1-set.
From now on we will consider direct products of four complete graphs and will index the factors from 0 to 3. We first exclude the following four types.
Proposition 2.1 Let I be an independent dominating set of G = x3=0Kni, m > 2. Then I is not T2, T3, T2,3 nor TM.
Proof. Assume on the contrary that I is a T2-set or a T2,3-set. Since I is dominating, |I| > 2. Assume (0,0,0,0) e I. Using vertex-transitivity and the com-mutativity of the direct product we may also assume that (0,0,1,1) e I. Since e((0, 0,1,1), (1,0, 0, 0)) = 1, we get (1,0,0,0) £ I. Hence there exists a vertex (a, b, c, d) e I such that (a, b, c, d) dominates (1, 0, 0,0). This in particular implies that b, c, d = 0. But then e((a, b, c, d), (0,0,0,0)) < 1, a contradiction.
Suppose next that I is a T3-set. We may assume that {(0, 0, 0, 0), (0,0, 0,1)} C I. Clearly, (0,0,1,1) £ I, hence there exists a vertex (a, b, c, d) e I that dominates (0,0,1,1). But then a, b = 0 and thus e((a, b, c, d), (0,0,0, 0)) < 2.
In the last case let I be a T1>3 set. Again, assume that {(0, 0, 0, 0), (0,0, 0,1)} C I. From e((0,0,0,1), (0,0,1,0)) = 2 we deduce that (0,0,1,0) e I. Hence there is a vertex (a, b, c, d) e I that dominates (0, 0,1,0). The elements a, b, and d are different from 0, therefore c = 0 due to the independence of I. Moreover, e((0,0, 0,1), (a, b, 0,1)) = 2, hence d = 1. Since we already know that d = 0, the fourth factor must contain more than 2 vertices, for otherwise no element from I would dominate (0,0,1,0). We next consider the vertex (0,0,0, d), d e {0,1}. Suppose that (0,0, 0, d) e I. I is dominating, so there exists a vertex (e, f, g,h) e I, such that e, f, g = 0 and h = d. But then the vertex (e, f, g,h) is adjacent with at least one of the vertices (0,0,0,0), (0,0,0,1) e I, a contradiction. Thus we must have (0, 0, 0, d) e I. The proof is concluded by observing that e((0,0,0,d), (a,b, 0,d))=2.	□
So we are left with the possible types T1, T1>2, T1;2;3 and all three of them are achievable.
We have already mentioned that for two and three factors one can construct independent dominating sets by fixing one coordinate. This is true for any number of factors, in particular the vertex subset of G = Kn0 x Kni x Kn2 x Kn3, m > 2, defined with
I = [no] x [ni] x [n2] x {i},
where i G [n3], is independent and dominating. Moreover, I is a T1,2,3-set. Of course, we could fix any of the four coordinates in the above construction. But there are additional sporadic independent dominating sets that are T1,2,3. Consider K2 x K2 x K2 x K2, then
11	= {(0, 0, 0, 0), (1, 0, 0, 0), (0,1, 0, 0), (0, 0,1, 0),
(0, 0, 0,1), (1,1, 0, 0), (1, 0,1, 0), (1, 0, 0,1)}
and
12	= {(1,1,1,1), (0,1,1,1), (1, 0,1,1), (1,1, 0,1),
(1,1,1, 0), (0, 0,1,1), (0,1, 0,1), (0,1,1, 0)}
are both independent dominating T1,2,3-sets. In addition, they form an idomatic partition.
We conclude the section with an idomatic partition into T1,2-sets. Let G = K2 x K2 x K2 x K4 and consider the set
I1 = {(0, 0, 0, 0), (1,1,1, 0), (0,1,1,1), (1, 0, 0,1), (1, 0,1, 2), (0,1, 0, 2), (1,1, 0, 3), (0, 0,1, 3)}.
Clearly, I1 is an independent T1,2-set. But it is also dominating. To see it, note first that G consists of four connected components isomorphic to K2 x K4 which is in turn isomorphic to the 3-cube Q3. Then consecutive pairs of vertices dominate the four copies of Q3 respectively. Finally, the sets I1,I2,I3,I4, where
12	= {(u1 + 1 mod 2, u2, u3, u4) | (u1,u2, u3,u4) G I1} ,
13	= {(u1,u2 + 1 mod 2, u3, u4) | (u1,u2, u3,u4) G I1} ,
14	= {(u1,u2,u3 + 1mod2,u4) | (u1,u2, u3,u4) G I1} ,
form an idomatic partition of G.
3 Independent dominating T1-sets
In this section we prove the following:
Theorem 3.1 Let G = Kn0 x Kni x Kn2 x Kn3, m > 2, and let I be an independent T1-set of G. Then I is a dominating set if and only if m > 3 and I is of the form
I = {(00,01,02,03), (00,01,02,03), (ao,Yi,Y2,73),
(^0,01,^2,73), (^0,71,^2,^3), (00,01,72,^3), (70,01,72,^3), (70,^1,02,73), (70,71,^2,^3)} ,
where oi,^i,7i G Kni are pairwise different, 0 < i < 3.
Proof. We will prove Theorem 3.1 in two steps. In the first, major step, we assume that m > 3, 0 < i < 3.
So let I be an independent T1-set of G and without loss of generality assume that (0, 0, 0, 0) G I. Clearly, |I| > 1, hence we may further assume that (0,01,02,03) G I, where 01,02,03 = 0.
If w = 0 then (0,0,0,w) G I, hence there exists a vertex (00,b, c, d) G I, where 00, b, c = 0 and d = w. Since the latter vertex is not adjacent to (0,0,0,0) we get d = 0. In addition, it is also not adjacent to (0,0^02,03), hence either b = 01 and c = 02, or b = 01 and c = In the first case set c = y2, in the second b = y1. This gives the following two possibilities:
A1 = {(0, 0, 0, 0), (0,^1,^2,^3), 000,^,72, 0)} C I
and
A2 = {(0, 0, 0, 0), (0,01,02,03), (00,71,02, 0)} c I.
Similarly, the vertex (0, y, 0,0) does not belong to I hence there exists (a, b, c, d) G
1	(for some a, b, c, d different as above) that dominates (0, y, 0, 0). As (0, 0,0,0) G I, we infer that b = 0. Now comparing (a, 0,c, d) with (0,01,02,03) we obtain either (i) (a, 0, c, d) = (a, 0,02, d), d = 03, or (ii) (a, 0, c, d) = (a, 0, c, 03), c = 02.
Consider case (i). Comparing (a,0,02,d) (d = 03) with the third vertex of A1 we get a = 00. Since 0 = d = 03 we can set d = y3. Similarly, comparing (a, 0,02,d) with the third vertex of A2 we obtain 0 = a = 00 and 0 = d = 03, hence we can set a = Y0 and d = y3.
Consider case (ii). In this case (a, 0, c, 03) (c = 02) is a candidate for a vertex from I. In that case, we must have either a = 00 and c = y2, or a = 00 and
02	= c = y2. In the latter case set c = 52. Note that when n2 = 3 this is not possible there are only three coordinates available for the Kn2 factor. Comparing (a, 0, c, 03) with the third vertex of A2 we find that a = 00. Since 0 = c = 02 we
can set c = y2. Hence we have altogether obtained 5 possible subsets of I:
B1 = A1 u{(6O, 0,^2,73)}, B2 = A2 U {(yO, 0,^2,73)}, B3 = A1 u{(yO, 0,72,63)}, B4 = A1 U{(^0, 0,^2,63)}, B5 = A2 u{(^O, 0,72,63)}.
We next take into account that (0,0, z, 0) EI for any z = 0. Hence there is a vertex (a, b, c, d) E I, a,b,d = 0, c = z. Comparing it with (0, 0, 0,0) we get c = 0. Since it is not adjacent to (0,6b 62,63), either (i) b = 61 and d = 63, or (ii) b = 61 and d = 63.
We first consider case (i), that is, we will compare the vertex (a, 6b0,d) with B1,..., B5. Since e((a, 6b 0, d), (60, A, 72,0)) = 1 we infer a = 60. Hence, as in the set B1 no y0 is present we can set a = y0. Considering further the vertex (60, 0,62,73) E B1 we find that d = y3, for otherwise e((70,61, 0, d), (60, 0,62,73)) = 0. Set
C1 = B1 u{(yO,61, 0,73)}. Next, compare (a, 6b0, d) with B2. Then a = 60 because it is not adjacent to (60,7b 62, 0). In addition, d = y3 as (60, A, 0, d) is not adjacent to (y0, 0, 62,73). So we have the following possibility:
C2 = B2 U {(60,61, 0,73)}.
Next, compare (a, 6b 0, d) with (y0, 0,y2,63) e B3. Since d = $3 we must have a = y0, while d can be denoted with y3, yielding
C3 = B3 u{(yO,61, 0,73)}.
Now compare (a, 6b 0, d) with (60,0, £2,$3). Since d = $3 we have a = $0. But then e((60,61, 0, d), (60,6b72, 0)) = 2, a contradiction. Finally, compare (a,$1, 0, d) with (60,7b62, 0) E B5. Since e((a,6b0,d), (60,7b62, 0)) = 1, we have a = $0. As 0 = d = $3 and y3 is not present in B5 we can set d = y3 thus yielding
C4 = B5 U {(60,61, 0,73)}.
We next consider case (ii) by comparing (a,b,0,$3)(b = $1) with the sets B1,... ,B5. The arguments are similar as above. In particular, also this vertex is not compatible with B4. The other four cases give the following possibilities:
C5 = B1 U {($0,71, 0,63)}, Co = B2 U {(70,71, 0,63)}, C7 = B3 U {($0,71, 0,63)}, Cs = B5 U {(70,71, 0,63)},
where y1 is introduced into C5 and C7, and 7O into C8.
To complete the proof of necessity part of the proof we claim that in any of the above 8 cases the set I is as stated in the lemma. More precisely, if one of the sets C1, C3, C5, C7 is contained in I, then the set
{(0, 0, 0, 0), (0, 01,02,03), (0,71,72,73), (0o, 0,02,73), 000,^1,72, 0), (0o,71, 0,03), (YO, 0,72,03), (70, 01, 0,73), (70,71,02, 0)}
is contained in I. And if one of C2, C4, C8 is contained in I, then eventually the set
{(0, 0, 0, 0), (0,01,02,03), (0,71,72,73), (0o, 0,72,03), (0o, 01, 0,73), (00,71,02, 0), (70, 0,02,73), (70, 01, 72, 0), (70,71, 0,03)}
is contained in I. Note that both of these sets are as claimed in the statement of the lemma, which can be seen by observing that exchanging 00 with 70 in the second set yields the first one. Observe also that such a set is a maximal independent set with respect to the property that e(u, v) = 1 for any of its different vertices u and v.
We are going to prove the above claim for C1. The still missing vertices are
(0,71,72,73), (0o, 71, 0,03), (70, 0,72,03) and (70,71,02, 0),
where 71 G V(Kni) — {0,01} has not yet been introduced.
Assume (70,0,72,03) G I. Then there exists (a, b, c, d) G I such that a = 7O,b = 0,c = 72 and d = 03. Since e((a, b, c, d), (0,0,0,0)) = 1, exactly one of a, c and d equals 0. If a = 0, then we compare (0, b, c, d) with (00,01,72,0) G C1 to realize that they can only be equal in the second coordinate, that is, b = 01. It follows that (0,01,c, d) = (0,01,02,03) G C1, which is not possible because d = 03. Suppose c = 0. Since e((a, b, 0,d), (0,01,02,03)) = 1, we have b = 01. Then (a, 01,0,d) = (70,01,0,73) G C1, another contradiction. Suppose finally d = 0. Since e((a, b, c, 0), (70,01,0,73)) = 1, we get b = 01 and thus (a, b, c, 0) = (0o,01,72, 0) G C1, the final contradiction. We conclude that (70,0,72,03) G I.
To prove that the remaining three vertices necessarily lie in I, some more efforts are needed. Clearly, (0,0,72,73) G I. Note also that this vertex is not dominated with any of the vertices from C1 U {(7O, 0,72,03)}. Hence there exists (a, b, c, d) G I with a, b = 0, c = 72, and d = 73. Since e((a, b, c, d), (0,0,0, 0)) = 1, either c = 0 or d = 0. Assume first c = 0. Comparing (a, b, 0, d) with (00,0,02,73) yields a = 0O. Since (0O, b, 0, d) and (00,01, 72,0) already coincide in one position and differ in two positions, we find that b = 01. Hence we can set b = 71.
Comparing (^0,71,0, d) with (0,	gives d = $3. We conclude that
C1.1 = C1 U{(7o, 0,^2,73)}u{(^o,71, 0,^3)} C I.
Assume next d = 0. Then comparing (a, b, c, 0) with (y0, 0, y2, $3) we get a = y0. Since (Y0,b, c, 0) and (^0,^1,Y2,0) e C1 already coincide in one position and differ in two positions, b = Hence we can introduce b = Y1. We next find that c = by comparing (y0,y1,c, 0) with ($0, 0,$2,y3). So we have another possibility for a subset of I:
C1.2 = C1 U{(Y0, 0,^2,Y3)}U{(Y0,Y1,^2, 0)} C I.
Suppose C1.1 C I. Then we need to prove that (y0, Yb $2,0) and (0, Y1, Y2, Y3) belong to I. Assume on the contrary that (yo , Yb$2, 0) e I. Then there is a vertex (a, b, c, d) e I such that a = Yo,b = Y1,c = $2, and d = 0. Since e((a, b, c, d), (0,0, 0, 0)) = 1 and as d = 0, exactly one of a, b, c equals 0. In the first case compare (0, b, c, d) with ($0,Y1, 0, $3) e C1.1. It follows that d = $3. Then, since e((0, b, c, $3), (0, $1, $2, $3)) > 2, these two vertices must be the same. But this means that c = $2, a contradiction. Assume next b = 0. Then comparing (a, 0, c, d) with (y0,$1, 0,y3) e C1.1 we find that d = y3. It follows that (a, 0, c, y3) = ($0, 0,$2,y3), another contradiction because c = $2. In the last case, c = 0, compare (a, b, 0, d) with (y0, 0,y2,$3) e C1.1 to see that d = $3. Therefore (a, b, 0,$3) = ($0,Y1,0,$3), the final contradiction, since b = Y1. We conclude that (y0 ,Y1,$2,0) e I.
We proceed similarly for the vertex (0, Y1, Y2, Y3) and assume that it does not belong to I. Then there exists (a, b, c, d) e I, such that a = 0, b = Y1,c = y2, and d = y3. Since e((a, b, c, d), (0,0,0,0)) = 1, exactly one of b, c, d equals 0. In the first case compare (a, 0, c, d) with ($0,$1,Y2, 0) e C1.1 to get a = $0. But then ($0,0, c, d) = ($0, 0, $2,y3), which is not possible since d = y3. In the second case we have a = $0 by considering (a, b, 0, d) and ($0, 0,$2,y3) e C1.1. Then ($0,b, 0, d) = ($0,Y1, 0, $3), which is not possible since b = Y1. Finally, if d = 0, we have a = Yo (compare (a, b, c, 0) with (y0, 0,y2,$3) e C1.1), therefore (Y0,b, c, 0) = (y0,Y1,$2,0). Another contradiction, since b = Y1. We conclude that (0, Y1, Y2, Y3) e I and hence I is as required.
Assume C1.2 C I. Then we need to show that ($0,Y1, 0, $3) and (0,Y1,Y2,Y3) belong to I. Suppose ($0,Y1, 0, $3) e I. Then there exists (a, b, c, d) e I, such that a = $0,b = Y1,c = 0, d = $3, and exactly one of a, b, d equals 0. If a = 0 then c = by considering (0, b, c, d) and (Y0,Y1,$2,0). But then (0, b, $2,d) = (0,$1 ,$2,$3), contradicting d = $3. If b = 0, then consider (a, 0, c, d) and (0, $1,$2,$3) to get c = $2. Now (a, 0, $2,d) = ($0, 0, $2,y3), contradicting a = $0. Finally, if d = 0, then (a, b, c, 0) and ($0, 0,$2,y3) give c = $2. But then (a,b,$2,0) = (Y0,Y1,$2,0), which contradicts b = Y1. Therefore, ($o,Y1, 0,$3) eI.
Suppose (0,71,72,73) G I. Then we have (a, b, c, d) G I, where a = 0, b = 71, c = 72, d = 73, and one of b, c, d is 0. If b = 0 then a = 7O (consider (a, 0, c, d) and (70,01, 0, 73)), and therefore (7O, 0, c, d) = (7O, 0,72,03), contradicting c = 72. If c = 0 we get a = 0O (consider (a, b, 0, d) and (00,0,02,73)), and so (0O, b, 0, d) = (0O,71,0,03), contradicting b = 71. Finally, for d = 0 we have a = 7O (consider (a,b,c,0) and (70,0,72,03)). Now (7O,b,c,0) = (7O,71,02,0), contradicting b = 71. We conclude that (0,71,72,73) G I and hence also in this case I is as claimed.
The proofs for the remaining 7 cases, that is, for the sets Cj, i = 2, 3,..., 8, go along the same lines as the above proof for C1. In each of these sets we miss four vertices and exactly one of the integers 7O,71,72, and 73. (In the above case, 71 was missing.) Now, exactly one among the four missing vertices does not contain the missing integer (above such a vertex is (70,0,72,03)). Then we prove for this vertex that belongs to I. We continue by selecting a vertex not in I that coincides with the previous six vertices in at least one position, and coincides in at least one position also with one of the three missing vertices. (Above the vertex (0,0,72,73) played this role.) Now we proceed as above and detect the remaining two vertices. We note that the order in which we prove the inclusion of these two vertices is essential because the inclusion of one of them is needed to prove the inclusion of the other.
Conversely, assume that I contains 9 vertices as described in the statement. We need to prove that an arbitrary vertex x = (5O, 52, 53) G I is dominated by at least one vertex from I.
Note first that for each i, each of the ai,0i, and 7j, appears in exactly three vertices from I. If, say, u, v, and w contain aj, then e(u, v) = 1, e(u, w) = 1, e(v,w) = 1, and, moreover, u, v, and w coincide in the position where ai stands. We now distinguish four cases.
Suppose e(x, (aO, a1, a2, a3)) = 0. Then (aO, a1, a2, a3) dominates x.
Let e(x, (aO, a1, a2, a3)) = 3 and let 5k = ak, where k G {0,1,2,3}. Then x is dominated by the two vertices that contain ak and do not contain ai for i = k.
The next case is e(x, (aO, a1, a2, a3)) = 2. Let 5k = ak and 5e = a^, where k,^ G {0,1,2,3}. Consider the two vertices that contain ak and none of the remaining ai's. These two vertices can coincide with x only in Since they differ in the corresponding position (which is because they agree in ak), one of them dominates x.
The last case to consider is when e(x, (aO,a1 ,a2,a3)) = 1. Let 5k = ak. Then 5i = ai for i = k. Assume that no vertex from I dominates x. Let I1 be the set of the three vertices from I that contain 0k and let I2 be the set of the three vertices that contain 7k. Since x is dominated by no vertex from I1 U I2, we have three positions to agree with each of them. For such a fixed position, x can agree with at most one vertex from I1 and with at most one vertex from I2. Hence only in the optimal case we can have e(x, u) > 1 for each u G I1 UI2. This in particular implies that 5i G {0i,7i} for any i = k. No two of the 5i's, where
i = k, appear in the same vertex from I1 U I2, for otherwise we would have two vertices from this set that would agree on two positions. Note further that for any two integers r and s that appear as coordinates of vertices from I, there is exactly one vertex in I that contains r and s. There are three pairs of integers of the form {5i,5j}, where i,j = k. None of these two such integers appear in the same vertex from I1 U I2. Hence these pairs must appear on the two vertices from I\ (I1UI2 U {(0,0,0,0)}). Therefore, two of these pairs appear on the same vertex, but this means that x is equal to one them, the final contradiction which completes the first step of the proof.
It remains to prove that if 2 G {ni, 0 < i < 3}, then G contains no independent dominating T1-set. Suppose I is such a set and assume (0, 0, 0,0) G I. We may also without loss of generality assume n3 = 2. Since (1,0,0,0) G I, there exists a vertex (a, b, c, d) G I such that a = 1 and b, c, d = 0. Hence d = 1 and because e((a, b, c, 1), (0,0,0, 0)) = 1 we have a = 0. Thus
{(0,0,0,0), (0, b, c, 1)} C I.
Consider next (0,1, 0, 0) G I. Then there exists (e, f, g,h) G I that dominates (0,1,0,0). Similarly as above we get h = 1 and f = 0. Since e((e, 0,g, 1), (0,0,0,0)) = 1 and e((e, 0,g, 1), (0, b, c, 1)) = 1 we also have g = 0 and g = c. If n2 = 2 this is a contradiction because no vertex of I dominates (0,1,0,0). So let n2 > 2. Then
{(0,0,0, 0), (0, b, c, 1), (e, 0,g, 1)} C I.
Now (0,0,1,0) G I, hence there is a vertex (k, l, m,n) G I, such that k, l,n = 0 and m = 1. Similarly as above we find that
{(0,0,0,0), (0, b, c, 1), (e, 0,g, 1), (k, l, 0,1)} C I.
If m0 = 2 or m1 = 2 we have a contradiction because 0, e, k are pairwise different as well as are 0, b, l. So let n0 > 3 and n1 > 3. Since (0, l,g, 1) G I, there is a vertex (x,y,z,w) G I with x = 0, y = l, z = g, and w = 0. The set I is T1 hence (x,y,z, 0) = (e, l,c, 0) or (x,y,z, 0) = (k,b,g, 0). But both possibilities are impossible because y = l and z = g, respectively.	□
4 Idomatic partitions into Ti-sets
We next turn our attention to idomatic partitions of products of four complete graphs and characterize the products which admit such partitions into T1-sets as follows:
Theorem 4.1 Let G = Kn0 x Kni x Kn2 x Kn3, ni > 2. Then G has an idomatic partition into T1-sets if and only if ni > 3 and there exist indices j, k E [4], j = k, such that 3|nj and 3|nk.
In the rest of the section we prove this theorem, where the arguments are in part parallel to those from [6].
Note first that by Theorem 3.1, ni > 3 is a necessary condition for the existence of an idomatic partition into T1 -sets. Hence assume in the rest that this is the case.
Suppose that G has an idomatic partition into T1 -sets. By Theorem 3.1, each part (every T1-set) in an idomatic partition into T1-sets has nine vertices, and thus 9 is a divisor of n0n1n2n3, so there exists at least one j E [4] such that 3|nj. By the commutativity of the direct product, we can assume that j = 3. Let Ig be a T1-set of our idomatic partition. By Theorem 3.1, Ig is of the form
{(0:0,0:1,0:2,0:3), (00,61,62,63), (ao,71,72,73), (60,^1,62,73), (60,71, «2,63), (60,61,72,03), (70,01,72,63), (70,61,02,73), (70,71,62,03)}
for some pairwise different oi,6i,7i E [ni], 0 < i < 3. The number of vertices of the form (x,y,z,o3) with fixed o3 E [n3] in G is exactly n0n1n2. In every T1 -set of the partition in which 03 occurs, there are exactly three vertices (x,y,z,o3), (x', y', z', o3) and (x'', y'', z", o3), where x, x', and x" are pair-wise different and so are y, y', and y''. Hence we must be able to partition the n0n1n2 vertices containing o3 into triples of vertices described above. Therefore, 3|non1n2.
Conversely, assume that there exist indices j,k E [4], j = k, such that 3|nj and 3|nk. The graph G = Kn0 x Kni x Kn2 x Kn3 can be seen as the Cayley graph associated with the direct product group G = Zn0 x Zni x Zn2 x Zn3 with connector set ([n0]\{0}) x ([n1]\{0^ x ([n2]\{0}) x ([n3]\{0}), where Zni denotes the additive cyclic group of the integers modulo ni. Using the commutativity of the direct product again, we can assume that j = 2 and k = 3. Let aj be the element of order nj in the group Znj for j E {2, 3}. Let H0 = ((1, 0, 0, 0)) denote the cyclic subgroup of G generated by the element (1, 0, 0, 0). Similarly, let H1 = ((0,1,0,0)), H2 = ((0,0,a2, 0)) and H3 = ((0,0,0,a3)). It is obvious that Hi n Hj = {(0,0,0,0)} for i, j E [4], i = j. As G is abelian it follows that H0H1H2H3 = {h0 + h1 + h2 + h3 | hi E Hi for i E [4]} is a subgroup of order noni9n2n3 in G. Let us use the notation r = noni9n2n3 and P = H0H1H2H3 = {p1,p2,...,pr}, where we may without loss of generality assume that p1 = (0,0,0,0). Let 6fc and 7k be any elements in Znk \ {0}, with 6fc = 7fc for k E {0,1}, and let 6j and 7j be any elements in Zn. \ {0}, with 6j = 7j; 6j,7j E (aj); and if aj = 0 then
0j ^ 7j mod aj, j G {2, 3}. By standard group theory arguments,
P, (0, 01, 02, 03) + P, (0,71,72,73) + P, (0o, 0, 02,73) + P, (00,71, 0,03) + P, (0o, 01,72, 0) + P, (70, 0,72, 03) + P, (70,01, 0, 73) + P, (70,71,02, 0) + P
is a partition of G into left cosets of P. If we denote
D = {(0,01,02,03), (0,71,72,73), (0O, 0,02,73), (00,71, 0,03), (00,01,72, 0), (70, 0,72,03), (70, 01, 0,73), (70,71,02, 0)},
then no element from D belongs to the subgroup P due to the construction of D. Moreover, there exists no element z G P such that x + z = y for some pairwise different elements x,y G D. Otherwise, z = (zO,z1,z2,z3) is such that Z2 G {±02, ±72, ±(02 — 72)} or z3 G {±03, ±73, ±(03 — 73)}. All these possibilities lead to a contradiction with the conditions of choosing 0j and 7j, j G {2, 3}. Hence our statement about the partition of G into left cosets of P holds. For instance, in the above construction we could have chosen 00 = 01 = 02 = 03 = 1
and 70 = 71 = 72 = 73 = 2.
Now we will construct an idomatic partition of G into T1 -sets. For every pi G P, 1 < i < r, we introduce
Ci = {pi,pi + (0, 01, 02, 03), Pi + (0,71,72,73),
Pi + (0O, 0,02,73),Pi + (00,71, 0,03),Pi + (00,01,72, 0), Pi + (70, 0,72, 03),Pi + (70, 01, 0,73),Pi + (70,71, 02, 0)},
where
Pi + x = (Pi0 ,Pii ,Pi2 ,Pi3) + (xo,x1,x2,x3)
= (Pi0 + xO mod nO,Pi1 + x1 mod n1 ,Pi2 + x2 mod n2,Pi3 + x3 mod n3).
It is clear that for arbitrary pairwise different x,y G D U {(0,0,0,0)} and i G {1,2,..., r} the vertices Pi+x and Pi+y are non-adjacent because of non-adjacency of x and y. That is, all Ci are independent. By Theorem 3.1, all Ci are T1-sets and by our statement above we get (J[=1 Ci = G and Ci n Cj = 0 for i = j. Hence C1, C2,..., Cr is an idomatic partition of the graph G into T1-sets.	□
5 Concluding remarks
We have started the paper with fall colorings and noted that they coincide with idomatic partitions. The fall chromatic number %/(G) of a graph G is defined as the minimum order of a fall coloring of G. Clearly, (G) > x(G).
Since Hedetniemi's conjecture holds for complete graphs, see [5, 8], we have x(xk=1Kni) = min{ni | 1 < i < k}. Let u = min{ni | 1 < i < k}. In Section 2 we have noticed (for four factors) that
Ij = [U1] x ■ ■ ■ x [u^-1] x {j} x [u^+1] x ■ ■ ■ x [ufc] ,
where j G [u^], is an independent dominating set. Consequently, {Ij | j G [u^]} is a fall coloring. Hence Xf (xk=1Kni) < u = x(xk=1Kni) < Xf (xk=1Kni) and so
Xf (xk=1 Kn) = X(xi=1Kn).
An alternative argument for the above conclusion could use the independence number of the direct product of complete graphs, see [7, Corollary 1].
Acknowledgements
We wish to thank Mario Valencia-Pabon for several useful discussions. S. KlavZar was supported in part by the Slovenian Research Agency, program P1-0297.
References
[1]	E.J. Cockayne, S.T. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Math. 15 (1976) 213-222.
[2]	J.E. Dunbar, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely, R.C. Laskar, D.F. Rall, Fall colorings of graphs, J. Comb. Math. Comb. Comput. 33 (2000) 257-273.
[3]	W. Imrich and S. KlavZar, Product Graphs: Structure and Recognition, Wiley, New York, 2000.
[4]	J. Lyle, N. Drake, R. Laskar, Independent domatic partitioning or fall coloring of strongly chordal graphs, Congr. Numer. 172 (2005) 149-159.
[5]	N. Sauer, Hedetniemi's conjecture—a survey, Discrete Math. 229 (2001) 261292.
[6]	M. Valencia-Pabon, Idomatic partitions of direct products of complete graphs, manuscript, 2008.
[7]	M. Valencia-Pabon, J. Vera, Independence and coloring properties of direct products of some vertex-transitive graphs, Discrete Math. 306 (2006) 22752281.
[8]	X. Zhu, A survey on Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998) 1-24.