R ESEARCH I NSTITUTEFOR M ATHEMATICAL S CIENCESKYOTOUNIVERSITY,Kyoto,Japan ByBoramPARK,Suh-RyungKIM,andYoshioSANONovember2008 ThecompetitionnumbersofcompletemultipartitegraphsandorthogonalfamiliesofLatinsquares RIMS-1649

RIMS-1649

The competition numbers of complete multipartite graphs and orthogonal families of Latin squares

By

Boram PARK, Suh-Ryung KIM, and Yoshio SANO

November 2008

R ESEARCH I NSTITUTE FOR M ATHEMATICAL S CIENCES

The competition numbers of complete multipartite graphs and orthogonal families of Latin squares

B

PARK

, S

-R

KIM

, Department of Mathematics Education, Seoul National University, Seoul 151-742, Korea.

Y

SANO

Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan.

November 2008

Abstract

The competition graph of a digraphDis a graph which has the same vertex set as Dand has an edge betweenuandvif and only if there exists a vertexxinDsuch that (u, x)and(v, x)are arcs ofD. For any graphG,Gtogether with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition numberk(G)for a graph Gand it has been one of important research problems in the study of competition graphs to characterize a graph by its competition number.

In this paper, we give new upper and lower bounds for the competition number of a complete multipartite graphK_n^m onmpartite sets of the same sizenby using orthogonal Latin squares. Furthermore, we give better bounds for the competition number of the complete tetrapartite graphK_p⁴for a prime numberp.

Keywords: competition graph, competition number, edge clique cover number, complete multipartite graph, orthogonal Latin squares

∗This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2008-531-C00004).

†The third author was supported by JSPS Research Fellowships for Young Scientists.

‡Corresponding author: [email protected] ; [email protected]

1 Introduction

The notion of a competition graph was introduced by Cohen [1] as a means of determining the smallest dimension of ecological phase space (see also [2]). The competition graph C(D)of a digraphDis a graph which has the same vertex set asDand an edge between verticesuandvif and only if there is a vertexxinDsuch that(u, x)and(v, x)are arcs of D. Roberts [9] observed that ifGis any graph,Gtogether with sufficiently many isolated vertices is the competition graph of an acyclic digraph. Then he defined thecompetition number k(G) of a graph G to be the smallest number k such that G together with k isolated vertices added is the competition graph of an acyclic digraph.

For a digraph D, an ordering v1, v2, . . . , vn of the vertices ofD is called an acyclic ordering of D if (v_i, v_j) ∈ A(D) implies i < j. It is well-known that a digraphD is acyclic if and only if there exists an acyclic ordering ofD.

For a clique S of a graph G and an edge e of G, we say e is covered by S if both of the endpoints ofe are contained inS. Anedge clique cover of a graphGis a family of cliques such that each edge ofG is covered by some clique in the family. The edge clique cover numberθe(G)of a graphGis the minimum size of an edge clique cover of G. Dutton and Brigham [3] characterized the competition graphs of acyclic digraphs in terms of an edge clique cover as follows.

Theorem 1.1 ([3]). A graph G is the competition graph of an acyclic digraph if and only if there exist an ordering v₁, . . . , v_n of the vertices ofG and an edge clique cover {S₁, ..., S_n}ofGsuch thatv_i ∈S_j impliesi < j.

Roberts [9] observed that the characterization of competition graphs is equivalent to the computation of competition numbers. It does not seem to be easy in general to com- putek(G)for all graphsG, as Opsut [7] showed that the computation of the competition number of a graph is an NP-hard problem (see [4], [5] for graphs whose competition numbers are known). It has been one of important research problems in the study of competition graphs to characterize a graph by its competition number.

For some special graph families, we have explicit formulae for computing competition numbers. For example, if Gis a choral graph without isolated vertices thenk(G) = 1, and ifGis a triangle-free connected graph thenk(G) = |E(G)| − |V(G)|+ 2(see [7]).

We denote byK_n^m the complete multipartite graph onmpartite sets of the same size n, and denote an n-set{1, ..., n}by [n]. From the above formulae, it follows that for a complete graphK₁^m =K_m we have k(K₁^m) = 1, and for a complete bipartite graphK_n² we havek(K_n²) = n²−2n+ 2. For a graphK_n¹ =I_nwithout edges, we havek(K_n¹) = 0.

However, for generalmandn, it is so hard to computek(K_n^m)sinceK_n^mhas many cycles and many triangles.

Recently, Kim and Sano [6] gave the exact competition number of a complete tripartite graphK_n³.

Theorem 1.2([6], Theorem 1). Forn≥2,k(K_n³) = n²−3n+ 4.

After then, Parket al.[8] gave the exact competition numbers ofK₂^mandK₃^m. Theorem 1.3([8]). Form≥2,k(K₂^m) = 2.

Theorem 1.4([8]). Form≥3,k(K₃^m) = 4.

So, now, we are interested in the casem≥4andn≥4.

In this paper, we continue to study the competition numbers of complete multipartite graphsK_n^monmpartite sets of the same sizen. We give new upper and lower bounds for k(K_n^m)by using orthogonal Latin squares. Furthermore, we give a better upper bounds for the competition number of a complete tetrapartite graphK_p⁴ of the same sizepwhich is a prime number greater than 4 and also give a better lower bound for k(K_n⁴). This paper is organized as follows. In Section 2, we give some bounds for k(K_n^m) by using orthogonal Latin squares. In Section 3, we focus on complete tetrapartite graphsK_p⁴ with prime numberspgreater than4. In Section 4, we make some remarks.

2 Bounds for the Competition Number of K

In this section, we compute the edge clique cover number ofK_n^m with3 ≤ m ≤ n + 1 when there exists a family L of mutually orthogonal Latin squares of ordern such that

|L| ≥ m− 2(see, for example, [10] for all undefined terms related to Latin squares).

Then we give some bounds fork(K_n^m)with3≤m≤n+ 1when there exists a familyL of mutually orthogonal Latin squares of ordernsuch that|L| ≥m−2.

Suppose that there exists a familyL of mutually orthogonal Latin squares of ordern such that|L| ≥m−2. We denote byv_j^l thejth vertex in thelth partite set forl ∈[m]and j ∈[n]. By the hypothesis, there arem−2Latin squares of ordernwhich are orthogonal each other. LetL₁, L₂, . . . , L_m−2be such Latin squares, and we denote the(i, j)-element ofL_lbyL_l(i, j). Then, we define a setS_ij of vertices fori, j ∈[n]as follows:

S_ij ={v_i¹, v_j², v_L³_1(i,j), v⁴_L2(i,j), . . . , v^m_Lm−2(i,j)}. (2.1) (See Figure 1 for illustration.) We denote bySthe collection of thoseSij, that is,

S :={S_ij |i, j ∈[n]}. (2.2)

Theorem 2.1. Let m and n be positive integers such that 3 ≤ m ≤ n+ 1. Suppose that there exists a family L of mutually orthogonal Latin squares of order n such that

|L| ≥m−2. Then the following are true:

(1) Sdefined by (2.1) and (2.2) is an edge clique cover ofK_n^m of minimum size.

L₁ =

1 2 3 4 5

2 3 4 5 1

3 4 5 1 2

4 5 1 2 3

5 1 2 3 4

L₂ =

1 2 3 4 5

3 4 5 1 2

5 1 2 3 4

2 3 4 5 1

4 5 1 2 3

L₃ =

1 2 3 4 5

4 5 1 2 3

2 3 4 5 1

5 1 2 3 4

3 4 5 1 2

L₄ =

1 2 3 4 5

5 1 2 3 4

4 5 1 2 3

3 4 5 1 2

2 3 4 5 1

Figure 1: For the orthogonal family of Latin squares {L₁, L₂, L₃, L₄}, S₂₄ = {v₂¹, v₄², v₅³, v⁴₁, v₂⁵, v⁶₃}.

(2) θ_e(K_n^m) =n².

Proof. Since any pair of two vertices inSij belongs to distinct partite sets ofK_n^m, the set S_ij is a clique ofK_n^m. Now take an edge eofK_n^m. Thene = v^l_jv^l_j⁰0 for somel, l⁰ ∈ [m]

andj, j⁰ ∈[n]withl6=l⁰. By symmetry, we may assume thatl < l⁰.

If l = 1 and l⁰ = 2, then e is covered by Sjj⁰. If l = 1 and l⁰ ≥ 3, then, by the definition of a Latin square, there exists j^∗ ∈ [n]such that L_l0−2(j, j^∗) = l. Then e is covered byS_jj∗.

Ifl= 2, then, by the definition of a Latin square again, there existsj^∗ ∈[n]such that L_l0−2(j^∗, j) =l. Theneis covered byS_j∗j.

Now suppose thatl≥3. By the orthogonality of Latin squares, there existsi^∗, j^∗ ∈[n]

such thatLl−2(i^∗, j^∗) = j andLl⁰−2(i^∗, j^∗) = j⁰. Then eis covered bySi^∗j^∗. Therefore S :={S_ij |i, j ∈[n]}is an edge clique cover ofK_n^m.

It is easy to see thatShas sizen². Thusθ_e(K_n^m)≤n².

Since any of edges joining a vertex in the1st partite set and a vertex in the2nd partite set belongs to distinct cliques, it follows thatθ_e(K_n^m)≥n². Hence we haveθ_e(K_n^m) =n² andS is an edge clique number minimum size.

The statement (2) is an immediate consequence of (1).

It is a well-known theorem that for any n = p^r, where p is a prime number and r is a positive integer, there exists a complete orthogonal family of Latin squares of order n. Since the size of a complete orthogonal family of Latin squares of order n isn −1, we have a familyL of mutually orthogonal Latin squares of order n with|L| ≥ m−2 if3 ≤ m ≤ n+ 1. Therefore the following corollary is an immediate consequence of Theorem 2.1.

Corollary 2.2. Ifnis a prime power and3≤m≤n+ 1, thenθ_e(K_n^m) = n².

For distinct cliques S and S⁰ of a graph G, we say S and S⁰ are edge-disjoint if

|S∩S⁰| ≤1.

Corollary 2.3. Letm and n be positive integers such that 3 ≤ m ≤ n+ 1. Suppose that there exists a family L of mutually orthogonal Latin squares of order n such that

|L| ≥m−2. LetE be an edge clique cover ofK_n^m of minimum size. ThenE consists of exactlyn² cliques of sizemwhich are edge disjoint each other.

Proof. LetE be an edge clique cover ofK_n^m of minimum size. By Theorem 2.1, we have θ_e(K_n^m) =n². So we putE ={S₁, ..., S_n²}.

Suppose that there exist cliquesS_i, S_j ∈ E such that|S_i∩S_j| ≥ 2andS_i 6=S_j. Any maximal clique ofK_n^mhas sizem. Now we count the number of edges which are covered byE. The two cliquesS_i andS_j cover at most 2·¡_m

2

¢−1edges since |S_i ∩S_j| ≥ 2, and E \ {S_i, S_j} covers at most ¡_m

2

¢(n² −2) edges. Thus the familyE covers at most 2·¡_m

2

¢−1 +¡_m

2

¢(n² −2) =¡_m

2

¢n²−1edges ofK_n^m. On the other hand, we know that

|E(K_n^m)|=¡_m

2

¢n². This contradicts the hypothesis thatE is an edge clique cover ofK_n^m. Therefore any two distinct cliques inE are edge disjoint.

Now we show that|S_i|= mholds for any i = 1, ..., n². Since the size of a maximal clique of K_n^m is m, we have |S_i| ≤ m for any i. Suppose that there exists S_j ∈ E such that |Sj| ≤ m −1. Then the number of edges which is covered by E is at most

¡_m

2

¢(n²−1) +¡_m−1

2

¢ =¡_m

2

¢n²−(m−1)which is less than|E(K_n^m)|. But it contradicts the hypothesis thatE is an edge clique cover ofK_n^m. Therefore any cliques inE have the sizem.

Theorem 2.4. Let m and n be positive integers such that 3 ≤ m ≤ n+ 1. Suppose that there exists a family L of mutually orthogonal Latin squares of order n such that

|L| ≥m−2. Then

k(K_n^m)≤n²−n+ 1.

Proof. TakeSgiven in (2.2) which is an edge clique cover ofK_n^m by Theorem 2.1. Then we define a digraphDas follows:

V(D) = V(K_n^m)∪ {zij |i, j ∈[n], i6=n} ∪ {znn}, A(D) =

n[−1 i=1

[n j=1

{(v, zij)|v ∈Sij} ∪

n[−1 j=1

{(v, v¹_j)|v ∈Snj}

∪ {(v, z_nn)|v ∈S_nn}.

Once we note thatv_n¹ is the only vertex in the 1st partite set that is contained inS_n

j=1S_nj, it is not difficult to see thatDis acyclic. It is obvious that

C(D) =K_n^m∪ {z_ij |i, j ∈[n], i6=n} ∪ {z_nn}. Hence we have shown thatk(K_n^m)≤n²−n+ 1.

As we mentioned above, there exists a familyLof mutually orthogonal Latin squares of ordern with|L| ≥ m−2if nis a prime power and 3 ≤ m ≤ n+ 1. Therefore the following corollary is an immediate consequence of Theorem 2.4.

Corollary 2.5. Ifnis a prime power and3≤m≤n+ 1, thenk(K_n^m)≤n² −n+ 1.

The following theorem gives a lower bound for k(K_n^m)with 3 ≤ m ≤ n+ 1 when there exists a familyLof orthogonal Latin squares of ordernsuch that|L| ≥m−2.

Theorem 2.6. Letm andn be positive integers such that3≤ m ≤n+ 1. Suppose that there exists a family L of orthogonal Latin squares of ordern such that |L| ≥ m−2.

Then

k(K_n^m)≥n²−mn+m+ 1.

Proof. By the definition of competition number, there exists an acyclic digraph D such that C(D) = K_n^m ∪I_k, where k = k(K_n^m). By Theorem 1.1, there exist an ordering v₁, . . . , v_mn+kof the vertices ofK_m×n∪I_kand an edge clique coverF ={S₁, ..., S_mn+k} ofK_n^m∪I_k such thatv_i ∈ S_j ⇒i < j. Note that F is also an edge clique cover ofK_n^m and thatS₁ =∅,S₂ ⊆ {v₁}, . . . ,S_j ⊆ {v₁, . . . , v_j−1}.

Consider the firstmverticesv₁, . . . , v_m. Then there are two cases: (1) any pair of the verticesv₁, ..., v_m belongs to different partite sets; (2) there are at mostm−1partite sets that contain one ofv₁, ...,v_m.

Firstly we consider the case in which any pair of verticesv₁, ..., v_mbelongs to different partite sets. Then S⁰ = {v₁, ..., v_m} is a clique of K_n^m by the definition of K_n^m and S⁰ contains each ofS₁, ..., S_m+1 sinceS_j ⊆ {v₁, ..., v_j−1} forj = 1, ..., m+ 1. Therefore F⁰ :=F ∪{S⁰}\{S₁, ..., S_m+1}is also an edge clique cover ofK_n^m. Now considerS_m+2. We know thatS_m+2 ⊆ {v₁, ..., v_m+1}.

If|S⁰∩Sm+2| ≥2, thenS⁰andSm+2are not edge-disjoint and, by Corollary 2.3,F⁰ is not an edge clique cover ofK_n^mof minimum size. If|S⁰∩S_m+2| ≤1, thenS_m+2contains at most one ofv₁, . . . ,v_m and so|S_m+2| ≤ 2 < m. ThusF⁰ is not an edge clique cover ofK_n^m of minimum size by Corollary 2.3. Thus, in both cases, we have

θ_e(K_n^m)<|F⁰|=mn+k−(m+ 1) + 1.

By Theorem 2.4, we haveθ_e(K_n^m) = n². Hence we haven² < mn+k−(m+ 1) + 1, that is,

k(K_n^m)≥n²−mn+m+ 1.

Now consider the case where there are at mostm−1partite sets that contain one of v₁, ...,v_m. That is, there exists a partite set, sayP, that does not contain any ofv₁, ..., v_m. To cover all the edges which have an endpoint inP, we need at least n² cliques. Since

Sj∩P =∅forj = 1, ..., m+ 1, there are at leastn²+m+ 1distinct cliques inSand so n²+m+ 1 ≤mn+k. Therefore we have

k(K_n^m)≥n²−mn+m+ 1.

Hence we can conclude thatk(K_n^m)≥n²−mn+m+ 1.

Corollary 2.7. Ifnis a prime power and3≤m≤n+1, thenk(K_n^m)≥n²−mn+m+1.

3 The Competition Numbers of Complete Tetrapartite Graphs

In this section, for a prime numberp, we give sharper bounds for the competition numbers of complete tetrapartite graphsK_p⁴ than the upper boundp²−p+ 1and the lower bound p²−4p+ 5obtained in the previous section. LetFp denote the finite field withpelements.

For p = 2 and p = 3, we have k(K₂⁴) = 2 and k(K₃⁴) = 4 by Theorem 1.3 and Theorem 1.4. In the following, we consider the casep≥5.

Theorem 3.1. LetK_p⁴ be a complete tetrapartite graph whose partite sets have the same sizepwhich is a prime number greater than or equal to5. Then we have

k(K_p⁴)≤p² −4p+ 8.

Proof. Let{a_i | i ∈ Fp}, {b_i | i ∈ Fp}, {c_i | i ∈ Fp}, and{d_i | i ∈ Fp}denote the 4 partite sets ofK_p⁴. Note that sincepis prime andp≥ 5, there exists a pair of orthogonal Latin squares of orderp. Let

S ={{a_i, b_j, c_j−i+1, d_j−2i+2} |i, j ∈Fp},

which is an edge clique cover ofK_p⁴ obtained from a pair of orthogonal Latin squares of orderpas given in (2.2). Note that|S|=p²and any two of cliques inS are edge-disjoint by Corollary 2.3.

Now we label all the cliques inS as follows. For1≤i≤7, we putS_ias S₁ ={a₁, b₁, c₁, d₁}, S₂ ={a₁, b₂, c₂, d₂},

S₃ ={a₂, b₃, c₂, d₁}, S₄ ={a₁, b₃, c₃, d₃},

S₅ ={a₂, b₂, c₁, d_p}, S₆ ={a₂, b₄, c₃, d₂}, S₇ ={a₃, b₄, c₂, d_p}. For8≤i≤3p−2, we putS_i as

S₈ ={a₃, b₃, c₁, d_p−1}, S₉ ={a₂, b₁, c_p, d_p−1}, S₁₀ ={a₁, b_p, c_p, d_p}, S₁₁={a₃, b₂, c_p, d_p−2}, S₁₂={a₂, b_p, c_p−1, d_p−2}, S₁₃ ={a₁, b_p−1, c_p−1, d_p−1}, S₁₄={a₃, b₁, c_p−1, d_p−3}, S₁₅={a₂, b_p−1, c_p−2, d_p−3}, S₁₆ ={a₁, b_p−2, c_p−2, d_p−2}, S₁₇={a₃, b_p, c_p−2, d_p−4}, S₁₈={a₂, b_p−2, c_p−3, d_p−4}, S₁₉ ={a₁, b_p−3, c_p−3, d_p−3},

...

S_3p−7 ={a₃, b₈, c₆, d₄}, S_3p−6 ={a₂, b₆, c₅, d₂}, S_3p−5 ={a₁, b₅, c₅, d₅}, S_3p−4 ={a₃, b₇, c₅, d₃}, S_3p−3 ={a₂, b₅, c₄, d₃}, S_3p−2 ={a₁, b₄, c₄, d₄}.

More precisely, we put

S_3t−1 = {a₃, b_p+6−t, c_p+4−t, d_p+2−t}, S_3t = {a₂, b_p+4−t, c_p+3−t, d_d+2−t}, S3t+1 = {a1, bp+3−t, cp+3−t, dp+3−t} for3≤t≤p−1, where all the indices are reduced to modulop.

Furthermore, ifp≥7, then we putS_i for3p−1≤i≤4p−8as S_i ={a₄, b_i+2, c_i−1, d_i−4}.

Then there arep²−4p+8cliques inS\{S₁, ..., S_4p−8}and we label them asT₁, ..., T_p²_−4p+8 arbitrarily. (Note that, in the casep= 5,4p−8 = 12 = 3p−3. )

Now we label the vertices ofK_p⁴ in the following way. We labela₁,b₁,c₁,d₁ inS₁ as v₁, v₂,v₃,v₄. Then label the verticesb₂, c₂,d₂ inS₂ \S₁ asv₅,v₆,v₇. Inductively label the vertices ofS_i \Si−1

t=1S_t in alphabetical order as v_j+1, . . . ,v<sub>j+`</sub> wherej = ¯¯¯Si−1 t=1S<sub>t</sub>¯¯¯ and`=¯¯¯S_i\S_i−1

t=1S_t¯¯¯. That is, we label the vertices ofK_p⁴

a₁, b₁, c₁, d₁, b₂, c₂, d₂, a₂, b₃, c₃, d₃, d_p, b₄, a₃, dp−1, cp, bp, dp−2, cp−1, bp−1, . . . , d4, c5, b5, c₄, a₄, a₅, . . . , a_p−1, a_p

asv₁, v₂, ..., v_4p. Since S₇ = {c₂, d_p, b₄, a₃} = {v₆, v₁₂, v₁₃, v₁₄}and¯¯¯S_i\Si−1

t=1S_t¯¯¯ = 1 for8≤i≤4p−8, it holds that

S_i ⊆ {v₁, v₂, . . . , v_i+7} (3.1) for1≤i≤4p−8. We define a digraphDas follows.

V(D) = V(K_p⁴)∪ {z1, z2, . . . , z_p²_−4p+8}, A(D) =

4p[−8 i=1

{(x, v_i+8)|x∈S_i} ∪

p²−[4p+8 i=1

{(x, z_i)|x∈T_i}.

ThenDis acyclic by (3.1). The following statements are equivalent:

• uv ∈E(C(D));

• There exitsw∈V(D)such that(u, w)∈A(D)and(v, w)∈A(D);

• There exists w ∈ V(D) such that {u, v} ⊂ S_i and w = v_i+8 for some i ∈ {1, . . . ,4p−8}or that{u, v} ⊂T_j andw=z_j for somej ∈ {1, . . . , p²−4p+ 8};

• {u, v} ⊂Sifor somei∈ {1, . . . ,4p−8}, or{u, v} ⊂Tj for somej ∈ {1, . . . , p²− 4p+ 8};

• uv ∈E(K_p⁴).

ThusE(C(D)) = E(K_p⁴)and soC(D) = K_p⁴ ∪ {z₁, z₂, . . . , z_p²_−4p+8}. Hence we have k(K_p⁴)≤p²−4p+ 8.

Next we give a lower bound for the competition numbers of complete tetrapartite graph. The following theorem does not require that the size of the partite sets of a com- plete tetrapartite graph is prime.

Theorem 3.2. LetK_n⁴ be a complete tetrapartite graph whose partite sets have the same sizenwithn ≥4. Then we have

k(K_n⁴)≥n² −4n+ 6.

Proof. We put k = k(K_n⁴) for convenience. Let D be an acyclic digraph such that C(D) =K_n⁴∪I_kand letv₁, v₂, . . . , v_4n+kbe an acyclic ordering of the vertices ofD. Let F ={N_D⁻(v)| v ∈ V(D)}whereN_D⁻(v)denotes the set{w ∈V(D)| (w, v)∈ A(D)} of in-neighbors of a vertex v in a digraphD. By the definition, N_D⁻(v) forms a clique inC(D)and soF is an edge clique cover ofK_n⁴. Then since v₁, . . . , v_4n+k is an acyclic ordering of the vertices ofD, we have

N_D⁻(v_i)⊆ {v₁, ..., v_i−1}.

Let Ei be the set of edges of K_n⁴ covered by the cliques N_D⁻(vi). We define e1 as the number of edges inE₁ande_i (i ≥2)as the number of edges inE_i\ ∪ⁱ_j=1⁻¹E_j. SinceF is an edge clique cover ofK_n⁴,

4n+kX

i=1

e_i =

¯¯¯¯

¯

4n+k[

i=1

E_i

¯¯¯¯

¯=|E(K_n⁴)|= 6n².

LetU7 ={v1, v2, . . . , v7}andnl =|Pl∩U7|forl ∈ {1,2,3,4}, whereP1, P2, P3, P4

denote the 4 partite sets of K_n⁴. Without loss of generality, we may assume that n₁ ≥ n₂ ≥n₃ ≥n₄. Sincen₁+n₂+n₃+n₄ = 7, we haven₄ = 0orn₄ = 1.

Suppose that n4 = 0. Then we need n² cliques to cover all the edges incident to some vertex in P₄. Since P₄ ∩ N_D⁻(v_i) = ∅ for each i ∈ {1, . . . ,8}, it follows that n²+ 8 ≤ |F|= 4n+k, which impliesk ≥n²−4n+ 8 > n²−4n+ 6.

Now we suppose thatn4 = 1. Then there are three possibilities for(n1, n2, n3, n4), that is,(4,1,1,1), (3,2,1,1), and(2,2,2,1). We show thatP8

i=1e_i ≤ 17in each case.

SinceN_D⁻(v_i)⊆U₇ for anyi∈ {1, . . . ,8}, it follows thatE₁∪...∪E₈ ⊆E(K_n⁴[U₇])and thusP₈

i=1e_i ≤ |E(K_n⁴[U₇])|, whereK_n⁴[U₇]denotes the subgraph ofK_n⁴induced byU₇.

If(n1, n2, n3, n4) = (4,1,1,1), then|E(K_n⁴[U7])|= 15and soP₈

i=1ei ≤15.

If(n₁, n₂, n₃, n₄) = (3,2,1,1), then|E(K_n⁴[U₇])|= 17and soP8

i=1e_i ≤17.

Suppose that(n₁, n₂, n₃, n₄) = (2,2,2,1). Then|E(K_n⁴[U₇])|= 18. Since k(K_n⁴[U₇])≥min{θ_v(N_K⁴

n[U7](v))|v ∈U₇}= 2

(see [7], Proposition 7, for this inequality), the set{N_D⁻(vi)|i∈ {1, . . . ,8}}cannot cover all the edges in K_n⁴[U₇]. Otherwise, we have k(K_n⁴[U₇]) ≤ 1, which is a contradiction.

ThereforeP₈

i=1e_i ≤18−1 = 17.

Since the size of maximal cliques inK_n⁴ is4, we haveei ≤ |Ei| ≤¡₄

2

¢= 6for eachi.

Therefore it holds that

6n² =

4n+kX

i=1

e_i = X8

i=1

e_i+

4n+kX

i=9

e_i ≤17 + 6(4n+k−8),

which impliesn²−4n+ 6−⁵₆ ≤k. Sincekis an integer, we haven²−4n+ 6≤k.

Corollary 3.3. Ifpis a prime number greater than or equal to5, then p²−4p+ 6≤k(K_p⁴)≤p²−4p+ 8.

4 Concluding Remarks

In this paper, we gave upper and lower bounds for the competition number of a complete multipartite graphK_n^m with a prime powernand3≤ m ≤n+ 1. Furthermore we gave better bounds for the competition number of a complete tetrapartite graph.

We conclude this paper with leaving the following questions for further study.

• Give the exact value of the competition number of a complete tetrapartite graphK_p⁴ with a prime numberp≥5.

• Give the exact values or better bounds for the competition numbers of complete multipartite graphsK_n^m.

References

[1] J. E. Cohen: Interval graphs and food webs: a finding and a problem, Document 17696-PR, RAND Corporation, Santa Monica, CA (1968).

[2] J. E. Cohen: Food webs and Niche space, Princeton University Press, Princeton, NJ (1978).

[3] R. D. Dutton, and R. C. Brigham: A characterization of competition graphs,Discrete Appl. Math.6(1983) 315–317.

[4] S. -R. Kim: The competition number and its variants, inQuo Vadis, Graph Theory?, (J. Gimbel, J. W. Kennedy, and L. V. Quintas, eds.),Annals of Discrete Mathematics 55, North-Holland, Amsterdam (1993) 313–326.

[5] S. -R. Kim and F. S. Roberts: Competition numbers of graphs with a small number of triangles,Discrete Appl. Math.78(1997) 153–162.

[6] S. -R. Kim, and Y. Sano: The competition numbers of complete tripartite graphs, Discrete Appl. Math.156(2008) 3522-3524.

[7] R. J. Opsut: On the computation of the competition number of a graph, SIAM J.

Algebraic Discrete Methods3(1982) 420–428.

[8] B. Park, S. -R. Kim, and Y. Sano: On competition numbers of complete multi- partite graphs with partite sets of equal size, preprint RIMS-1644 October 2008.

(http://www.kurims.kyoto-u.ac.jp/preprint/file/RIMS1644.pdf)

[9] F. S. Roberts: Food webs, competition graphs, and the boxicity of ecological phase space, Theory and applications of graphs (Proc. Internat. Conf., Western Mich.

Univ., Kalamazoo, Mich., 1976) (1978) 477–490.

[10] J. H. van Lint and R. M. Wilson,A Course in Combinatiorics, 2nd Ed., Cambridge University Press (2001).