MAXIMAL-CLIQUE PARTITIONS
by
Chariya Uiyyasathain
B.S., Chulalongkorn University, 1996
M.S., University of Illinois at Urbana-Champaign, 1998
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
2003
This thesis for the Doctor of Philosophy
degree by
Chaxiya Uiyyasathain
has been approved
by
\ck/ C$/Oi?
Date
Uiyyasathain, Chariya (Ph.D., Applied Mathematics)
Maximal-clique Partitions
Thesis directed by Professor Kathryn L. Fraughnaugh
ABSTRACT
This dissertation discusses maximal-clique partition problems with emphasis
on existence problems. We obtain a necessary and sufficient condition for a line
graph to have a maximal-clique partition. There are three clique parameters
of a graph G: the clique covering number cc(G), the clique partition number
cp(G), and the maximal-clique partition number mcp(G). We evaluate all three
clique parameters for line graphs. In addition, we discuss the complexity of the
problem of finding maximal-clique partitions for line graphs.
We then investigate graphs with maximal-clique partitions of different sizes.
The graph L(K5) has two maximal-clique partitions of different sizes. We con-
firm that there are no graphs with maximal-clique partitions of different sizes of
fewer vertices than L(K5). Also, for each natural number n, we give a clique-
inseparable graph with n maximal-clique partitions of n different sizes.
We investigate the question of the existence of a graph G with cc(G) =
cp(G) < mcp{G). We achieve infinitely many graphs satisfying this property.
Finally, we solve another existence problem regarding graphs with cc(G) <
cp(G) < mcp(G). In 1982, Pullman, Shank and Wallis showed a graph of 11
vertices satisfying cc{G) < cp(G) < mcp(G) and asked whether or not there
exists a graph of fewer vertices with cc(G) < cp(G) < mcp{G). We confirm that
there is no such a graph.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
IV
ACKNOWLEDGMENT
Special thanks are due to my advisor, Professor Kathryn Fraughnaugh, for
introducing me to this interesting topic and advice, for her guidance and encour-
agement. Without her continued support, this thesis would not be possible. I
am also grateful to and very appreciative of my committee members, Associate
Professor William Cherowitzo, Professor Harvey Greenberg, Professor Michael
Jacobson, Professor Richard Lundgren, and Assistant Professor Ross McConnell,..
for their valuable comments and suggestions, and Dr. Sylvia Monson, for her.
kind comments about Chapter 4.
I would like to acknowledge and thank for their financial support: the DPST
(Development and Promotion of Science and Technology Talent Project) schol-
arship from IPST (The Institute for the Promotion of Teaching Science and
Technology), Thailand and the department of Mathematics at the University of
Colorado at Denver for the doctoral fellowship.
Lastly, I would also like to express thanks to my parents and friends for
their support during my stay in the USA.
CONTENTS
Figures ............................................................ viii
Tables............................................................... xi
Chapter
1. Introduction .................................................... 1
1.1 Definitions........................................................ 1
1.2 History and Overview .............................................. 2
1.3 The Existence of Maximal-clique Partitions ........................ 9
2. Maximal-clique Partitions of Line Graphs.......................... 14
2.1 Line Graphs..................................................... 14
2.2 The Existence of Maximal-clique Partitions of Line Graphs....... 15
2.3 Maximal-clique Partitions of L(Kn)................................ 23
2.4 L(K5) ... ...................................................... 28
3. Maximal-clique Partitions of Different Sizes...................... 32
3.1 Smallest Graph with Maximal-clique Partitions of Different Sizes . 32
3.2 The Glue Operator............................................... 39
3.3 Maximal-clique Partitions of k Different Sizes.................... 46
3.3.1 Graphs with k Maximal-clique Partitions of the Same Size .... 47
3.3.2 Graphs with Maximal-clique Partitions of k Different Sizes .... 50'
4. Graphs with cc cp < mcp ..................................... 53:
4.1 Our First Target Graph.......................................... 54
vi
4.1.1 The Construction................................................ 55
4.1.1.1 The Graph L................................................... 55
4.1.1.2 The Graph B................................................... 58
4.1.1.3 A Target Graph U* .......................................... 59
4.1.2 The Clique Numbers of U*........................................ 60
4.2 A Family of Target Graphs ..................................... 64
4.2.1 Link Graphs L* and Base Graphs Bk............................. 64
4.2.2 Target Graphs Uk................................................ 68
4.3 The Smaller Target Graphs......................................... 74
5. Clique Partitions of Graphs with Ten Vertices..................... 80-
5.1 Ten Vertex Graphs with a Maximal-clique Partition............... 81
5.2 The Nonexistence of Graphs having Ten Vertices and cp < mcp . 105
5.2.1 Definitions and Values of Pi and m*........................... 106
5.2.2 The Target Theorem.............................................. 117
6. Conclusion and Open Problems for Future Work...................... 123
6.1 Conclusion........................................................ 123
6.2 Open Problems for Future Work..................................... 124:
References............................................................. 127
FIGURES
Figure
1.1 cc(Gn) = n and cp(Gn) = 2n 1 ................................... 3
1.2 Monsons graph.................................................. 7.
1.3 Pullman, Shank and Wallis (PSW)s graph........................... 9
1.4 Kite and ocular graph........................................... 9.
1.5 The kite K is contained in an ocular graph ...................... 10
1.6 Each kite is contained in an ocular graph while the graph contains
no MCP.......................................................... 11
1.7 Example shows clique-separable and clique-inseparable graphs ... 12
2.1 Example of a line graph.......................................... 14
2.2 Motivating examples.............................................. 16
2.3 Triangle T and corresponding subgraph in L(G).................... 17
2.4 e e V(L(G)) can be adjacent to at most two vertices in Q(v) .... 19-
2.5 H contains a triangle whose vertices satisfy the condition, but H has
a maximal-clique partition...................................... 22
2.6 L(Ks): the line graph of K5...................................... 23
2.7 Each edge in Â£* destroys the maximality of triangles in %........ 30
3.1 Hx = A(l, 2,3) C G\ and H2 = A (a, b,c)CG2 .................... 39
3.2 Hx = A(l, 2,3) C Gx and H2 = A(a, b, c) C G2 ................. 40
3.3 The unique resulting graph...................................... 41:
viii
3.4 H\ is not maximal in G\ whereas H2 is maximal in C2................ 43
3.5 L{K^) with two maximal-clique partitions, and JV4.................. 47
3.6 Hk.................................................................... 49
4.1 Monsons graph........................................................ 54
4.2 The link graph L...................................................... 55
4.3 The partition of E{L) into 12 triangles.............................. 56
4.4 The partition of E{L) into 12 copies of Ki^.......................... 57
4.5 B = L U T0 U Ti U ... U Tn = AT0 U ... U Xn......................... 58
4.6 A copy of L(K5) glued to B at a triangle.............................. 60
4.7 12 cliques needed to cover the 12 thick edges......................... 62
4.8 The link graph L* .................................................... 65
4.9 3k pairwise clique-independent edges.................................. 70
4.10 The base graph B:i and its subgraph L3 represented by the thick edges 73
5.1 ad E Ci and bd E C2................................................... 83
5.2 Ci is a 4-clique and C2 is a triangle................................. 84
5.3 Both Ci and C2 are triangles.......................................... 86
5.4 A graph of ten vertices with a maximal-clique partition containing a 1
2-clique............................................................. 87
5.5 Three configurations of H............................................. 87
5.6 The configuration of I................................................ 88
5.7 The configuration of J................................................ 88
5.8 The edge set of H is partitioned into three groups.................... 90
5.9 Edges a, b, and c are the type-1 edges in Configuration 1 of H ... 91
IX
5.10 The seven type-1 edges in Configuration 2 of H..................... 92.
5.11 Nine type-1 edges in Configuration 3 of H........................... 92
5.12 The possible X when T G M and z X................................... 99
5.13 Seven type-1 edges in Configuration 2 of H......................... 100
5.14 Nine type-1 edges in Configuration 3 of H.......................... 101
5.15 The subset H of G composed of four 4-cliques in V.................. 103
5.16 The subgraph H of G................................................ 120
5.17 Pullman, Shank and Walliss Graph.................................. 121
6.1 A graph illustrating /i+ and jT..................................... 125
x
TABLES
Table
2.1 Relationships between G and L(G)................................. 15 .
xi
1. Introduction
1.1 Definitions
For our purpose, graphs are simple. Cliques are complete subgraphs of a
graph that are not necessarily maximal. The number of vertices in a clique v
is its order. A clique of order n is also called an n-clique or Kn. A 3-clique
is also referred to as a triangle. The triangle on the set of vertices {a, b, c}'
is represented by A(a,b,c). The 4-clique on the set of vertices {a,b,c,d} is- '
represented by Kl(a, b, c, d). A clique covering of G is a family C of cliques of
G such that every edge of G lies in at least one member of C. The number of
cliques in a clique covering is its size. The smallest size among all possible clique
coverings of G is called the clique covering number of G and denoted by cc(G). A
minimum clique covering is a clique covering of size cc(G). A clique partition is .
a clique covering in which each edge belongs to exactly one clique. The smallest. -
size of all possible clique partitions of a graph G is the clique partition number
denoted by cp{G). A minimum clique partition is a clique partition of G having
size cp(G).
A maximal clique is a clique that is not contained in any larger clique. If
every element in a clique partition V of G is maximal, then V is a maximal-clique
partition of G (or briefly, an MCP of G). A maximal-clique partition with the...
smallest size among all possible maximal-clique partitions of G is a minimum ::
maximal-clique partition of G and its size is denoted mcp(G). We refer to cc(G);
cp(G) and mcp(G) as cc, cp and mcp, respectively, if there is no ambiguity.
1
Every graph has at least one clique covering and clique partition, namely the
edge set of the graph. However, a graph does not necessarily have a maximal-;
clique partition. For example, when n > 4, Kn\K2, which is the graph obtained :
by deleting one edge from Kn, does not have a maximal-clique partition. (Be- v
cause all maximal cliques in Kn \ K2 are (n l)-cliques and each pair of them
share an edge.) In fact, many graphs do not have a maximal-clique partition.
1.2 History and Overview
The maximal-clique partition problem is one of many problems of covering
and partitioning the edge set of a graph with a minimum number of cliques. The .
algebraic problem of factoring binary matrices, the geometric problem of mini- -
mum perfect pair coverings, and the set theoretic problem of finding a smallest ,
set having a family of subsets with prescribed intersection properties are inti-.
mately connected to graph theoretic problems.
The subject of clique coverings of graphs has its origins in the problem of
intersection sequences. Erdos, Goodman, and Posa in 1966 [10] and Lovasz in::'
1968 [16] considered the problem graph theoretically. In the early 1970s, H.
Ryser [36] studied it as a problem in matrix theory. In 1977, J. Orlin empha- .
sized the graph theoretic approach and obtained several results [26]. F. Roberts
compiled a survey paper listing many applications of these and related ideas in
1985 [35]. The first survey of clique coverings of graphs for the early works was
written by N.Pullman [27] in 1982. More recently, clique coverings and partitions
have been studied by Wallis and co-authors [38, 37, 39, 41, 42, 40, 43, 44, 45],:
Cacetta et al. [3], Monson et al. [25], and others. An excellent survey by Mon- :
2
son, Pullman, and Rees [24] appeared in 1995 and updates and extends the 1982
survey [27]. It collects most related works and is considered to be one of the
most valuable recent works.
The problem can be thought of as three subproblems: clique covering, clique
partition and maximal-clique partition problems. They yield three clique num7
bers cc(G), cp(G) and mcp(G) of a graph G. The difference in their values
may be zero or extremely large depending on the graph. For example, all three
clique numbers of Kn are the same which is 1. However, the graph Gn of n + 2
vertices in Figure 1.1 has a minimum clique covering composed of n triangles:-
A (a, b, Vi), i = 1,..., n, and a minimum clique partition composed of one trian-
gle and the remaining 2(n 1) edges. Hence, cc(Gn) = n and cp(Gn) = 2n 1.
The difference between cc(Gn) and cp(Gn) is n 1.
Figure 1.1: cc(Gn) n and cp{Gn) = 2n 1
Clique covering problems have been studied widely during the 1990s for
many classes of graphs by a variety of authors, for instance, complements of:
cliques [31], regular graphs [5, 29], cubic graphs [4], threshold graphs [18], chordal'
3
graphs [17], generalized chordal graphs [41], complements of paths and cycles [8] ;
line graphs [21], and self-complementary graphs [7].
In parallel, clique partition problems have been investigated. Pullman and
de Caen [30] studied clique partitions of regular graphs, the cartesian product;
of graphs and graphs of maximal degree at most three in 1981. Later, Wallis
and co-authors studied clique partitions of many classes of graphs including split,
graphs [40], chordal graphs [19, 11], threshold graphs [18], squares of trees [42],
complements of triangles [43], complements of cycles [37], graphs of the form
GV Kn [45], and complements of one-factors [12, 38]. In addition, McGuinness,.
Sean and Rees [21] studied clique partitions of line graphs, Lone [15] clique
partitions of graphs without odd chordless cycles and Rees [34] clique partitions
of norm three.
Because clique covering and clique partition numbers are somewhat related
and one can be much harder to determine than the other, some authors have
tried to find relationships between them in order to help determining the value
of the harder one. In 1985, Caccetta et al. [3] examined the clique covering .-
and clique partition numbers in terms of their difference, which is called the
spread, and in 1988, Erdos et al. [9] investigated them in terms of their ratio.
The clique partition problem is also related to several other concepts. Two such
articles concern clique partitions and pairwise balanced designs by Rees [33] and
clique partitions and finite planes by Wallis [39]. The clique covering problem
is also extended to the biclique covering problem: see biclique covering number
of Kn \ Km and complete f-partite graphs [13]. Also, the effect of vertex and'
4
edge deletion on clique numbers [23, 2] and linear operators preserving partition s. -
numbers of graphs [1] are more recent related topics.
The maximal-clique partition problem is developed further from the clique
partition problem. Unlike clique partition and clique covering problems, there- .
have only been a few articles regarding maximal-clique partitions. A paper [32]-
written by Pullman, Shank and Wallis in 1982 covers some main concepts of '
the problem giving a few open problems. Since the existence of a maximal-s
clique partition requires maximality of all cliques in a partition, many graphs .
do not have a maximal-clique partition. Problems related to maximal-clique-
partitions are hard to solve. Results for only a few classes of graphs have been v
published so far: graphs with maximum degree at most four [32], triangulated v V
planar graphs [32], irreducible graphs [44], interval graphs [20] and threshold
graphs [18].
This dissertation emphasizes maximal-clique partitions. We study graphs
with a maximal-clique partition and examine some relationships between the;
maximal-clique partition number and other clique numbers of a graph.
We will start by providing simple results about the existence of maximal-
clique partitions in Section 1.3 to provide the reader with some intuition about v
this problem.
In Chapter 2, we obtain a necessary and sufficient condition for a line graph
to have a maximal-clique partition, along with all three clique numbers and the.
complexity of the maximal-clique partition problems for line graphs. Although -
the fact that the line graph of the n-clique L(Kn) has two maximal-clique par- -
5
titions are well known, we provide details and investigate L(K$) further. These.. :
results will be used throughout the rest of the dissertation.
Chapter 3 involves graphs having at least two maximal-clique partitions of
different sizes. When n is at least 5, L{Kn) has two maximal-clique partitions
of different sizes. Pullman, Shank and Wallis (PSW) [32] asked whether or not.
there is a graph with maximal-clique partitions of different sizes of fewer vertices
than L{Ks). We confirm that there is none. In [32], PSW also found a clique-
inseparable graph (defined in Section 1.3) with n maximal-clique partitions. -
However, all of them have the same size. We will show that there exists a-
clique-inseparable graph with n maximal-clique partitions of n different sizes..
The details of this will be found in Section 3.3. These graphs are obtained by
gluing many copies of a variety of line graphs of complete graphs together. ;. -
Chapter 4 and Chapter 5 will emphasize the three clique parameters cc, cp
and mcp. Since a clique partition is a clique covering, cc < cp. Since a maximal-
clique partition is a clique partition, cp < mcp. Hence, it is always true that
the three clique parameters of a graph satisfy cc < cp < mcp. These clique :
parameters of a graph are not always equal. However, all graphs with at most-.
nine vertices have the same three clique parameter values. This fact was proved' r
by Monson in her Ph.D. Dissertation [22], Thus, these three parameters could
be different when a graph has ten or more vertices. In Chapter 2, we show
that if a line graph has a maximal-clique partition, then it has cc = cp = mcp.
Interval graphs [20] and graphs with norm at most 4 [32] are also examples of::
graphs having cc cp = mcp.
6
Figure 1.2: Monsons graph
As cc < cp < mcp, there are three more relationships among the three
clique parameters, which are cc < cp = mcp, cc = cp < mcp and cc < cp < mcp.
Monson found the graph of ten vertices with cc < cp = mcp shown in Figure
1.2. This graph G has cc(G) = 8 < cp(G) = mcp{G) = 9. Since ten vertices
is the minimum number of vertices needed to get different values for the three'
clique parameters, Monsons graph has the minimum number of vertices for a
graph satisfying cc < cp = mcp. ;
The question of the existence of graphs with cc cp < mcp has been
investigated by Monson [22] who conjectured [personal communication] that no
such graph exists. Chapter 4 answers this open problem. In fact, we construct
infinitely many graphs with cc = cp < mcp. They will be constructed by using-.
the glue operator (defined in Chapter 3) and their clique numbers will be verified:.1
7
The smallest graph among those constructed in this fashion has 68 vertices and .
234 edges.
The next chapter involves the last relationship of clique parameters cc <
cp < mcp. Pullman, Shank and Wallis [32] found a graph of 11 vertices satisfying :
this relationship. The graph is shown in Figure 1.3 with cc = 5 < cp = 8 <'>
mcp = 10. They asked whether or not there exists a graph of fewer vertices : \
satisfying cc < cp < mcp. In order to find such a graph, since graphs of at most -.
nine vertices give cc cp mcp, our candidate graphs must have ten vertices. \
Chapter 5 studies related issues for graphs of ten vertices. The first part provides T
some characteristics of clique partitions and maximal-clique partitions of graphs: -,
with ten vertices. The second part of the chapter shows that in fact a graph
of ten vertices with cp < mcp does not exist. Hence, PSWs graph is a graph:
having the minimum number of vertices satisfying cc < cp < mcp. We conclude .
that graphs satisfying cc < cp < mcp or cc = cp < mcp have at least 11 vertices.
Finally, the conclusion and some open problems for future work are located
in Chapter 6. Since many graphs do not have a maximal-clique partition, we :
suggest a way to investigate how much a graph deviates from having a maximal-
clique partition.
8
Figure 1.3: Pullman, Shank and Wallis (PSW)s graph
1.3 The Existence of Maximal-clique Partitions
Definition 1.1 Let the graphs shown in Figure 1.4 be called the kite and the '.
ocular graph.
Kite Ocular Graph
Figure 1.4: Kite and ocular graph
9
Lemma 1.1 For any graph G, if G has a maximal-clique partition, then each-
kite in G must be contained in an ocular graph in G.
Proof Assume G has a maximal-clique partition Ad. Let K be a kite in G
whose vertices are labelled a, b, c and d as in Figure 1.5.
a
M2
Figure 1.5: The kite K is contained in an ocular graph
Because A(a,b,c) and A(b,c,d) share an edge, both of them cannot be in
Ad at the same time, say A(b, c, d) is not in Ad. It follows that edges bd and cd
must be contained in other maximal cliques in Ad, say Mi and M2, respectively. ..
Mi is not edge bd because edge bd is not maximal. Thus, Mi contains a triangle
Ti sharing bd with the kite K. Similarly there exists a triangle T2 sharing cd
with the kite K. Therefore, Ti and T2 together with A(a,b,c) and A(b,c,d) -.
form an ocular graph in G containing the kite K.
A kite in a graph not satisfying the condition in Lemma 1.1 prevents the exis-
tence of a maximal-clique partition of the graph. There are a number of graphs
containing kites that do not satisfy the condition. However, the condition in-./
10
Lemma 1.1 is not sufficient. Some graphs still do not have a maximal-clique
partition though they satisfy the condition in the lemma. An example is shown
in Figure 1.6.
Figure 1.6: Each kite is contained in an ocular graph while the graph contains
no MCP.
Determining whether a graph has a maximal-clique partition can be confined
to determining whether certain of its subgraphs has a maximal-clique partition
as follows:
Definition 1.2 A subgraph of G is a proper subgraph of G if it does not contaiii: :
all edges of G and it is a nonempty subgraph of G if it contains at least one edge
of G. If a subgraph H has the property that for every clique K in G, either every
edge of K or no edge of K lies in H, then we say that H separates the cliques
of G. If a proper nonempty subgraph separates the cliques of G', we say G is
clique-separable. Otherwise G is clique-inseparable. If a subgraph B separates
the cliques of G, but no proper nonempty subgraph of B does so, we call B a.
clique-block of G.
11
Example 1.1 Let Gi and G2 be graphs in Figure 1.7.
C
Figure 1.7: Example shows clique-separable and clique-inseparable graphs
Consider subgraphs Hi and H2 of G\ where Hi is composed of the edge ab
and H2 is composed of two edges ab and be. H2 does not separate cliques of Gi
because A(b,c,d) has edge be in H2 but edges bd and cd are not in H2. It is easy,
to verify that Hi separates the cliques of G\. Hence, Gi is a clique-separable
graph. Gi has two clique-blocks, the edge ab and the triangle A(b,c,d). In
contrast, there is no proper nonempty subgraph separating the cliques of G2.:
Thus, G2 is a clique-inseparable graph.
Note that a clique-block is clique-inseparable in itself. Therefore, a subgraph
B is a clique-block of G if and only if B is a clique-inseparable graph and B is
not a subgraph of any other clique-inseparable subgraph of G. Note that if G
has isolated vertices, then they form one clique-block of G. It was shown in [28];
that the family B(G) of clique-blocks partitions the edge set of G.
12
Lemma 1.2 (Lemma 2.1 in [32])
The graph G has a maximal-clique partition if and only if each of its clique-blocks'
has a maximal-clique partition, in which case
mcp(G) = ^ mcp(B)
BeB(G)
Therefore, the study of maximal-clique partitions may be confined to clique-
inseparable graphs.
13
2. Maximal-clique Partitions of Line Graphs
2.1 Line Graphs
Let G be a connected graph. The line graph L(G) of G is the graph
generated from G by V(L(G)) = E(G) and for any two vertices e, / G V(L(G)},
vertex e and vertex / are adjacent in L(G) if and only if edge e and edge / share >
a common vertex in G. If H is the line graph of G, we call G the root graph of
H.
Figure 2.1: Example of a line graph
Because edges in L(G) are induced by a pair of edges in G sharing a com-
mon endpoint, each vertex v G V(G) with d(v) > 2 generates a clique, denoted.:
Q(v). Vertices in Q(v) correspond to edges incident to v in G; thus, Q(v) has
order dc(v). Let V^G) be the set of vertices in G of degree at least 2. Then,
(Q(u) : v G V2(G)} partitions the edge set of L(G).
14
Table 2.1 contains a summary of properties of the vertices and edges in G
and of their corresponding elements in L(G):
Table 2.1: Relationships between G and L{G)
In G In L(G)
edge e vertex e
vertex v of degree do(v) clique Q(v) of order da(v)
V2(G)= the set of vertices {Q(v): U e V2(G)}=
of degree at least two in G a clique partition of L(G)
2.2 The Existence of Maximal-clique Partitions
of Line Graphs
Consider the three motivating examples in Figure 2.2. Example 1 illustrates
a line graph L(Gi) that does not have a maximal-clique partition. Example 2
shows a line graph L(G2) with a maximal-clique partition. Note that the root
graph G\ has a vertex of degree two, but the root graph G2 does not contain;
a vertex of degree two. However, the root graph G3 in Example 3 contains a
vertex of degree two, but L(Gz) has a maximal-clique partition. Hence, a vertex
of degree two is not the only factor that effects the existence of maximal-clique '
partitions of a line graph. Although both G1 and G3 contain a vertex of degree
two, the vertex of degree two in G\ is in a triangle whereas the one in G3 is not.
This idea leads to our necessary and sufficient condition on a root graph G that
guarantees the existence of a maximal-clique partition of the line graph L(G)..
15
Example 1
Figure 2.2: Motivating examples
Theorem 2.1 Let G ^ K% be a connected graph. Then,
L{G) has a maximal-clique partition if and only if no vertex of degree two in G
lies in a triangle.
Moreover, if L(G) has a maximal-clique partition, then the set of cliques
generated by vertices of degree at least two in G forms a maximal-clique partition
of L(G).
16
Proof Let G ^ K3 be a connected graph.
(=>) Assume L(G) has a maximal-clique partition At. Suppose there exists a
triangle T in G containing a vertex v of degree 2. As in Figure 2.3, let u,v,
and w be the vertices of T and let ei,e2 and e3 be the edges uv, vw, and uw-,,
respectively. Since G is not a 3-clique and is connected, T contains a vertex of
degree at least 3, say vertex u. Then u is incident to an edge outside T, say;
edge e4 = ut. Figure 2.3 illustrates this situation.
Now, consider L{G). As we observed in Table 2.1, T in G becomes a triangle
A(ei,e2,e3) in L(G); also, u, v, and w in G produce cliques Q(u),Q(v), and
Q(w) in L(G), respectively. Since v has degree two, Q(v) in L(G) is the edge.
eie2. Figure 2.3 illustrates the triangle T in G and its corresponding subgraph
in L(G).
In G In L(G)
Figure 2.3: Triangle T and corresponding subgraph in L(G)
In G, since v has degree two and G is simple, e3 is the only edge adjacent
to both edges e4 and e2 at the same time. That is, the vertex e3 in L(G) is the
only vertex adjacent to both vertices e\ and e2. Hence, A(ei,e2,e3) is the only
17
maximal clique in L(G) containing edge eie2. It follows that A(ei, e2, e3) must be.
in M. However, Q(u) contains edge eie3, while eie3 is covered by A(ei, e2, e3)..
So, Q(u) cannot be in M. Now, let K be the clique in M containing edge .
eie4. (So, K is maximal.) If all vertices in K correspond to edges in G that
share vertex u with t\ and e4, then K is a subgraph of Q(u), contradicting the'
maximality of K. Hence, there exists a vertex in K corresponding to an edge
in G that shares the other endpoint (which is not u) with ei and e4. It forces
the edge vt in G, which yields another edge in G incident to v besides edges e4
and e2. This contradicts d(v) = 2.
(<=) Conversely, assume that no vertex of degree two in G lies in a triangle.
We will show that L(G) has a maximal-clique partition. -
Since (Q(u) : v y2(G)} is a clique partition of L(G), it is sufficient to
show that Q(v) is maximal in L(G) for all v Â£ V2(G).
Case 1 d(v) > 2. Then Q(v) is a clique in L(G) of order at least 3. Consider
any vertex in L(G) not contained in Q(v). Let e 6 V(L(G) \ Q(v)). Since e -
is not in Q(v), v is not an endpoint of e. Then as in Figure 2.4 (G is simple);
edge e in G is incident to at most two edges in L(G) that contain v. Hence, in
L(G) the vertex e can be adjacent to at most two vertices in Q(v). Since Q(v)
has order more than two, e is nonadjacent to a vertex of Q(v). Hence, Q{v) is
a maximal clique. This completes the proof for this case.
Case 2 d(v) = 2. Let ei = vx and e2 = vy be the two edges incident to v
in G. If a; is incident to y, the set {v,x,y} forms a triangle in G containing the
vertex v of degree 2. This contradicts the assumption. Thus, x is not adjacent .
18
InG
v
In L{G)
Q{v)
e is adjacent to at most 2 vertices in Q(v)
Figure 2.4: e G V(L(G)) can be adjacent to at most two vertices in Q(v)
to y in G. Since x y and d(v) = 2, there is no edge incident to both e\ and' l.
e2 in G. It follows that there is no vertex in L(G) adjacent to both vertices e\
and e2. Hence, the edge eie2 is not contained in other cliques in L(G). Note,
that Q{v) consists of just the edge eie2. Thus, it is maximal. This completes1
the proof in this case.
In both cases we have shown that each Q(v), where v e V2(G), is a maximal
clique in L(G). Therefore, {Q(v) : v G V2{G)} is a maximal-clique partition of... ;.
L{G).
Theorem 2.2 (Orlin, 1977 [26]) Let G be a connected graph but not a 3-clique.: :
Let m be the number of triangles with exactly two vertices of degree two in G.
Then
cp{L{G)) = \V2(G)\ and
cc(L(G)) = \V2(G)\-m.
19
We extend Theorem 2.2 to include the maximal-clique partition number for
line graphs.
Theorem 2.3 Let G be a connected graph. If L(G) has a maximal-clique par-i
tition, then
partition. By Theorem 2.1, G is a 3-clique or each triangle in G contains
no vertices of degree two. If G is a 3-clique, L(G) is also a 3-clique. Then
cc(L(G)) = cp(L(G)) = mcp(L(G)) = 1. Otherwise, each triangle in G con-
tains no vertices of degree two. That is, G does not contain any triangles with.,
exactly two vertices of degree two. Hence, by Theorem 2.1 and Theorem 2.2,
Theorem 2.1 gives a characterization of the root graph of a given line graph
with a maximal-clique partition. Next we will provide a condition of the line
graph that guarantees a maximal-clique partition. The following is straight,
forward, but we need it to prove our next theorem.
Lemma 2.1 Let G be a connected graph. For e = uv G V(L(G)), e is contained
in Q(x) if and only if x = u or x = v. Moreover, dL(G){z) = da(v) + da(u) 2:-
Proof Since edge e has two endpoints in G, vertex e can be contained in
only two cliques in L(G). As we observed in Table 2.1, Q(v) and Q(u) have order-
1 if G is a 3-clique,
\V2(G)\ if G is not a 3-clique.
Proof Let G be a connected graph. Assume L(G) has a maximal-clique
cc(L(G)) = cp{L{G)) = mcp(L(G)) = |V2(G)|.
20
dc(v) and do(u), respectively. Hence, vertex e in L(G) is adjacent to do{v) 1
vertices in Q{v) and da(u) 1 vertices in Q(u).
Theorem 2.4 Let H be a line graph. If no maximal triangle S = A(v,u,w) in
H has vertices satisfying dj{(u) + d^(w) dn(v) = 2, then H has a maximal-
clique partition.
Proof Let H be a line graph and let G be the root graph of H, i.e.,
H = L(G). If H is a triangle, then H itself is a maximal triangle. Hence,;
assume H ^ K$ and that H does not have a maximal-clique partition. By
Theorem 2.1, there exists a triangle T = A (a,b,c) in G containing a vertex a
of degree 2. The triangle S = A(ab,bc,ac) in H comes from the edges of T in
G. Note that there is no edge in G that can be incident to all three edges in
T. So, there is no vertex in H adjacent to all three vertices in S. Hence, S is
a maximal triangle. Now by Lemma 2.1, we have dniab) da{a) + dc(b) 2,
dH{bc) = do{b) + do(c) 2, and dff(ac) = dc(a) + dc{c) 2. Thus,
dn{ab) + dH(ac) dnipc)
= [dc(a) + da{b) 2] + [da (a) + dc(c) 2] [do(^) + <^g(c) 2]
= [2 + da{b) 2] + [2 + dc(c) 2] [d(?(&) + ^g(c) 2]
= 2.
Hence, H contains a maximal triangle A(ab,bc,ac) whose vertices satisfy
djj(ab) + dn{ac) dn{bc) 2. Therefore, the theorem is proved as desired. .
Our condition in Theorem 2.4 is sufficient to guarantee a maximal-clique
partition of a line graph without finding the root graph of the line graph. How-r.
21
ever, the existence of a maximal triangle S = A(u, v, w) in the line graph whose
vertices satisfy d(u) + d(w) d(v) = 2 cannot guarantee that the given line
graph does not have a maximal-clique partition. As in Figure 2.5, H is a line
graph of G, and S = A(u, v, w) is a maximal triangle in H whose vertices satisfy
d(u) + d(w) d(v) = 2, but H has a maximal-clique partition composed of two .
3-cliques and two 2-cliques.
H = L(G) G
Figure 2.5: H contains a triangle whose vertices satisfy the condition, but H
has a maximal-clique partition.
Generally, the maximal-clique partition problem is NP-complete [24]. How-
ever, the condition in Theorem 2.1 leads to an algorithm with linear time. Given
a graph H, Lehot [14] presents a linear time algorithm for testing whether H
is a line graph and retrieving the unique simple graph G such that H = L(G).
Then to test whether there exists a maximal-clique partition only requires find-
ing vertices of degree two in G and verifying whether they are in a triangle (by
checking whether the endpoints of the two edges incident to a vertex of degree
two are adjacent). Hence, the condition in Theorem 2.1 can be checked in linear
time. Therefore, the maximal-clique partition problem for line graphs has a:
linear time complexity in terms of the input size.
22
2.3 Maximal-clique Partitions of L(Kn)
For n > 5, the line graph of n-clique L(Kn) has a special property. It
contains exactly two maximal-clique partitions and their sizes are different. We ,
first illustrate the two maximal-clique partitions of L(K5) to get the general idea
for L(Kn). Then we define two maximal-clique partitions Mn and Afn of L(Kn). ,
We shall then verify that Ain and Mn have different sizes when n is at least 5.
As A5 has ten edges, L(K5) has ten vertices. In Figure 2.6, each vertex in
L(K5) is labelled according to its corresponding edge in G. Then two distinct,
vertices in L(K5) are adjacent if their labels share a digit.
#
4 3
K,5
L{Kb)
Figure 2.6: L(K5): the line graph of K5
23
Let u E {1,2, 3,4,5} be a vertex in K5. Recall that Q(u) is a clique in
L(K5) derived from u. Since dKb{u) = 4, Q(u) is a 4-clique. Then V(Q(u)) =
{nl,... ,u(u 1 ),u(u + 1),... ,un}. Let Ads = {Q(u) : u = 1,... ,5}. By /
Theorem 2.1, At5 is a maximal-clique partition of L(KÂ§). We refer to Ads as
the vertex-induced partition of L(K5). '
Next, consider the triangles of K5. They may be identified with the 3-sets
of {1,2,3,4,5}. There are (g)=10 such subsets. Let {x,y,z} be any 3-set of.
{1,2,3,4,5}. Then vertices xy,yz and xz form a triangle in L(K5). Consider any ... '
vertex outside the triangle A(xy, yz, xz). Its label can contain at most one digit
in {x,y,z}. Thus, it is adjacent to at most two vertices in A(a:y,yz,xz). That ;
is, A(xy,yz,xz) is maximal. Hence, a 3-set of {1,2,3,4,5} induces a maximal
triangle in L(K5). Furthermore, the ten maximal triangles induced from the ten
3-sets partition the edge set of L(K5), forming another maximal-clique partition
of L(K5). Let A/5 be the collection of ten maximal triangles induced from these '
ten 3-sets. It is referred to as the triangle partition of L(K5). Therefore, L(Kf) '
has two maximal-clique partitions, Ads of size 5 and A/5 of size 10. .
In general, L(Kn) is the intersection graph of the 2-sets of an n-set. The
vertex set of L(Kn) is the collection of all 2-sets of the n-set. Hence, L{Kn) has
(2) vertices, and any two vertices of L(Kn) are adjacent if and only if they share
exactly one element. The graph K\ has no edges, so L(Kf) is an empty graph.
When n = 2, then K2 has one edge which implies that L{Kf) is K\. When !
n = 3, then K3 is a triangle. It is easy to see that L(Kf) is also a triangle.
In the same fashion as in our explanation of L(K5), the triangle partition A/y-.
24
consists of the triangle L(K3) itself, and the vertex-induced partition M3 is the
set of three edges in L(Kz). However, each edge in M3 is not maximal; hence,
M3 is not a maximal-clique partition of L{K3). Hence, for our purposes, we
consider L(Kn) when n is at least 4.
Now let n be any integer at least 4. As before, let u G {l,...,n} be a
vertex in Kn. Then Q(u) is an (n l)-clique in L(Kn) induced by u. The set
{Q(u) : u = 1,..., n} is the vertex-induced partition of L(Kn) which is denoted
Mn By Theorem 2.1, Mn is a maximal-clique partition of L(Kn). Clearly,
|A4n| = n. Next, we get the triangle partition of L(Kn), or Afn, by considering'
3-sets of the n-set. Each of these 3-sets produces a triangle in L(Kn). Since
there are (") 3-sets of the n-set, there are (3) of such triangles; so, they covert
3- (^)=Zti(n"1Hri-~2) edgeg in L(Kn). Because L(Kn) is composed of n copies of
An_ 1, L(Kn) has n \E(Kn-1)| = n- (n~1)=n (n-lHn-2) edges. Therefore, the
collection of all of such triangles partitions the edge set of L(Kn). And in the
same fashion as L(K5), we can conclude that each of these triangles is maximal
in L(Kn). Hence, J\fn, which is the collection of these maximal triangles, is
another maximal-clique partition of L(Kn). Therefore, for n > 4, L(Kn) always
has exactly two maximal-clique partitions Mn and J\fn where \Mn\ = n and
ivi= (;) =
When n 4, .M4 = 4 and |.V[| = (] = 4^4-IK4"2) 4. Hence, Ms and
JV4 have the same size. When n > 5, we have n 1 > 4 and n 2 > 3,
so n(nri)(n-2) > n'(4H3) = 2n. Hence, for n > 5, |A4n| = n < 2n < |A/"n|.
Furthermore, consider possible maximal cliques containing an edge (xy,yz) in
25
L(Kn). A vertex that can be adjacent to both xy and yz must be either vertex xz
or its label containing y. The first case yields a maximal triangle A(xy,yz,xz)
in J\fn. The latter case yields a maximal (n l)-clique Q(y) in Adn. This shows
that each edge in L(Kn) is contained in exactly two maximal cliques and all
possible maximal cliques in L(Kn) are in Adn or Afn. Now, let Ad be a maximal-
clique partition of L(Kn). If an (n l)-clique Q(t) in Adn is in Ad, since V(Q(t))
is {tl, Â£2,... ,Â£(Â£ 1), Â£(Â£ +1),..., tn}, for any i ^ j {1, ...,Â£ 1, Â£ +1,..., n},
edge e\ = (ti, tj) is covered by Q(t). But e\ is also in A(ti, tj, ij)\ so, A(ti, tj,ij).
is not in Ad. Since edge 62 = (tj, ij) is in A(ti,tj,ij), it follows that Q(j) must
be in Ad to cover 62- Since j is arbitrary, the remaining (n l)-cliques in Adn
must be in Ad. We have shown that if a clique in Adn is in a maximal-clique
partition of L(Kn), then all cliques in Adn must also be in it. Therefore, L(Kn)
has exactly two maximal-clique partitions. In particular, when n is 4, L(K4)
has exactly two maximal-clique partitions of the same size, and when n is 5 or
more, L(Kn) always has exactly two maximal-clique partitions, and they have
different sizes.
Notice that, for n > 4, the largest order of a clique in L(Kn) is n 1 and
Adn is composed of (n l)-cliques; so, Ain is a minimum clique covering of
L(Kn). Hence, we can conclude that for n > 4, cc(L(Kn)) = cp(L(Kn)) =
mcp(L(Kn)) = |Adn| = n.
In conclusion, the properties of L(Kn) mentioned above are summarized in
the following lemma for reference later:
26
Lemma 2.2 (Folklore) (i) For any integer n > 4, L(Kn) has exactly two.
maximal-clique partitions, the vertex-induced partition M.n of size n and the .
triangle partition J\fn of size n(n~1Kn~2). In particular, \M.f[ = \N\1; otherwise,
A4n and J\fn have different sizes.
(ii) For any integer n > 4, cc(L(Kn)) = cp(L(Kn)) = mcp(L(Kn)) =
\Mn\ = n.
Note that we can also derive Lemma 2.2(H) from Theorem 2.3. Next,
Lemma 2.3 shows that for n > 4, L(Kn) is a clique-inseparable graph. (Clique-..:
inseparable is defined in Definition 1.2.)
Lemma 2.3 For any integer n > 4, L(Kn) is a clique-inseparable graph.
Proof Let n > 4. Let H be a nonempty subgraph of L(Kn) separating
cliques in L(Kn). Let e = (uv,vw), where u ^ v ^ w e {l,...,n}, be an
edge in H. (The two endpoints of an edge in L(Kn) have labels sharing a.
digit.) Recall that Q(v) is an (n l)-clique in the vertex-induced partition:
where V(Q(v)) = {vl,v2,... ,v(v l),u(u-|- 1),... ,vn}. Then Q(v) contains e:-
Since e is in H which separates cliques in L(Kn), Q(v) must be a subgraph of
H.
Let a be any vertex in Kn other than u or v. Since edge (va, vu) is in Q(v),
edge (va, vu) is in H. But edge (va,vu) is also contained in A(va,vu,ua)\ be-
cause H separates cliques of L(Kn), A (va, vu, ua) must be a subgraph of H, i.e.7
(va,ua) is contained in H. Moreover, edge (va,ua) is also in Q(a), it follows,
that Q(a) must be a subgraph of H. Since a is arbitrary, all (n l)-cliques in the..
27
vertex-induced partition are subgraphs of H. Hence, H = L(Kn). Therefore,
there is no proper nonempty subgraph of L(Kn) separating cliques in L(Kn).
Thus, L{Kn) is a clique-inseparable graph.
2.4 L(K5)
The ten vertices of L{K5) correspond to the ten edges in K5. Each vertex
can be labelled by two digits corresponding to the two labels on the endpoints
incident to the edge it comes from in K5. Two vertices in L(K5) are adjacent
if and only if they share a digit. Hence, L(K5) is also an intersection graph. It'
follows from Section 2.3 that L(K5) has exactly two maximal-clique partitions,
the vertex-induced partition M.5 and the triangle partition J\f5. All maximal
triangles of L{K5) are in J\f5. Another interesting fact about L(K5) is that the
complement of L(K5) is the Petersen graph. In this section we discuss the effect
of adding edges of the complement of L(K5) into L(A5).
Let e = (xx',yy') be an edge in the complement of L(K5). (So, x ^ x ^
y 7^ y1.) And let L(K5) + e be the graph that results from adding the edge e to
L(K5). Consider any triangle T containing the edge e in L(K5) + e. Since the
third vertex in T is adjacent to both xx' and yy', one digit in the label of the third
vertex must be either x or x' and the other digit must be either y or y'. Without
loss of generality, say the third vertex is xy. That is, T = A(xx', yy, xy). Since:
vertex xy1 is adjacent to all three vertices in A(xx',yy',xy), triangle T is not
maximal in L(K5) + e.
Furthermore, adding edge e = {xx',yy') to L{K$) creates four 4-cliques in
28
L(K5) + e, namely E(xx',yy',xy,x'y), M(xx', yy', xy', x'y1), 3(xx1 ,yy,xy,xy'),
and M(xx',yy',x'y,x'y'). Hence, it destroys the maximality of four trian-
gles in L(K~~
A (yy', x'y, x'y').~~
For example, adding edge (12,34) to L(K5) creates four 4-cliques
lÂ§3(12,34,13,23), 13(12,34,14,24), 3(12,34,13,14), and 3(12,34,23,24), and
destroys the maximality of triangles A(12,13,23), A(12,14, 24), A(34,13,14),
and A(34,23,24).
Let e be an edge in the set {(xx',yy'), (xy,x'y'), (xy',x'y)}. Then
{A(xx',xy,x'y), A(xx',xy,,x,y'), A(yy', xy, xy'), A(yy'} x'y, x'y')} be the set
of all maximal triangles in L(K5) but not maximal in L(K5) + e. This relation
partitions the edge set of the complement of L(K5) into five classes A,... ,Â£5
and the set of the maximal triangles in L(K5) into five classes 7i,..., % as in
Figure 2.7. Then for i = 1,..., 5, e Â£ Â£j if and only if all triangles in % are not
maximal in L(K5) + e.
Next, we consider adding three edges of the complement of L(K^) into
L(K5). Let the resulting graph be called L(K5) + 3e. Note that adding all
three edges in the same class to L(K5) does not create any new maximal trian-
gle in the resulting graph while it destroys the maximality of all triangles in %.
Hence, the graph obtained from adding at most three edges in the same class
to L(KÂ§) contains at most six maximal triangles. However, if not all of them
are in the same class, then they may create at most two new maximal triangles
in L(K5) + 3e. Since \% D Tj\ = 1, adding three edges not in the same class to
29
L(K5) destroys the maximality of seven triangles of L(K5). Hence, the graph
obtained from adding three edges not all in the same class to L(K$) contains at
most 10 + 2 7 = 5 maximal triangles. We will put this fact in Remark2.1 and:
we will refer back to it in Chapter 5:
Â£, = {(12,34), (13,24), (14,23)}
Tx = {A(12,13,23), A(12,14,24), A(13,14,34), A(23,24,34)}
Â£2 = {(12,35), (13,25), (15,23)}
T2 = {A(12,13,23), A(12,15,25), A(13,15,35), A(23,25,35)}
Â£3 = {(12,45), (14,25), (15,24)}
% = {A(12,14,24), A(12,15,25), A(14,15,45), A(34,35,45)}
Â£4 = {(13,45), (14,35), (15,34)}
% = {A(13,14,34), A(13,15,35), A(14,15,45), A(34,35,45)}
Â£5 = {(23,45), (24,35), (25,14)}
T5 = {A(23,24,34), A(23,25,35), A(24,25,45), A(34,35,45)}
Figure 2.7: Each edge in destroys the maximality of triangles in %.
30
Remark 2.1 The graph that results from adding three edges to L(Kf) contains
at most six maximal triangles.
L(K5) is the smallest line graph of an n-clique having maximal-clique parti-
tions of different sizes. In the next chapter we will show that L(K5) is in fact the
smallest one among graphs with a maximal-clique partitions of different sizes. .
31
3. Maximal-clique Partitions of Different
Sizes
Chapter 3 is concerned with maximal-clique partitions of different sizes.
By Lemma 2.2, when n is at least 5, L(Kn) has two maximal-clique partitions
of different sizes. In 1982, Pullman, Shank and Wallis [32] asked whether or
not there is a graph with maximal-clique partitions of different sizes and fewer
vertices than L(K5). This chapter confirms that there is no such graph. In
the same paper [32], Pullman et al. exhibited a clique-inseparable graph with
n maximal-clique partitions. However, all of them have the same size. We
are interested in whether or not there exists a clique-inseparable graph with n
maximal-clique partitions of n different sizes. Section 3.3 illustrates a graph
satisfying this property. The graph is constructed by gluing many copies of
various sizes of line graphs of complete graphs. A graph operation called the
glue operator will be introduced in Section 3.2 and some of its properties will
be investigated.
3.1 Smallest Graph with Maximal-clique
Partitions of Different Sizes
We start by preparing a list of properties of graphs with at least two
maximal-clique partitions. We will apply the classic theorem of de Bruijn and .
Erdos [6] as formulated in graph theoretic terms by Orlin in [26].
32
Lemma 3.1 (i) The intersection of two different maximal cliques of a graph-:-
is empty or a clique of order less than the order of either.
(ii) Any two cliques in the same clique partition of a graph share at most
one vertex.
Proof The proofs are simple, but here are the details:
(i) Clearly the nonempty intersection of two cliques is a clique. If the in-
tersection is a clique of the same order as one of the original cliques, then such:
clique is contained in the other one, contradicting its maximality.
(ii) If two cliques in a maximal clique partition V share two vertices, they
will share the edge joining these vertices, contradicting the fact that V is a par- >
tition.
Theorem 3.1 (N.G. de Bruijn and P. Erdos [6], 1948)
IfC is a clique partition of an n-clique and 1 < \C\ < n, then C is composed
of either
(i) one (n 1 )-clique and n1 copies of 2-cliques or
(ii) n copies of (m + l)-cliques if there exists an integer m such that n
m2 + m + 1.
33
Corollary 3.1 Let M be a maximal clique partition of a graph. Then each n-
clique K in the graph that does not belong to M. needs at least n different cliques
in M to cover its edges.
Moreover, if K is covered by n cliques in A4, say Mi, M2,..., Mn, then
{K n M{ : i = 1,2,..., n\ is composed of either
(i) one (n 1)-clique and n 1 copies of 2-cliques or
(ii) n copies of (m + 1 )-cliques if there exists an integer m s.t. n = to2 + m + 1:
Proof Let K be an n-clique that does not belong to M. Consider cliques in
M. covering edges of K. Let V C M. be composed of maximal cliques covering
edges of K. Let V' = {K D C : C E V}. Notice that members in V are
cliques, and by Lemma 3.1 (i-i), they share at most one vertex. Thus, V' is a
clique partition of K. Moreover, both types of clique partitions of K in Theorems
3.1 have size n, which means that K has no clique partitions of size i, where
1 < i < n. Hence, \P\ \T'\ > n.
If K is covered by exactly n maximal cliques in Ai, then the second part of
the corollary follows immediately from Theorem 3.1.
34
Theorem 3.2 Let M be any maximal-clique partition of a graph. Let K be an
n-clique in the graph that does not belong to M.. '
(i) If every two maximal cliques in A4 covering edges of K share a vertex
in K, then there are at least n vertices not in K.
(ii) If there exist two maximal cliques in M. covering some edges of K but
not sharing a vertex in K, then there are at least six vertices not in K.
Proof (i) Let K be an n-clique that does not belong to M. such that every
two maximal cliques in M covering edges of K share a vertex of K. Let Mi and
M2 be two maximal cliques in M. covering edges of K. Then M\ and M2 share ,,
a vertex in K. By Lemma 3.1(2), each of Mi and M2 must contain a vertex
that is not contained in K. However, since they share a vertex in K, by Lemma '
3.1(22), they cannot share vertices outside K. Hence, each maximal clique in M >
that covers edges of K has a distinct vertex outside K. By Corollary 3.1, K is,
covered by at least n cliques in M; so there are at least n vertices outside K.
(ii) Let K be an n-clique in the graph that does not belong to A4. Assume
there exist two maximal cliques, say Mi and M2, in Ai covering edges of K
and not sharing a vertex in K. Then each of them contains at least one edge.
of K and, therefore, at least two vertices of K. Let ab and cd Â£ E(K) be
contained in Mi and M2, respectively. Because Mi and M2 do not share a
vertex of K, edges ac,ad,bc and bd cannot be in Mi or M2. Moreover, if any -
two edges in {ac, ad, be, bd} are in the same maximal clique, then such a clique :
contains edge ab or cd, contradiction. Hence, edges in {ac, ad, be, bd} must be
in different maximal cliques in A4. This yields a 4-clique [x](a, b, c, d) which
35
is a subset of K covered by six maximal cliques in M. For convenience, for
any i,j E {a, 6, c, d}, let My be the maximal clique in Ai covering edge ij of:
K. Hence, M4 and M2 are renamed M0{, and Mcd, respectively. By Lemma
3-1 (z), each My contains an extra vertex not in K. If all such extra vertices
are different, we have six extra vertices as desired. Otherwise, there are two
maximal cliques sharing the same extra vertex not in K. By Lemma 3.1(h),
they cannot share another vertex, without loss of generality say Mac and
share the same extra vertex rq. For all i,j E {a, b, c, d}, let Py = My 0 K. It
follows that vertices in {iq} U V(Pac) U V(Pm) form a larger clique containing
the clique formed by {iq} U V(Pac). Since Mac is maximal, it cannot be the .
clique composed of vertices in {rq} U V(Pac). Thus, Mac must contain another
vertex, say v2. Similarly, vertices in {ui} U V(Pac) U V(Pbd) form a larger clique
containing the clique formed by {rq} U V(Pbd)', hence, M^a contains another-,
vertex, say u3. If v3 is the same as v2, by the same argument as above, Mbd must
contain another extra vertex, which must eventually be a different vertex from
v2. Hence, we can assume that v3 is different from v2. Now, let u4 and v5 be
extra vertices of Mab and Mad, respectively. Since edges ab and ad share a, by:
Lemma 3.1(h), n4 7^ v3. Furthermore, ab and ad share a vertex with both ac
and bd; hence, ^ {vi,V2,v3}.
Next let u be an extra vertex of Mbc outside K. Then u cannot be rq, v2, v3
or Vi because be shares a vertex with ac, bd and ab. If u is not v3, we have six-
different extra vertices as desired. If u is v3, vertices in {u5} U V(Pbc) U V(Pad)
form a larger clique containing the clique formed by {^5} U V(Pbc)', hence, My-- -
36
must contain at least one more vertex outside {v\, v2, v^, u4, u5}; thus, we get the
sixth extra vertex. Hence, there are at least six extra vertices not in K.
Theorem 3.3 The minimum number of vertices of graphs with at least two
maximal-clique partitions of different sizes is 10.
Proof Suppose the theorem is not true. Let G be a graph of at most nine
vertices with at least two maximal-clique partitions of different sizes. Let Ad
and Af be two maximal-clique partitions of G of different sizes. If Ad and Af
have nonempty intersection, remove from G all cliques in the intersection to get
a graph G' of at most nine vertices with two maximal-clique partitions Ad\Af
and Af\A4. Because A4 and Af are different and they partition the edges of G,
neither AA\Af or Af\Ad is empty. Hence, without loss of generality, assume that
Ad and Af have empty intersection. Note that neither Ad nor Af can contain a
2-clique, because if a 2-clique is a maximal clique, it must be in every maximal-
clique partition. Hence, maximal cliques of G in Ad U Af are cliques of order at
least three. If Ad (or Af) contains a clique C of order at least five, then C is
not contained in Af (or Ad). Since by Theorem 3.2, G would have at least ten
vertices, this contradicts |y(G)| < 9. Hence, Ad and Af cannot contain cliques
of order greater than or equal to five. Thus, Ad and Af are composed of 3-cliques
and 4-cliques.
Let m and n be the numbers of 4-cliques in Ad and Af, respectively, and let s
and t be the numbers of 3-cliques in Ad and Af, respectively. Since Ad and Af are
clique partitions of G, counting the number of edges we have 6m + 3s = 6n + 2>t. '
37
If m n, then s t. Then \AA\ = m + s n + t = |JV|, which contradicts
|M | 7^ |AA|. Hence, m ^ n. We can assume without loss of generality that.
m> n. Then m > 1.
To prove the theorem, it suffices to show that there exists a 4-clique in AA
no two edges of which are covered by the same maximal clique in Af. If this
occurs, we can apply Theorem 3.2(n) to conclude that G has at least 4 + 6 = 10
vertices, contradicting |V(G)| < 9. Then it follows that the theorem is true.
Suppose that each 4-clique in AA contains two edges covered by the same
maximal clique in Af. Since an intersection between two cliques is a clique,
each 4-clique in AA must share at least a triangle with some maximal clique in
Af. Moreover, we can conclude by Lemma 3.1(i) that they share exactly one
triangle and that such a maximal clique in Af must be a 4-clique. Therefore,
we have shown that each 4-clique in A4 shares a triangle with a 4-clique in Af.
However, if each two 4-cliques in A4 share a triangle with the same 4-clique in
Af, they must share at least two vertices, contradicting Lemma 3.1 (ii). Thus,
each 4-clique in AA shares a triangle with different 4-cliques in Af. Hence, the
number of 4-cliques in AA is at most the number of 4-cliques in Af or m < n.
This contradicts m > n. Hence, we have the desired result and the theorem is
proved.
As L(K5) has ten vertices and two maximal-clique partitions of different
sizes, L(K5) is a graph having the minimum number of vertices satisfying this
property. Determining whether or not it is unique still remains an open problem.
38
The next section defines a natural graph operation called the glue operator.
It will be used to construct our graphs in Section 3.3 and Chapter 4. *
3.2 The Glue Operator
Let Gi and G2 be any two graphs. If there exist H\ C G\ and H2 C G2 such
that Hi = H2 with an isomorphism /, then we will denote by G\ G2 the
IT* Â£*Â£
graph that results from combining G\ with G2 by identifying H\ and H2 with,
respect to the isomorphism / between Hi and H2. We call this the glued graph
of Gi and G2 at Hi and H2 with respect to f.
Example 3.1 Let Hi and H2 be subgraphs of G\ and G2, respectively, where
Hi = H2 as in Figure 3.1:
G2
Figure 3.1: Hi = A(l, 2,3) C Gi and H2 = A (a, 6, c) C G2
Consider three isomorphisms between Hi and H2, f, g, and h, as follows:
/(l) = a, /(2) = b, /(3) = c,
0(1) = b, g{2) = c, g{3) = a, and
ih=fi-h
1
a
39
h(l) = c, h(2) = b, h(3) = a. Then we have:
Gi O G2
Gx O G2
Hi=gH2
Gi o
H^hH2
g2
Example 1 shows that different isomorphisms could give different or the
same result. However, in some cases it is possible that all isomorphisms give the
same resulting graph. The next example will illustrate this fact.
Example 3.2 Consider the following Hi C G\ and H2 C G2 as Figure 3.2.
G i G2
Figure 3.2: Hi = A(l, 2,3) C G i and H2 = A (a, b, c) C G2
There are six isomorphisms between Hi and H2, but all of them give the
40
same graph as in Figure 3.3:
Figure 3.3: The unique resulting graph
In this particular case, we do not need to specify an isomorphism in the
notation representing the glued graph, i.e., / can be omitted from the nota- .
tion without ambiguity. Hence, the glued graph notation can be written as
Gl O G2.
Hi^H2
Generally, a number of graphs with the isomorphic subgraphs can be glued
together at the same time.
Definition 3.1 For = 1,2,..., n, let Hi be a subgraph of Gi such that Hi = HjS
for all i,j G {1,2, ...,n}. If gluing all Gi together at H gives the isomor-
phic resulting graph, then write <Â£> (G'i, G2,..., Gn) as a notation fort
((((?! O G2)
Hi^H2
<Â£>
H2H3
-1 sjf
Gn)-
Now we will investigate some properties of graph gluing.
41
Theorem 3.4 Let Hi and H2 be subgraphs ofG\ andG2, respectively, and Hi =:
H2 for an arbitrary isomorphism f. The number of vertices in Gi <*> G2 is
|H(Gi)| + |V(G2)| \V(Hi)\ where i = lorS.
Proof Because Hi and H2 are identified, they are counted twice in the
glued graph.
Definition 3.2 Let C(G) be the set of all cliques and M{G) be the set of all
maximal cliques in a graph G.
Theorem 3.5 Let Gi G2 be an arbitrary graph resulting from gluing Gi
and G2 at any isomorphic subgraphs Hi = H2 with respect to any of their iso-
morphisms. Then
C(Gi G2) = C{Gi) U C(G2)
Proof Because Gi and G2 are subgraphs of Gi G2, C(Gi) C C(G\ G2)
and C(G2) C C{G\ O G2). Hence, C{Gf) UC(G2) C C(Gi ~~ G2). Conversely,:~~
let C G C(Gi G2). Note that if v e V(Gi \ Hi) and u E V(G2 \ H2),
then v is not adjacent to u. Hence, C E C(Gi) or C E C(G2). Therefore,
C(Gi G2) = C(Gi) U C(G2). m
That is, graph gluing does not create any new cliques or destroy any cliques
in the original graphs, but it identifies each pair of corresponding cliques in Hi
and H2. The next theorem determines the number of cliques in a glued graph.
42
Theorem 3.6 Let Gi G2 be an arbitrary graph resulting from gluing Gv
and G'2 at any isomorphic subgraphs Hi = H2 with respect to any of their iso-
morphisms. Then
\C{Gx G2)\ = |C(G0| + |C(G2)| \C(Hi)\ where i = 1 or 2.
Proof
^(GiOGa)! = |C(G!)UC(G2)|
= |C(G1)| + |C(G2)|-|C(G1)nC(G2)|
= |C(G0| + |C(G2)| \C(Hi)\ where i = 1 or 2.
However, graph gluing may destroy the maximality of cliques. Consider the
next example.
Example 3.3 Let Hi and H2 be subgraphs of G\ and G2, respectively, where
Hi = H2 as in Figure 3.4:
G\ G2
Figure 3.4: Hi is not maximal in G1 whereas H2 is maximal in G2
43
A glued graph of Gx and G2 at Hx and H2 with respect to an isomorphism
is as follows:
H2 is a maximal triangle in G2. However, its copy in Gx <1> G2 is not
h^h2
maximal. Hence, graph gluing may destroy the maximality of a clique in the
original graph.
Theorem 3.7 Let Gx G2 he an arbitrary graph resulting from gluing Gx
and G2 at arbitrary isomorphic subgraphs Hx C Gx and H2 C G2 with respect to
any of their isomorphisms. Then
M(GX G2) c M(GX) U M(G2)
Moreover, Ai(Gx G2) = A4(GX) U J\4(G2) if and only if for any pair of
corresponding cliques Cx in Hx and C2 in H2) Cx is maximal in G\ and C2 is.
maximal in G2, or Cx is not maximal in Gx and C2 is not maximal in G2.
Proof Let M be a maximal clique in A4(GX G2). Since A4(GX <
> G2) C C(Gx G2), by Theorem 3.5, either M Â£ C(GX) or M e C(G2).
Assume M e C(Gj), for = 1 or 2. Because Gi C Gx G2 and M is maximal
in Gi * G2, then M is maximal in Gj. Therefore, M Â£ M.{Gi) for i = 1 or 2;*
i.e., M Â£ M(GX) U M(G2).
Now, to show a necessary and sufficient condition for equality, it suffices to
show a necessary and sufficient condition for Ad(Gi)UAf (G2) C Af (Gx G2). ;
(=y>) Assume there exists a clique Cx in Hx that is maximal in Gx, but its
44
corresponding clique C2 in H2 is not maximal in G2. Then there exists a larger
clique X containing C2. It follows that X contains C\ in G\ G2. Hence, Ci
is not maximal in Gi O G2. Thus, C E M.(Gi), but C\ 0 M.{G\ G2), i.e.,
M{Gt)UM{G2)%M{G1oG2).
(
and C2 are maximal in G'i and G2, respectively, or C\ and C2 are not maximal in
G\ and G2, respectively. Let C E M(Gi) U M{G2). Without loss of generality,,
assume C E M.(Gi), i.e., C is maximal in G\. If C contains a vertex outside
then C is also maximal in Gi G2 because gluing does not effect any
vertices outside Hi. Thus, assume C is in Hi. Let C' be the corresponding
clique of C in H2. Since C is maximal in Gi, no vertex in Gi \ C is adjacent
to all vertices of C. By the assumption, C' is also maximal in G2. Then no
vertex in G2 \ C is adjacent to all vertices of C'. Hence, identifying C and C
yields that C is maximal in Gi * G2. Therefore, C E M.(Gi G2). Hence,*
M(Gi)UM{G2) c M{Gi <3>G2). m
Theorem 3.8 Let Gi G2 be an arbitrary graph resulting from gluing G\
and G2 at any isomorphic subgraphs Hi C Gi and H2 C G2 with respect to any:
of their isomorphisms. Let A be the set of cliques in Hi that are maximal in Gi
and whose corresponding cliques are also maximal in G2. Let Bi be the set of
cliques in Hi that are maximal in Gi but whose corresponding cliques in H2 are.
not maximal in G2. Let B2 be the set of cliques in H2 that are maximal in G2
but whose corresponding cliques in Hi are not maximal in Gi- Then
\M{Gi o G2)| = |Ad(Gi)| + \M(G2)\-\A\ \Bi\- \B2\.
45
Proof We can derive the number of cliques in the glued graph A4(GX <
> G2) by discarding the number of cliques in |A4(Gi)| + |.A4(G2)| that are not
counted in \M.{G\ G2)|. The result follows directly from Theorem 3.7. If
both cliques of a pair of corresponding cliques are maximal, they are counted
twice in the glued graph. Hence, one of them must be discarded by being in A.
If a clique G is maximal in one original graph while its corresponding clique is
not maximal in the other original graph, then C is not maximal in the glued
graph. Hence, it will be discarded by being in either Bx or B2.
Theorem 3.9 The glued graph of two clique-inseparable graphs is clique-
inseparable.
Proof Let Gx and G2 be graphs. Let Gx G2 be the glued graph between
Gx and G2 at Hx C Gx and Hi C G2. Suppose Gx G2 is clique-separable.
That is, there exists a proper nonempty subgraph H of Gx G2 separating
cliques in Gx G2. By Theorem 3.5, C(GX G2) = C(GX) UC(G2). Then it
follows that HDGi separates cliques in Gi and HnGi separates cliques in G2. If:
HrG\ Gi, then HC\G2 = H2 and it follows that H2 separates G2. Since Ii2 is;
a proper nonempty subgraph of G2, G2 is clique-separable. If H D Gx = 0, then
Hr\G2 is nonempty and Hf]G2 G2. Thus, G2 is clique-separable. Otherwise,
H is a proper nonempty subgraph of Gx. It follows that G'i is clique-separable.
3.3 Maximal-clique Partitions of k Different Sizes
When n > 5, L(Kn) is a clique-inseparable graph having maximal-clique
partitions of two different sizes. A disjoint union of a number of L(Kn) has
46
maximal-clique partitions of various sizes. The graph composed of a number of
L(Kn) all of which share a vertex is a connected graph with maximal-clique parti-
tions of various sizes. However, neither of these examples are clique-inseparable.
Pullman, Shank and Wallis (PSW) [32] showed a graph Hk with k maximal-
clique partitions of the same size by using k 1 copies of L(K^). By Theorem
2.3 and Theorem 3.9, we can conclude that Hk is a clique-inseparable graph.
The objective of this section is to construct a clique-inseparable graph with
maximal-clique partitions of k different sizes. Our construction is similar in
concept to PSWs construction. We will reintroduce Hk in terms of a construc-
tion using the glue operator for insight into the construction of a graph with k
maximal-clique partitions of k different sizes.
3.3.1 Graphs with k Maximal-clique Partitions
of the Same Size
From Lemma 2.2, L{K) has two maximal-clique partitions M.4 and 7V4
where Ma is the vertex-induced partition and JV4 is the triangle partition shown
in Figure 3.5. These two maximal-clique partitions have the same size, which is
4.
Figure 3.5: L(Ka) with two maximal-clique partitions, M4 and A/4
47
Consider k 1 copies of L(K4), called L(K4)1, L(K4)2,..., L(i^4)fe_1. For
z = 1,..., k 1, let M\ and Af\ be the vertex-induced partition and the triangle
partition of L(K4)1, respectively, and for each z, let Sj be any triangle in the.
triangle partition M\.
Let Si be the middle triangle in Figure 3.5, and for z y j {1,... ,k 1},
any isomorphism between Si and Sj gives the same resulting graph. Then it is..
well-defined to define
Hk = O (L(Ki)',L(Ki)21...,L(K1)k-1)
Si=S2=--=Sk
That is, Hk is the graph obtained by gluing k 1 copies of L(K4) together
at the middle triangle of each copy as shown in Figure 3.6. Rename the middle
triangle in the resulting graph Hk as S. Hence, S S\ ... = Sk-1 in Hk-
It is easy to see that for each 2, covering L(K4)1 \ S in Hk by Ml \ {5,}
yields a maximal-clique partition of Hk \ S. Let y = {S'} U Ui=i (-^4 \ {Si});
then y is a maximal-clique partition of Hk, and |T| = |{S}| + 1) =
1 + X)i=i (4 1) = 1 + 3k 3 = 3k 2. Now, we obtain other maximal
clique partitions of Hk. Fix t Â£ {1,..., k 1} and cover L(K4)t by its vertexT
induced partition Mi\. Note that Ml\ has already covered S. Since other copies
of L(K4) in Hk share S with L(K5y, it follows that the remaining edges inf
L(K4y \ {Sj} with i y t are in the unique maximal-clique partition which is
the collection of nine triangles in Ml \ {Sj}. That is, for t = 1,..., k 1, let .
= u UK,., (Ml \ {Si}). Thus, Xt is a maximal-clique partition of Hk,
and |^| = \M\\ + - 1) = 4 + E^W4 1) = 4 + 3(* 2) =,
4 + 3k 6 = 3k 2. Therefore, {T, Xlt..., Xk-i} is a collection of maximal-
48
Figure 3.6: Hk
clique partitions of Hk, and each of them has size 3k 2. Moreover, since L(Kf)
is clique-inseparable (by Lemma 2.3) and the glued graph of clique-inseparable.
graphs is clique-inseparable (by Theorem 3.9), we have Hk is clique-inseparable.
Thus, we can conclude the following:
Theorem 3.10 (Theorem 3 in [32]) For any positive integer k, there exists
a graph with k maximal-clique partitions of the same size.
Proof K2 is a graph with one maximal-clique partition. When k> 2, then
Hk is a graph with k maximal-clique partitions of the same size.
49
Corollary 3.2 For any positive integer k, there exists a clique-inseparable graph
with k maximal-clique partitions of the same size.
Proof Ki is clique-inseparable. When k > 2, by Theorem 2.3, Theorem
3.9, and Theorem 3.10, H& is a clique-inseparable graph with k maximal-clique
partitions of the same size.
3.3.2 Graphs with Maximal-clique Partitions of
k Different Sizes
For k> 2, let 14 be the graph constructed in this section having k maximal-
clique partitions of k different sizes. Similar to the construction of Hk, V/- will'
be obtained by gluing k 1 graphs. Since we need the target graph to have
maximal-clique partitions of different sizes, we will glue graphs with maximal-
clique partitions of different sizes. Recall from Section 2.3, for an integer i > 5,
L(Ki) has two maximal-clique partitions of two different sizes. This is the vital
property to get our target graph.
The graph 14 will be constructed from and L(Kk+3), a
total of k 1 graphs. Recall that A* is the triangle partition of L(Kf). For
1 = 5, ...,Â£; + 3, let A, be any triangle in J\ft. We will glue the above k 1
graphs together at Ff. Since L(Kn) is a vertex transitive graph, all isomorphisms
between Ri and Rj, where i ^ j, give the isomorphic graphs. Thus,
14 = O (L(ATS), L(K6),..., L(Kk+3))
R5^Re^...^Rk+3
is well-defined. Rename the triangle representing all Ri in the glued graph 14
as R. So, R = R5 = ... = Rk+3 in 14.
50
Theorem 3.11 For k > 2, 14 has k maximal-clique partitions of k different ;
sizes.
Proof It is easy to see that for each i = 5,..., k+3, covering L(Ki)\Ri in 14
by Afi\{R{} yields a maximal-clique partition of Vk\R. Let y = {i?}UUi=5 (-A4\ .
then y is a maximal-clique partition of 14, and by Lemma 2.2, |T| = .
K-R}i+EhhiMi -1)=i+-1)=es - 2).
Next we will obtain other maximal-clique partitions of T4- Fix t G
{5,..., k + 3}. Cover L(Kt) in 14 by its vertex-induced partition Alt, then
jR in 14 has already been covered by A4t. Since L(Ki) where i t in 14 share R '
with L(Kt), it follows that the remaining edges in L(Ki) \ {Iff} are partitioned :
by the unique maximal-clique partition which is the collection of triangles in
Afi \ That is, for t = 5,..., k + 3, let Xt Mt U (J^i=5(A/'i \ {A^});
then Xt is a maximal-clique partition of 14 and by Lemma 2.2, \Xt\ = |Adt| +
=t+Eh3.-B(a^a-D=t+EtyÂ¥,lfi=Â¥=a-^-2).
Furthermore, there are only two ways to partition edges in L(Kt) \ St by its
maximal cliques. One way uses cliques in M.t and the other uses cliques in A/i,"-.
and they induce maximal-clique partitions of 14 as mentioned above. Therefore,
{T, X5,..., Xk+} is the collection of all k maximal-clique partitions of Vk. 1'
6
6 6
maximal-clique partitions, and they all have different sizes.
We have |T| \Xt\ because for i > 5, i ^ .Lh.Tl, anq |^| ^ |^.| because
for i 7^ j G {5, ...,k + 3}, ^ Hence, T4 has k different:
51
Theorem 3.12 For any positive integer k, there exists a clique-inseparable,
graph with k maximal-clique partitions, and they all have different sizes.
Proof K2 is a clique-inseparable graph with one maximal-clique partition.
Since for each natural number n, L(Kn) is clique-inseparable (by Lemma 2.3),
and the glued graph of clique-inseparable graphs is clique-inseparable (by The-
orem 3.9), we have 14 is clique-inseparable for k > 2. Therefore, by Theorem
3.11, for k > 2,14 is a clique-inseparable graph with k maximal-clique partitions
of k different sizes.
52
4. Graphs with cc cp< mcp
The rest of the dissertation emphasizes the three clique parameters cc, cp and
mcp. Since a clique partition is a clique covering, cc < cp. Since a maximal-
clique partition is a clique partition, cp < mcp. Hence, it is always true that
the three clique parameters of a graph satisfy cc < cp < mcp. These clique
parameters of a graph are not always equal. However, all graphs of at most
nine vertices have the same three clique parameter values. This fact was proved
by Monson in her Ph.D. Dissertation in 1995 [22]. Thus, the three parameters
could be different when a graph has at least ten vertices. From Chapter 2, if
a line graph has a maximal-clique partition, it has cc = cp = mcp. Interval
graphs [20] and graphs with norm at most 4 [32] are also examples of graphs
having cc = cp = mcp.
As cc < cp < mcp, there are three more relationships possible among the
three clique parameters, which are cc < cp = mcp, cc cp < mcp and cc <
cp < mcp. Monson found the graph of ten vertices with cc < cp = mcp shown
in Figure 4.1. This graph has cc = 8 < cp = mcp = 9. Since ten vertices is the
minimum number of vertices needed to get different values of clique parameters,
Monsons graph is a graph with the minimum number of vertices satisfying
cc < cp = mcp.
The question of the existence of graphs with cc = cp < mcp has been
investigated previously to no avail. In this chapter we solve this open problem:
by constructing an infinite family of graphs with cc = cp < mcp. We will-
53
Figure 4.1: Monsons graph
start by constructing our first target graph U* in Section 4.1. Using the glue
operator we generalize this construction to obtain a family of graphs satisfying
cc = cp < mcp. It will be shown in Section 4.3 that the smallest graph among-
those constructed in this fashion has 68 vertices and 234 edges.
4.1 Our First Target Graph
In this chapter we refer to graphs satisfying cc = cp < mcp as target graphs.
Let U* be our first target graph. It will be constructed by gluing 12 copies
of L(K5) to a graph called B. The graph B is an extension of another graph <
L. Graphs L and B are constructed to have some special properties so that
B, glued with a number of L(K5), gives the target graph U* with the desired
property cc = cp < mcp. .p
54
4.1.1 The Construction
Definition 4.1 The notation Ki^{a : b,c,d) represents the complete bipartite '
graph with bipartition {a} and {b, c, d}.
4.1.1.1 The Graph L
do
Figure 4.2: The link graph L
Let L be the graph with 20 vertices and 36 edges as in Figure 4.2. Two
important characteristics of L are stated in Lemma 4.1. They are keys to getting
the target graph U*.
55
Lemma 4.1 (Characteristics of L)
(i) E(L) can be partitioned into 12 triangles.
(ii) E{L) can be partitioned into 12 induced subgraphs KXt3, named Aq, .... Axx
where for all 0 < i, j < 11, Ai and Aj have at most one vertex in common.
Proof () Here is the list of 12 triangles partitioning E(L):
Y0 = A(a0,b0>c0) I4 = A(a0, b3, d3) Y8 = A(a0, bx, ex)
Yx A(ax, bx, cx) Y5 = A(ax, bo, do) Yg A(ax, 621 Â£2)
Y2 = A(fl2, b2, c2) Y6 = A(a2, bx, dx) Yio = A(a2, b8, e8)
Y3 = A(a3,b3,c3) Y7 = A(a3, b2, d2) Yxx = A(a3, bo, e0).
Let y = {Yi : i = 0,..., 11} be the set composed of 12 triangles partitioning
E(L). Hence, ^ is a clique partition of L. Figure 4.3 shows the partition of
E{L) into 12 triangles.
Figure 4.3: The partition of E(L) into 12 triangles
56
(h) The edge set of L can be partitioned into 12 copies of K\>3 as follows:
A0 Kit3(b0 : c0, d0, e0) A4 = -Ki)3(a0 : b\, c0, d3) A8 = Kii3(a0 : b3, b0, ei)
A\ = -Ki,3(&i : Ci, di, ei) A5 = Kii3(ai : &2; ci, do) Ag = ' bo, b\, e*
A2 = Ki,zip2 ' C2, d2, e2) A6 = K4i3(a2 : 63, C2, di) A10 = -Ki,3(a2 : &ii ^2, Â£3)*
A3 = Ki 3(b3 : C3, d3, e3) A7 = ^1,3(03 : ^0, C3, d-2) An = ^1,3(03 : 62, 63, eo)
Figure 4.4 illustrates A = {Aj : z = 0,..., 11} partitioning E(L). Further-
more, any two members of A have at most one vertex in common. .. v
Figure 4.4: The partition of E(L) into 12 copies of dfli3
57
4.1.1.2 The Graph B
For % = 0,... 11, let T* be the graph that is the complement of Ai on the
vertex set of Aj. They are:
To = A(co, do, eo) T4 = A(61, Co, d3) T8 = A(63, bo, ei)
Ti = A(ci, di, ei) T5 = A(62,ci,do) Tg = A(b0,bi, e2)
T2 = A(c2, d2, e2) Tg = A(bz, c2, d\) T10 = A(b\,b2,ez)
T3 = A(c3, d3, e3) T7 A(bo,Cz,d2) Tn = A(62, bz, eo)
Since A is an induced subgraph i^1;3 of L, the triangle T* does not contain any
edges of L. Since for any i ^ j E {0,..., 11}, Ai and A,- share at most one
vertex, T* and Tj cannot share an edge.
Figure 4.5: 5 = L U T0 U Tx U ... U Tn = X0 U ... U Xu
58
Let T {Ti'.i 0,..., 11}. Now, B is constructed by adding all triangles
Ti in T to L. Then B has the same vertex set as L which has 20 vertices, and
since B contains 36 edges from L and 36 edges from the 12 triangles in T, then .
B has a total of 72 edges. B is illustrated in Figure 4.5.
Now, for i = 0,..., 11, define Xi = A* UILet X {Xi : i = 0,..., 11},
then X is a collection of 4-cliques that is a clique partition of B.
4.1.1.3 A Target Graph U*
For each i 0,..., 11, let L(K5y be the zth copy of L(K5). Recall from
Section 2.3 that L(K^) has two maximal-clique partitions, the vertex-induced
partition and the triangle partition. Let Si be a triangle in the triangle partition
of L(K5y. For each i, L(K5)1 is glued to B at triangles Si and T*. Let U* be-
the resulting graph. That is,
U* = B{
L(K5)
To=So
<*> L(K5y
TiS5i
\
Tn=5ii
L(K5)n
An example of gluing L(K5)1 to B at Si and Ti is illustrated in Figure 4.6.
59
Figure 4.6: A copy of L(K5) glued to B at a triangle
Since for each i = 0,..., 11, L(K5)1 shares exactly three vertices with B,
the number of vertices of U* is |V(jB)| + 12 \V(L(K5))\ 12 \V(Kz)\ = 20-1-:
12 10 12 3 = 104. Also, U* can be considered to be the edge-disjoint union '
of 12 copies of L(K5) and L. Hence, the number of edges in U* is
\E(U*)\ = 12 \E(L{K5))\ + \E(L)\ = 12-30 + 36 = 396.
4.1.2 The Clique Numbers of U*
In this subsection, all three clique numbers cc(U*), cp(U*) and mcp(U*)
will be determined. The vertex-induced partition of each copy of L(K5) and
y composed of triangles Y{ partitioning L will determine cc(U*) and cp(U*)y
while mcp(U*) can be deduced from the triangle partition of each copy of L(K5) -
together with A = {A : i = 0,..., 11} in B.
60
Lemma 4.2 cp(U*) < 72.
Proof Since U* is an edge-disjoint union of subgraphs L(K5), L(Ks)1,
..., L(K5)u and L, the union of clique partitions of these subgraphs is a clique
partition of U*. For each i = 0,..., 11, let M.i be the vertex-induced partition
of L(K5)\ Recall that y = {Yi : % = 0,..., 11} composed of 12 triangles
partitioning L (in Lemma 4.1(i)) is a clique partition of L.
Hence, let V = Mq U M\ U ... U M.n U y. Then V is a clique partition of
U* with |P| = |A40| T l-^il + + |A4n| + |T| = 5 + 5 + ... + 5+12 = 72.
s 1 v y
12
Thus, U* has a clique partition V of size 72. Therefore, cp(U*) < 72.
Lemma 4.3 cc(U*) > 72.
Proof Let C be any clique covering of U*. First note that {L(K5) \
B, L(K5y \ B,..., L(K5)n \ B, L} is a collection of pairwise edge-disjoint sub-
graphs of U*, and there is no clique in U* covering two edges from different
subgraphs. Hence,
|Â£-| > tiq + rii + ... + nii + l
where for i=0,.. ,11, nt is the minimum number of cliques in U* covering edges
in L(K5y \ B, and l is the minimum number of cliques in U* covering edges in
L.
Since the largest clique in L(K5y \ B has order 4, each clique can cover at
most six edges of L(K5y \ B. Because L(K$y \ B has 27 edges, it needs at
61
least five cliques to cover its edges, i.e., rq > 5 for all i = 0,. ..,11. Thus,
\C\ > 5 + ... + 5 -\-l.
i i vv,
12
do
a\
d2
Figure 4.7: 12 cliques needed to cover the 12 thick edges
Note that no two of the 12 edges in Figure 4.7 are contained in the same
clique in U*. In other words, there is no clique that covers any two of these 12
edges at the same time. Hence, L needs at least 12 cliques to cover all its edges,
and l > 12. Hence, \C\ > 5 + 5 + ... + 5+12 = 60 + 12 = 72 cliques. Since C is
12
arbitrary, cc(U*) > 72.
62
Lemma 4.4 mcp(U*) = 120.
Proof First note that not every clique in the partition V defined in
Lemma 4.2 is maximal in U*. For example, Ys G V, but Y8 = A(o0,6i,e1) C .
E3(a0, bi,ei, b0) in U*. Since V uses the vertex-induced partition to cover L(K5)1,
now we will cover L(K5)1 by using the triangle partition. For i = 0,..., 11, let
Mi be the triangle partition of L(K5)1. Then Mi is composed of ten triangles:
Recall that Si G Mi. Because for each i, B is glued with L(K5)1 at T{ and S{, .
we have that U* is a disjoint union of B and L(K5y \ Si : i = 0,..., 11.
Let M[ = Ml\{Sl}. Then M' is a clique partition of L(K5)l\Si and \M(\ = 9.
From Subsection 4.1.1.2, X {Xi : i = 0,..., 11} is a collection of 4-cliques in
U* that partitions B. Let Mi = YUA/oUA/}U...UM[x. Since Xi and nine
triangles in Mi\{Si} are maximal in U*, Mi is a maximal-clique partition of U*.
In fact Mi is the only maximal-clique partition of U*. Thus, mcp(U*) = \Mi\ =
\X\ + IA/'qI + |A/}| + ... + lA/j^l = 12 T 9 T T 9 = 12 + 108 = 120. ;
12
Theorem 4.1 There exists a graph U* with cc(U*) = cp(U*) < rncp(U*).
Proof Consider U* that has been constructed with 104 vertices and 396
edges. By Lemma 4.2 and Lemma 4.3, cp(U*) <72 < cc(U*). However, because 1
a clique partition is always a clique covering, cc(U*) is always at most cp(U*):
Hence, cc(U*) = cp(U*) = 72. By Lemma 4.4, mcp(U*) = 120. Therefore,
cc(U*) = cp(U*) < mcp(U*). .
63
4.2 A Family of Target Graphs
Two characteristics of the graph L in Lemma 4.1 and the property of L(K5)
that it has two maximal-clique partitions of different sizes are crucial to obtain-
ing U* with cc = cp < mcp. Hence, other graphs with cc = cp < mcp can
possibly be constructed in the same fashion as in the last section by general-
izing U* using two approaches. The first approach is replacing L(K5) by any
graph with two maximal-clique partitions of different sizes, for example L(Kn)
when n > 5. The other one is generalizing L in a way that preserves the two
characteristics in Lemma 4.1.
4.2.1 Link Graphs Lk and Base Graphs Bk
For k > 3, let Lk be the graph defined as follows:
V{Lk) = {vi : v = a, b, c, d, e, and i = 0,1,..., k 1}.
E{Lk) {UjCj, &idil(mod k) j i^i+l(mod k) > Oi^ij l(mod k) > (mod k) 1 bjCjj
bidi, bi6i : % = 0,1,..., k 1}.
Therefore, Lk has 5k vertices and 9k edges. Lk is illustrated in Figure 4.8.
We call Lk a link graph.
64
Figure 4.8: The link graph Lk
When k 4, L4 = L, i.e., Lk is a generalization of L. The following two
lemmas give characteristics of Lk analogous to those of L in Lemma 4.1.
Lemma 4.5 For k > 3, E(Lk) can be partitioned, into 3k copies of 3-cliques
which are Yk>i : i = 0,1,..., 3k 1, where for i = 0,1,..., k 1,
Yk,i
Yk ,k+i = A(oi> b
il(mod k)t d>ii (mod k))
Yk ,2k+i A(Oj, k)-> &i+l(mod k))
Let 34 = {Ykti : i = 0,..., 3k 1}. Then 34 is a clique partition of Lk.
65
Lemma 4.6 For k > 3, E(Lk) can be partitioned into 3k copies of which
are Ak>i, i = 0,1,..., 3k l, where for i = 0,1,..., k 1,
Ak,i = #1,3 (bi : Cii d{, ef)
-4fe,fe+i = #1,3 (ai bi+l(mod k)i Qi dil(mod kf)
-Tfc,2fc+i = #1,3 (ai bil(mod k)i bit ^i+l(mod kf)
Moreover, Ak {Ak,i : i = 0,1,..., 3fc 1} has the property that any two
members of Ak have at most one vertex in common.
Next, the link graph Lk will be extended to a base graph Bk. For k > 3,
i 0,..., 3k 1, let Tkti be the graph complement of Akti on the vertex set of
A^ That is, for i = 0,1,..., k 1,
Tk'k+i ^(^i+l(mod k)i Qj di_i(mod k))
l(mod k); Ci+l(mod k))-
For each i, Akti is an induced of Lk- So, Tk>i is a triangle that does not
contain any edges in Lk. Since for any i A 3 Â£ {0,..., 3k 1}, Ak>i and Akj
share at most one vertex, Tk>i and Tkj do not share an edge. For k > 3, let
Tk = {Tkj : i = 0,..., 3k 1}. Bk is constructed by adding all triangles in Tj. to
Lk- Then Bk has the same vertex set as Lk which contains 5k vertices, and Bk
contains 9k edges from Lk and 9k more edges from the 3k triangles in Tk) so,
Bk has a total of 18k edges. For future reference, the numbers of vertices and
edges in Lk and Bk are summarized in the next Lemma.
66
Lemma 4.7 For k > 3,
(i) Lk has 5k vertices and 9k edges.
(ii) Bk has bk vertices and 18k edges.
As in the previous section, For k > 3, i = 0,..., 3k 1, define Xk*
Akji U Tkii. Then Xkji is a 4-clique. Let Xk = {Xkii : i = 0,..., 3k 1}. Thus,'*
Xk is a clique partition of Bk. When k > 4, for i = 0,..., k 1, Xkj is maximal:
in Bk. This fact will be shown in the next Lemma.
Lemma 4.8 For k > 4, Xk = {Xk*
partition of Bk.*
Proof Let k > 4. Let t G {0,..., 3k 1}. Consider Xkit in Bk. Let
uG V(Bk)\V(Xk>t).
Case 1 G {6o> - > x}- Say v bi. First note that bi is adjacent to
bj if and only if j = i l(mod k) or j = i + l(mod k). If Xkit contains bj
where j ^ i l(mod k) and j ^ i + l(mod k), then v is not adjacent to bj.
Thus, Xk t U {u} is not a clique. Otherwise, Xkjt does not contain bj where
j ^ i l(mod k) or j ^ i + l(mod k). From the definition of Xk>t in Bk where
k > 4, the only possible form for Xkt is M(bj, Cj,dj, Cj) where j = z+l(mod k) or
j = i l(mod k). However, bi is not adjacent to either Cj+i(moci k) or Ci_i(mod k)-
Hence, v = bi is not adjacent to all vertices of Xk)t. Hence, the induced subgraph
on V{Xk>t) U {u} is not a clique.
Case 2 v Â£ {&o, ,bk-1}- Then v is contained in exactly two members
of Ak = {Ak i : i = 0,..., 3k 1}, say Ak>p and Akiq where p A Q- Suppose.
v is adjacent to all vertices in V(Xk:t). By the Pigeon Hole Principle, at least
67
one of {AkiP, Ak,q} contains at least two vertices in V(Xk:t)- Without loss of
generality say it is AktP. This yields that Ak>p and At share at least two vertices,
contradicting the property of Ak in Lemma 4.6. Hence, v cannot be adjacent to
all vertices in V(Xkit).
Hence, for any vertex v in Bk \ Xkit, vertex v cannot be combined with Xk
to get a larger clique containing Xkit. Therefore, Xkit is maximal in Bk. Since
Xk = {Xki : i = 0,..., 3k 1} is a clique partition of Bk, we have proved Xk is
a maximal-clique partition of Bk.
4.2.2 Target Graphs Uk
For any integer k > 3, let Uk be the target graph resulting from gluing Bk
to 3k copies of L(K5). For i = 0,1,..., 3k 1, let L(K5)* be the ith copy of
L(K5). Let Si be any triangle in the triangle partition of L(fF5)h Recall that
Tk>i is a triangle added to Lk to get Bk. Define
/
Tk,oSo
L(K5)
Uk = Bk<
Tk,i=Si
L(K5y
0 LiKA-1
Tk,3k-1S3k-1
\
68
Lemma 4.9 For k >3, Uk has 26k vertices and 99k edges.
Proof Since Uk is the graph that results from gluing copies of L(K5) at
triangles of Bk, by Lemma 4.7 the number of vertices in Uk is
\V(Bk)\ + 3k \V(L(K5))\ 3k \V(K3)\ = 5k + 3k 10 3k 3 = 26k.
Since Uk can be considered to be the edge-disjoint union of L and 3k copies
of L(K5), the number of edges in Uk is
\E(Lk)\ + 3k \E(L(K5))\ = 9k + 3k 30 = 99k.
Lemma 4.10 For k> 3, cp(Uk) < 18k.
Proof Similar to the proof in Lemma 4.2, for each % = 0,..., 3k 1, let M.i
be the vertex-induced partition of L(K5)1. Let Tk {Tkti : i = 0,..., 3k 1}
partitioning E(Lk). Let Vk = Tk U A4o U... U Then Vk is a clique partb
tionof[/fc. Moreover, \Vk\ = \'Tk\ + \MQ\ +.. + \M3k-i\ = 3A:+5 + 5 + ... + 5 =
3 k
3k + 15k = 18&;. Hence, cp{Uk) < 18/c.
If n is a number of edges in a graph G so that no pair of edges is contained in
the same clique of G, then the clique covering number of G is at least n. Hence,
finding the maximum such n is the dual problem for finding the minimum size
of clique coverings of G.
69
Definition 4.2 Let e and / be any two edges in a graph G. If there is no clique
in G containing both e and /, then e and / are clique-independent with respect
to G.
ao ai
02
Figure 4.9: 3k pairwise clique-independent edges
Although the graph in Figure 4.9 does not show all edges in Bk, the set of
3k thick edges in the figure demonstrates 3k pairwise clique-independent edges-
with respect to Bk, i.e., there is no clique in Bk that can cover any two thick
edges in Figure 4.9.
70
Lemma 4.11 For k > 3, Lk contains a set of 3k pairwise clique-independent
edges with respect to Bk-
Proof Let Ik {c-ibi, aidii(mod k)j i(mod k) i 0,..., k 1}. Let 6 / /
be in Ik.
Case 1 3z Â£ {0,..., a* Â£ e and Oi Â£ /. Since di_i(mod k) is not adjacent
to ej+i(mod k), we have e and / are clique-independent with respect to
Case 2 3z 3j Â£ {0,..., k}, ai Â£ e and aj Â£ /. Since when i ^ j, ai is not
adjacent to a^, then e and / are clique-independent with respect to Bk-
Case 3 3z Â£ {0,..., k} Vj Â£ {0,, A;}, a, Â£ e but a5- ^ /. Note that a* is
not adjacent to Cj when j i, di_1(mocj k) is not adjacent to &i+i(mod k), and Cj is
not adjacent to ei+i(mo
to Bk.
Case 4 Vz Â£ {0,..., k}, a* ^ e and a* ^ /. Since c* is not adjacent to c,-
when z ^ j, then e and / are clique-independent with respect to Bk-
Since the above four cases include all possibilities, the lemma is proved.
Lemma 4.12 For k > 3, cc(Uk) > ISA;.
Proof Let Ck be a clique covering of Uk First note that {L(K5) \ Bk,
L{K$)1 \ Bk,---, L(if5)3fc_1 \ Bk, Lk} is a collection of pairwise edge-disjoint
subgraphs of Uk, and there is no clique in Uk covering any two edges from
different ones of these subgraphs. Hence,
\Ck\ > zzo + zii + + n^k-i + l
where for z = 0,..., 3k 1, rq is the minimum number of cliques in Uk covering.
71
edges in L(K5)1 \ Bk, and l is the minimum number of cliques in Uk covering,
edges in Lfc.
Since for each i = 0,... ,3k 1, the largest clique in L(K5y \ Bk has order
4, each clique can cover at most six edges of L(K5)l \ Bk. Because L(K$)1 \ Bk
has 27 edges, it needs at least five cliques to cover its edges, i.e., n; > 5 for all
i = 0,..., 11. Thus, \Ck\ ^ 5 T T 5 -f-l.
3 k
By Lemma 4.11, Lk contains 3k pairwise clique-independent edges with
respect to Bk. Besides, since there is no clique in Uk containing edges in both .
Bk and in Uk\Bk, these 3k edges also form a set of 3k pairwise clique-independent
edges with respect to Uk- Thus, l > 3k. Hence, \Ck\ > 5 + 5 + ... -I- 5 +3k =
v------v------y
3 k
15k + 3k = 18k. Since Ck is arbitrary, cc(Uk) > 18k. m
By Lemma 4.8, for k > 4, Bk has a maximal-clique partition which induces
a maximal-clique partition of Uk- The maximal-clique partition number of Uk
will be discussed in the next Lemma.
Lemma 4.13 For k > 4, mcp(Uk) = 30A:.
Proof First note that Vk in Lemma 4.10 is not a maximal-clique partition of
Uk because Y2k = A(a0, b\,ei) C IE(a0, &i, elf b0) in Uk, but Y% G Vk- We can get
a maximal-clique partition of Uk similarly to Lemma 4.4. For i = 0,..., 3k 1,
let Mi be the triangle partition of L(K5y. Then Mi is composed of ten triangles.
Recall that Si G Mi- Since for each i, Bk is glued with L(K5y at Tkyi and Si, we
have Uk is a disjoint union of Bk and L(K5)1 \ Si : i = 0,..., 3k 1.
72
For i = 0,..., 3k 1, let J\f! = A/i \ {5;}. Then Af( is a clique partition
of L(K5y \ Si and \J\f(\ = 9. By Lemma 4.8, Xk = {Xkii : i = 0,..., 3k 1}
is a maximal-clique partition of Bk. Let Mk = Xk U U Af[ U ... U Af3k_p-
Since Xkii and nine triangles in Hi \ {Fj} are maximal in Uk, we have that A4k
is a maximal-clique partition of Uk, and in fact Aik is the only maximal-clique ,
partition of Uk. Thus, mcp(Uk) = \Mk\ = \Xk\ + |A/2| + |A/]| + ... + |A/^a,_1 | =
3 k | 9 I... | 9 = 3k + 27 k = 30 A;.
Figure 4.10: The base graph B$ and its subgraph L3 represented by the thick .
edges
The graphs Lz and B?J are shown in Figure 4.10. Consider T3 6 = Ki^(a0 :
b2, b0, ei) and T3|6 = A(62, b0, ei) in B3. Hence, X3|6 = K(a0, b2, bQ, ex). However,,
bi is adjacent to all vertices in AT3 6; so, X3 e is contained in a 5-clique. Hence;-
X3j6 is not maximal in B3. It follows that B3 does not have a maximal-clique
partition and neither does U3. Hence, U3 does not have the property cc = cp <.
3 k
73
mcp. Therefore, U4, which is our first target graph U* described in Section 4.1,
is the smallest graph in this family.
Theorem 4.2 There exist infinitely many graphs with cc = cp < mcp.
Proof Consider Uk, for k > 4. By Lemma 4.10 and Lemma 4.12,
cp(Uk) < 18k < cc(Uk) However, because a clique partition is always a
clique covering, cc(Uk) is always at most cp(Uk) Thus, cc(Uk) = cp(Uk). By
Lemma 4.13, mcp(Uk) = 30k. Hence, for k > 4, cc(Uk) = cp{Uk) < mcp(Uk).
Let T = {Uk : k > 4}. Then T is a family of infinitely many graphs with
cc = cp < mcp. u
4.3 The Smaller Target Graphs
The fact that L(K5) has two maximal-clique partitions of different sizes is
an essential property for our construction of target graphs in this fashion. By
Lemma 2.2, L(Kn), for all n > 5, has two maximal-clique partitions. So, they
can be used to replace L(K5) in the construction. Hence, the graph constructed
by gluing Bk with any 3k graphs in {L(Kn) : n > 5} always has the property
of cc = cp < mcp. Now we are interested in finding a graph smaller than .
( or U*) that results from gluing B4 with 12 copies of L(K5). Because L(K4)
has two maximal-clique partitions, all copies of L(Ks) could be replaced by
L(Kfi) in the construction to obtain a graph with two clique partitions; one is
maximal but the other is not. However, unlike L(K5), which has two maximal- .
clique partitions of the same size, replacing all copies of L(K5) by L(K4) yields
74
a graph with cc = cp = mcp. However, it is not necessary to use all copies
of L(K5) to get cc = cp < mcp. Thus, the sizes of the target graphs can be
0 < d < 3k, let Uk,d be the graph resulted by gluing Bk to d copies of L(Ks) and
3k d copies of L{K). For i = 0,..., d 1, let L(K5y be the zth copy of L(K5),
and Si be a triangle in the triangle partition of L(K5)1. For i = d,..., 3k 1,
let L{Ki)1 be the (i d)th copy of L(K4), and Si be a triangle in the triangle
partition of L(i^4)1. Define
reduced by replacing some copies of L(K5) by L{KA) but not all. For k > 4 and
Tk,d-i=Sd-i
O LiKsY-1
Uk,d = Bk <
Tk,3k-1Ssk-l
L{KAyk~i
Note that if d 3k, Uk,zk = Uk-
75
Lemma 4.14 For k > 4 and 0 < d < 3k, Ukjd has 14k + 4d vertices and
45k + 18d edges.
Proof Since Uk,d is the glued graph of Bk with each copy of L(K5) and
L(Kf) at a triangle, then by Lemma 4.7, the number of vertices in Uk,d is
\V{Uk4)\ = \V(Bk)\ + d-\V(L(K5))\ + (3k-d)\V(L(K4))\-3k-\V(K3)\
= 5k + d 10 + (3fc d) 6 3k 3
= 5k + 10 d + 18 k 6d 9k
= 14k + 4 d.
The graph Uktd can be considered to be an edge-disjoint union of d copies of
L(K5), 3k d copies of L(K,\) and L. Hence, the number of edges in Uk,d is
\E(Uktd)\ = \E{Lk)\ + d-\E{L{Ks))\ + {3k-d)-\E{L{K))\
= 9/c + d 30 + (3k d) 12
= 9k + 30d + 36k-12d
= 45 A; + 18d.
Lemma 4.15 For k > 4 and 0 < d < 3k, let Mk,d be o. clique partition of Ukid
induced by the vertex-induced partitions of L(K5)1, i = 0,..., d 1 and L(/f4)-7,
j = d,... ,3k 1. Let Nk,d be a clique partition of Ukid induced by the triangle
partitions of L(K5)1, i = 0,...,d 1 and L{K$, j = d,... ,3k 1. Then
\Mktd\ = 15k + d and \Afktd\ = 12k + 6d.
Proof For i = 0,...,d 1 and for j = d,...,3k l, let M\ and M.\ be the
vertex-induced partition of L(K5y and L{K^)'J, respectively. Recall that Tk =
76
{Tm : i = 0,..., 3k -1}. Let Mk,d = TkUM5U...U Mdfl U U... U Mf~\
Then
\Mk,d\ = \Tk\ + |A*| + ...|.Mf1| + \Md\ + ... + |Mf"1|
= 3& + 5 + ... + 5 + 4 + ... + 4
'----V---' '---V----'
d 3kd
= 3k + 5d + 4(3A: d)
= 3k + 5d+12k-4d
= 15 k + d.
Next, for i = 0,..., d 1 and for j = d,..., 3k 1, let Ml and Ml be
the triangle partition of L(K5y and respectively. Recall that Xk =
{Xkti : i = 0,... ,3k 1}, Si e Ml, and Sj G M{. Let {Ml)' = Ml \ {S*} and
(Mi)' = Mi\{Sj}. Let Mu = Xiu(M)'u...u(Mt')'u(Mtyu.. .u(A/?-y
Then
i jvmi = i^i + i(jv?)'i + ---i(^1)'i + i(yf)'i + ---+i(jv?*-1)'i
= 3k + 9 + ... + 9 + 3 + ... + 3
V V
d 3kd
= 3k + 9d + 3{3k d)
= 3k + 9 d + 9 k 3d
= 12k+ 6d.
77
Theorem 4.3 For k > 4, if 0 < d < then cc(Ukid) = cp(Uk,d) =
mcp(Uk,d) = 12k + 6d. J/y < d < 3k, then cc(Uktd) = cp{Uk
Proof For integers k and d where k > 4 and 0 < d < 3k, similar to
the proof of Lemma 4.13, we can prove that Mk,d in Lemma 4.15 is the only
maximal-clique partition of Uktd- So, mcp(Ukid) = \Ffk,d\ = 12k + 6d.
However, both M.k^ and Afk,d in Lemma 4.15 are clique coverings and clique
partitions of Ukid The one with smaller size will determine cc(Uktd) and cp(Uktd)-
If 0 < d < y, then 15 k + d> 12 k + 6 d. Thus, \M.k,d\ > \Mk,d\- Hence, Mkyd
is a minimum clique covering and a minimum clique partition of Ukid Hence,
cc(Uktd) = cp(Ukjd) = mcp(Uk>d) = |A4,d| = 12fc + 6d.
If y < d < 3k, then 15k + d < 12k + 6d. Thus, \AAk^\ < |A4,d|- Hence,
M.ktd is a minimum clique covering and a minimum clique partition of Uk
Therefore, cc(Ukjd) = cp(Ukid) = = 15A; + d. Since 15k + d < 12k + 6d,
cc{Uk4) = cp(Uk4) < mcp(Ukid).
Theorem 4.4 T' = {Uktd : k > 4 and y < d < 3k} is a family of infinitely
many graphs with cc = cp < mcp.
Proof Immediate from Theorem 4.3.
Note that Uk^k = Uk. Recall that T = {Uk : k > 4} is defined in Theorem
4.2 and T' = {Ukid k > 4 and y < d < 3k} is defined in Theorem 4.4. Hence,
T CT and f74i3 is the smallest graph in T'. Thus, is the smallest possible
graph with cc= cp < mcp among graphs constructed in this fashion.
78
Theorem 4.5 There exists a graph of 68 vertices with cc = cp < mcp.
Proof By Lemma 4.14, f/4i3 has 14-4 + 4-3 = 68 vertices and 45-4 + 18-3 =
180 + 54 = 234 edges. By Theorem 4.3, cc([/4)3) = cp(f/4)3) = 15 4 + 3 = 63,
and mcp(t/4i3) = 12 4 + 6 3 = 66. Hence, cc(C/4i3) = cp(t/4|3) < mcp(L4|3).
We have solved the existence problem. However, there is no guarantee that
[/4)3 is the smallest possible graph with cc = cp < mcp. It remains an open,
question whether there exists a graph with cc= cp < mcp having fewer vertices
than I/4]3.
79
5. Clique Partitions of Graphs with Ten Vertices
This chapter continues the investigation of the three clique parameters cc, cp
and mcp. We know that many graphs do not have a maximal-clique partition.
Throughout this chapter, we will explore only graphs with a maximal-clique
partition. From Monsons Ph.D. Dissertation [22], we know that for any graph of
at most nine vertices with a maximal-clique partition, all three clique parameters
are the same, i.e., cc = cp mcp. Hence, ten is the smallest number that the
three parameters could have different values. Monson [22] found an example of
a graph of ten vertices with cp = mcp but different from cc. Thus, graphs with
cc < cp = mcp have a minimum number of ten vertices. For any graph G with,
a maximal-clique partition, if G has cp < mcp, then G must have at least two
clique partitions of different sizes and the partitions with the smallest cardinality
cannot be maximal-clique partitions. In Chapter 4, we found a family of graphs
with cc = cp < mcp. The smallest graph in the family has 68 vertices, which is
somewhat large. However, we do not know whether or not it has the minimum
number of vertices among graphs with cc cp < mcp. On the other hand,
there is an example of a graph on as few as 11 vertices with cc < cp < mcp.
Pullman, Shank and Wallis [32] asked whether or not there is such a graph with
fewer than eleven vertices. However, since Monson showed that any graph of
fewer than ten vertices has cc = cp = mcp [22], it is sufficient to answer the
open problem of Pullman, Shank and Wallis by investigating only graphs with ;
ten vertices. This chapter will confirm that there is no graph of ten vertices
80
with cp < map. Consequently, graphs with cc < cp < mcp have a minimum
of 11 vertices. From this we can conclude that any graph of ten vertices has a
minimum clique partition whose cliques are maximal or it has no maximal-clique
partition. In Section 5.1 we study characteristics of maximal-clique partitions
of graphs on ten vertices having clique partitions satisfying various properties.
Finally, the nonexistence of graphs having ten vertices and cp < mcp will be
investigated.
5.1 Ten Vertex Graphs with a Maximal-
Clique Partition
The maximal-clique partitions of graphs of ten vertices will be explored in
this section. These results will be used to prove the main theorem in the next
section.
Lemma 5.1 Every clique partition of a graph on ten vertices contains at most
five 4-cliques. Furthermore, if a clique partition of a graph G on ten vertices
contains exactly five 4-cliques, then G = L(K5).
Proof Let V be a clique partition of a graph G of ten vertices. Consider
any vertex v of G. Since G has ten vertices, v can be contained in at most three
4-cliques in V. If v is contained in three 4-cliques in V, then all ten vertices of
G are covered by these 4-cliques. Let K be a clique in V other than those three
4-cliques. Since every two cliques in V can share at most one vertex, K can
contain at most one vertex from each of those three 4-cliques. Thus, K contains
at most three vertices, that is, V cannot have other 4-cliques. Otherwise, every
vertex in G appears in at most two 4-cliques in V. Hence, ten vertices can be
81
used at most 10 2 = 20 times. Since one 4-clique contains four vertices, the :
number of 4-cliques in V is at most ^ = 5.
Furthermore, if V has five 4-cliques, then each vertex of G belongs to exactly
two 4-cliques. Since every two cliques in V can share at most one vertex, no two
vertices of G can belong to the same pair of 4-cliques in V. Labelling vertices of.
G according to the 4-cliques containing them gives a graph isomorphic to L{K~~
Lemma 5.2 If a graph has a vertex adjacent to all other vertices, then such a :~~
vertex must be in every clique of each maximal-clique partition of the graph.
Proof Let G be a graph with a vertex v adjacent to all other vertices. Sup-
pose the statement is not true for a maximal-clique partition M. of G, i.e., there
exists a clique C in M such that v C. Since, v is connected to every vertex
in C, then C V {u} (the join graph of C and {u}) is a larger clique containing
C, which contradicts the maximality of C.
Theorem 5.1 Let M be a maximal-clique partition of a graph with ten vertices.
If M. does not contain a 2-clique, then \M.\ <10.
Proof Let G be a graph of ten vertices with a maximal-clique partition
M.. Then \E(G)\ < (]2) = 45. Assume there is no 2-clique in Ai. If there is no
3-clique in Ai, then jAT| < \e*ka)\ = y < 10 as desired.
Now, assume that there exists a 3-clique in M, say A (a, b, c). Since A(a, b, c)
is maximal, none of the remaining seven vertices can be adjacent to all three
82
vertices in A (a, b, c). This yields |-E(G)| < 45 7 = 38.
Suppose |Ad| > 11. If Ad contains a clique of order 5 or more, the total
number of edges of G is minimized when the remaining ten cliques are 3-cliques.
Hence, 38 > |Â£?(G)| > \E(K5)\ +10 \E(K3)\ = 10 +10 3 = 40, a contradiction;
Thus, there is no clique of order 5 or more in Ad. If Ad contains two 4-cliques,
38 > \E(G)\ > 2 \E(K4)\ + 9 \E(K3)\ = 2 6 + 9 3 = 12 + 27 = 39, another-
contradiction. Therefore, M. contains at most one 4-clique, and the rest of its
cliques are 3-cliques.
Now if each of the seven vertices not in A(a, b, c) is adjacent to at most one
vertex of A (a, b, c), then |F(G)| < 45 2 7 = 45 14 = 31. Since the smallest
clique in Ad is a 3-clique, |Ad| < 10 as desired. Otherwise, there exists a vertex.
d adjacent to exactly two vertices of A(a,b,c). Without loss of generality, say
d +- a, d b but d c. Since A (a,b,d) shares an edge with A (a, 6, c) and
A (a, b, c) is in Ad, it follows that A(a, b, d) cannot be in Ad. So, there must be
two different maximal cliques C\ and C2 containing edges ad and bd, respectively. -
c
Figure 5.1: ad Â£ C\ and bd G C2
Because there is at most one 4-clique in Ad, then either of Ci,C2 is the
83
4-clique or neither of them is.
Case 1 Either C\ or C2 is the 4-clique. Without loss of generality,
say Ci is the 4-clique and C2 is a 3-clique. Let C\ be K(a, d, e, /) and C2 be
A(d,b,g). We note that no two vertices in {a,b,c,d,e, f,g} can be the same.
Next, consider the subgraph of G consisting of these three cliques in M. It has
seven vertices as shown in Figure 5.2. Let W = {a, 6, c, d, e, f,g}QV(G). Then
we have three more vertices not in W. We will consider the maximum possible
degree of each vertex in V{G). Note that there is no vertex contained in all of
three subgraphs C%, C2 and A(a, 6, c). Thus, by Lemma 5.2 no vertex of G can
be adjacent to every other vertex of G. Hence, each vertex in V(G) has degree
at most 8.
c
Figure 5.2: C\ is a 4-clique and C2 is a triangle.
However, the degrees of some vertices can be even less than 8. Let x be a
vertex in C\. Since G\ is the 4-clique, the set of edges incident to x is partitioned
84
into one 4-clique and a number of 3-cliques. This forces x to have odd degree.
Hence, every vertex in C\ has degree at most 7.
Next, consider vertices not in W. Let y 6 V(G) \ W. Since A(a,b,c),Ci
and C2 are maximal, y cannot be adjacent to all vertices in any one of them.
This forces y to be nonadjacent to at least two vertices in W and d(y) < 7.
Since y is not in the 4-clique in A4, the edges incident to y must be covered by
3-cliques. Hence, d(y) is even and d(y) <6.
Therefore, the three vertices outside W are of degree at most 6. For ver-
tices in W, four vertices in C\ are of degree at most 7, and the remaining
three vertices are of degree at most 8. Hence, the degree sum of G is at most
3 6 + 4 7 + 3 8 = 18 + 28 + 24 = 70, yielding \E(G)\ < = 35. But ten
3-cliques and one 4-clique require 3 10 + 6 = 36 edges to be disjoint. This is a
contradiction. So, Case 1 cannot occur.
Case 2 Neither C\ nor C2 is a 4-clique. Then both C\ and C2 are 3-
cliques. Let Ci = A(a, d, e) and C2 = A(b, d, /). As in Figure 5.3, the subgraph'
composed of A(a,b,c),Ci and C2 has six vertices. Let S {a,b,c,d,e,f} C
V(G). Since G has ten vertices, the degree sum of the six vertices in S is at
most 9 6 = 54. But since A(o, b, c), C\ and C2 are maximal, a yh /, b yh e and
c d. Then the degree sum of S is at most 54 6 = 48. Moreover, to preserve
the maximality of A (a, 6, c), C\ and C2, each of the remaining four vertices must
be nonadjacent to at least two vertices in S, this reduces the maximum possible
degree sum of S to 48 2 4 = 40. Next, we will consider the degrees of vertices.
85
outside S. Since M. contains at most one 4-clique, there are two possibilities.
Figure 5.3: Both Ci and Ci are triangles
Case 2.1 Suppose there exists a 4-clique in M.. Let w be any vertex
outside S. Again, to preserve the maximality of A(a, 5, c), C\ and C2, ver-
tex w must be nonadjacent to at least two vertices in S making d(w) < 7'.-
Counting the degree sum of vertices in S, the degree sum of G is at most
7 4 + 40 = 28 + 40 = 68. Hence, \E(G)\ < y = 34. Since ten 3-cliques and one
4-clique with disjoint edges cover 36 edges, this is a contradiction.
Case 2.2 Suppose there is no 4-clique in M. Similar to Case 2.1,
vertices not in S have degree at most 7. But because cliques in M. are 3-cliques, .
each vertex of G must have even degree. Hence, each vertex not in S is of degree
at most 6. Hence, the degree sum of G is at most 6 4 + 40 = 64. This yields :
|Â£(G)I < y = 32, which is insufficient to obtain 11 copies of the 3-clique, a
contradiction.
86
Thus, there is a contradiction in every possible case, and \M\ < 10.
Note that the conclusion of Theorem 5.1 may not be true if a maximal-
clique partition contains a 2-clique. For example, the graph in Figure 5.4 has
ten vertices and maximal-clique partition number 13.
dm
Figure 5.4: A graph of ten vertices with a maximal-clique partition containing
a 2-clique.
Remark 5.1 Let G be a graph of ten vertices with a clique partition V. Let
H be the subgraph of G composed of any three 4-cliques Hi,H2 and H3 in V.
Then, H has 18 edges with either nine or ten vertices. There are three possible
configurations for H as follows:
Configuration 1 Configuration 2 Configuration 3
Figure 5.5: Three configurations of H
87
Let I be the subgraph of G composed of any four 4-cliques in V. Then there
is only one possible configuration of I as follows:
Figure 5.6: The configuration of I
Let J be the subgraph of G composed of any five 5-cliques in V. By Lemma
5.1, there is one possible configuration of J and it is isomorphic to L(K5).
Figure 5.7: The configuration of J
88
Definition 5.1 Let if be a graph. Then e is a type-1 edge ofH if every maximal
triangle of any supergraph of if containing e does not contain other edges of if.
The next two theorems will show characteristics of maximal-clique partitions
of a graph having a clique partition containing at least three 4-cliques. As
Configuration 1 of if will play a central role in the proofs, let us investigate,
some of its properties here.
Definition 5.2 The following terminology is used when G is a graph of ten
vertices containing Configuration 1 of if as a subgraph. Recall that if consists.
of three 4-cliques ifi,if2 and if3 in V. Since Configuration 1 of if has nine
vertices, let z be the vertex in G \ if. Let T be the triangle composed of the .
three edges in the middle of Configuration 1 of if. It is simple to verify that
there are three type-1 edges in if as illustrated in Figure 5.8. For the remaining
15 edges in if, let edges outside T be called type-2 edges and edges in T be
called type-3 edges. Thus, the edge set of if is partitioned into three groups:
three type-1 edges, 12 type-2 edges and three type-3 edges.
Remark 5.2 Let uv be a type-2 edge in if. Then uv is in a 4-clique in
{ifi, if2, Hs}, say u 6 if*; and one of vertices {u, v} is in Hi D T and the other
one is in Hi \ T, say u 6 Hi Pi T, v 6 Hi \ T. Moreover, u E Hi D Hj where
i^je {1,2,3}-
89
*
* |