Printer Friendly

On economical set representations of graphs.

1 Introduction

We consider only finite undirected graphs without parallel edges or self-loops. Let G be a graph. A clique of G is one of its complete subgraphs. A clique is trivial provided it has no edges. A maximal clique is a clique which is not contained in any other one. We denote by CG the set of all cliques of G and by C(G) the set of all maximal cliques of G: For S [subset or equal to] V (G); let G[S] denote the subgraph of G induced by S: When S = 0; we often regard G[S] as a really trivial clique which has neither edges nor vertices.

Let S be a collection of sets. We say that G is the intersection graph of S if there is a mapping f from V (G) to S such that any two different vertices u; [member of] V (G) are adjacent in G if and only if f(u) and f(v) have a nonempty intersection [20, 26, 32, 51]. We call f a multifamily representation of G and say that f(v) represents v for each v [member of] V (G) in the representation. Sometimes, a multifamily representation is also referred to as an intersection representation or a set representation. The underlying set of the representation f is [[union].sub.v[member of]V(G)] f(v) and the size of f is defined to be the size of its underlying set. The intersection number of a graph G is the minimum size of a multifamily representation of G; denoted i(G): Note that intersection number is a function which is additive on the connected components of a graph. The study of intersection numbers plays a major part in various researches and has thus attracted much attention [13, 14, 15, 16, 27, 28, 31, 33, 36, 38, 44, 47, 48, 49, 52, 53]. We mention especially that competition number, an important graph parameter, is a close variant of the intersection number and many researches on it could be translated as researches on intersection number as well and vice versa [19, 32, 52].

Our paper is devoted to the economical set representation problem, namely the problem of minimizing the size of some restricted set representations of a given graph. The background of this problem can be illustrated as follows. On the one hand, as in many branches of mathematics, a useful approach to understand the structure of a graph is to study its representations, usually with some natural constraints. On the other hand, many practical problems can be formulated in terms of intersection models and thus reduce to solving some optimization problems on certain classes of intersection graphs. For some purposes, like storing a graph efficiently, we would like to determine how small the representations could be, how to identify such small representations, when they can be constructed efficiently and when the smallest representation is essentially unique. For more information on many related topics in intersection graph theory, we refer to [5, 26, 32, 51].

Let us identify various constraints for an intersection representation f: If f assigns distinct sets to different vertices of G; f is called a family representation of G: f is a Helly multifamily representation of G if f satisfies the Helly property [18], namely for any clique K of G; it holds [[intersection].v[member of]V(K)] f(v) [not eqaul to] 0: A family representation which satisfies the Helly property is named a Helly family representation. It is not hard to realize that each graph G possesses intersection representations which are family representations, multifamily representations, Helly multifamily representations, or Helly family representations, respectively. A good explanation of this fact can be found in Section 1.3 and Section 1.4 of [32]. We note that Gavril [23] shows that every graph G is the intersection graph of a Helly multifamily of subtrees of a graph without triangles, namely it has a very special Helly multifamily representation.

We use family intersection number, Helly multifamily intersection number and Helly family intersection number, denoted [i.sup.*](G); [i.sub.h](G) and [i.sup.*.sub.h](G); respectively, to be the minimum sizes of family representations, Helly multifamily representations and Helly family representations of G:

Lemma 1.1 (Erdos, Goodman, and Posa [20]) [32, Theorem 1.6] The intersection number of a graph G is exactly the minimum number of cliques covering the edges of G:

In view of Lemma 1.1, for any graph G; i(G) turns out to be the solution [[alpha].sub.I] (G) to the following integer linear programming problem.

Covering Problem I (CPI)

Minimize: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Subject To: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

With: w(C) [member of] {0,1} for each C [member of] [C.sub.G].

CPI can be relaxed to a linear programming problem without the integral constraints as follows. Covering Problem II (CPII)

Minimize: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Subject To: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

With: w(C) [greater than or equal to] 0 for each C [member of] [C.sub.G].

Let [[alpha].sub.II] (G) stand for the solution to CPII. Scheinerman and Trenk [44] define [[alpha].sub.II] (G) to be the fractional intersection number of a graph G; written as [i.sub.f] (G). It is immediate that

i(G) = [[alpha].sub.I] (G) [greater than or equal to] [[alpha].sub.II] (G) = [i.sub.f] (G): (1)

We know that the determination of i(G) is NP-hard in general [29]. But there are efficient algorithms to solve a linear programming problem and hence [i.sub.f] (G) serves as a computable lower bound for i(G) when we have all the necessary clique information as input to CPII. It is noteworthy that the number of maximal cliques might be exponential in terms of [absolute value of V] + [absolute value of E] and to report all these cliques is an important and difficult problem in combinatorial optimization [8].

Recall that a chordal graph is a graph with no induced cycles of length at least four [26, 51]. For any given chordal graph G, Scheinerman and Trenk [44] present a weighting algorithm, which assigns {0; 1} weights to E(G) [union] [C.sub.G]: They show that via this algorithm they can get a number which must be equal to both i(G) and [i.sub.f](G), thus yielding the following theorem.

Theorem 1.2 (Scheinerman and Trenk) [44, Theorem 5] If G is a chordal graph, then i(G) = [i.sub.f](G):

Given an intersection representation f of G and any A [subset or equal to] V (G); we write f(A) for [[union].sub.v[member of]V] f(v) and [bar.f](A) for [[union].v[member of]A] f(v); respectively. Two intersection representations [f.sub.1] and [f.sub.2] of G will be regarded as the same provided there is a bijection [pi] from [f.sub.1](V (G)) to [f.sub.2](V (G)) such that [pi] [omicron] [f.sub.1] = [f.sub.2]: A graph G is said to be uniquely (intersection) representable with respect to family representation (ui) if it has only one family representation f satisfying [absolute value of f(V (G))] = [i.sup.*](G): Analogously, we can define uniquely representable with respect to multifamily representation (uim), uniquely representable with respect to Helly multifamily representation (uimh) and uniquely representable with respect to Helly family representation (uih), respectively. We note that characterizing uniquely representable graphs or/and giving a recognition algorithm has been pointed out by Golumbic as the first research problem in his book [26, p. 20].

Here is a very basic result on the uniqueness of minimum-size family intersection representation.

Theorem 1.3 (Alter and Wang [2]) [31, p. 156] Complete graphs with more than one vertex are not uniquely representable with respect to family representation.

The set consisting of all the vertices adjacent to a vertex v in G is referred to as the open neighborhood of it in G and denoted by [N.sub.G](v); or merely N(v) if no confusion can arise. We say that two vertices u and v are twins if uv [member of] E(G) and N(v) = N(u); and in such a case we write uRv: Clearly, R is an equivalence relation on V (G): Each R-equivalence class is called a twin set. A graph is said to be twin-free provided each twin set consists of only one vertex. The graph obtained by deleting an edge from [K.sub.4] as shown in Fig. 1 is called a diamond.

Mahadev and Wang [31] study among diamond-free graphs the unique representability problem. Note that in their study of intersection representations, they require that no empty set can be used to represent a vertex. But it is easy to check that their result below also holds in our current framework.

Theorem 1.4 (Mahadev and Wang) [31, Theorem 3.8] If a graph G is diamond-free, then the following are equivalent:

(i) G is uniquely representable with respect to family representation;

(ii) G is twin-free;

[FIGURE 1 OMITTED]

The rest of this paper is organized as follows. The next section, Section 2, makes some elementary observations on the Helly multifamily intersection numbers. In Section 3, we put forward a sufficient condition for the validity of i(G) = [i.sub.f](G), which will play a key role in this work. Then we move on in the subsequent two sections to further explore some graph classes satisfying i(G) = [i.sub.f](G) by making use of this general criterion. In Section 4, as a direct generalization of Theorem 1.2, we discuss those graphs whose edge clique graphs are perfect; particularly, the so-called diamond-free elimination graphs are introduced there as a generalization of chordal graphs and are shown to satisfy i(G) = [i.sub.f](G): In Section 5, we address the so-called maximal clique irreducible graphs, which turn out to be those graphs with i(G) = [i.sub.f](G) = [i.sub.h](G); in particular, we identify a hierarchy of subclasses of maximal clique irreducible graphs, each of them is characterized by having some special intersection representations. Subsequently, in Section 6 we present a greedy algorithm to generate a set representation for any given graph. We take a closer look at the diamond-free elimination graphs and show that there is a polynomial time recognition algorithm for them and the greedy algorithm can be used to produce a minimum-size intersection representation for them in polynomial time. In Section 7 we are concerned with various lower bounds for [i.sup.*](G) and [i.sup.*.sub.h](G) and extremal graphs with respect to these parameters. We define a purple graph to be a sort of extremal graphs with respect to the Helly family intersection number. Then Section 8 is devoted to some intersection representation problems for purple graphs, including a generalization of the (ii) [left and right arrow] (iii) part of Theorem 1.4. Finally, we discuss in Section 9 the uniqueness of economical set representations and obtain generalizations of Theorem 1.3 as well as the (i) [left and right arrow] (iii) and the (i) [left and right arrow] (ii) parts of Theorem 1.4.

2 Helly multifamily intersection number

It is straightforward from the definitions that

i(G) [less than or equal to] [i.sub.h](G) [less than or equal to] [i.sup.*.sub.h](G); i(G) [less than or equal to] [i.sup.*](G) [less than or equal to] [i.sup.*.sub.h](G): (2)

To say more about the relationship among these intersection numbers, we examine some basic facts about the Helly multifamily intersection number.

For each set representation f of G; let [xi](f) = {G[[V.sub.x]] : x [member of] f(V (G))g; where [V.sub.x] = {v : x [member of] f(v)} for each x [member of] f(V (G)):

Theorem 2.1 (Roberts and Spencer [41]) [32, Lemma 1.11] An intersection representation f of a graph G satisfies the Helly property if and only if C(G) [subset or equal to] [xi](f):

Lemma 2.2 The equality [i.sub.h](G) = [absolute vale of C(G)] holds for any graph G.

Proof: A Helly multifamily representation f of size [absolute value of C(G)] can be obtained by letting S = C(G) and f(v) = {C [member of] C(G) : v [member of] V (C)} for each v [member of] V (G): But Theorem 2.1 implies that [absolute value of C(G)] [less than or equal to] [i.sub.h](G): This finishes the proof.

[FIGURE 2 OMITTED]

Example 2.3 For the graphs G and H in Fig. 2, {f(a) = {1}; f(b) = {1,2} 2g; f(c) = {1,3}; f(d) = {3}; f(e) = {2,3}; f(g) = {2}} and {f'(a) = {2,3}; f'(b) = {1,3}; f'(c) = {1,2}; f'(d) = {1,2,3} f'(e) = {1}} give minimum-size family intersection representations of them, respectively. By Lemma 2.2, for the graph G we have [i.sub.h](G) = 4 > 3 = [i.sup.*](G); while for the graph H we have [i.sub.h](H) = 2 < 3 = [i.sup.*](H):

Erdos, Goodman and Posa [20] establish that i(G) [less than or equal to] [[[absolute value of V(G)].sup.2]/4]. But [i.sub.h](G) can be exponentially large, as can be seen from the forthcoming example, which then tells us that [i.sub.h](G) can be much larger than i(G):

Example 2.4 [34, 35] Let n [greater than or equal to] 2 and G be a graph with n vertices. Then we have

[absolute value of C(G)] [less than or equal to] {[3.sup.n/3], if n [equivalent to] 0 ( mod 3); 4 x [3.sup.[[n/3].sup.-1]; if n [equivalent to] 1 ( mod 3); 2 x [3.sup.[n/3]] if n [equivalent to] 2 ( mod 3): (3)

Equality in (3) holds if and only if V (G) can be partitioned into disjoint subsets where each of them has three vertices with at most either one exception which has two or four vertices or two exceptions which both have two vertices and any two vertices are joined by an edge if and only if they come from different subsets.

For some classes of graphs we have more knowledge of their clique distributions and hence can get some better upper bounds for [i.sub.h](G): For example, we can deduce from the existence of a perfect elimination ordering [5, 17, 21, 32, 42] that a chordal graph G has at most [absolute value of V(G)] maximal cliques. We also know that a graph of boxicity k has at most O([[absolute value of V(G)].sup.k]) maximal cliques [5, 40]. We mention that to detect/enumerate the maximal cliques of various graph classes is a problem arising in many important applications [7].

3 Main result

Following Theorem 1.2, we will develop a more general sufficient condition for a graph to have equal fractional intersection number and intersection number.

First we need to introduce some more concepts. The independence number [alpha](G) of a graph G is the maximum size of an independent set of G: The minimum number of cliques in G needed to cover V (G) is referred to be its clique cover number and denoted by [theta](G): The edge clique graph of a graph G; denoted [K.sub.e](G); is the one whose vertices are the edges of G and two vertices are adjacent if and only if when regarded as edges of G they belong to a clique of G [1, 9, 10, 12, 29, 38, 39].

Next we present our main result, which confirms that edge clique graph is a natural context in investigating intersection numbers.

Theorem 3.1 Let G be a graph. If [theta]([K.sub.e](G)) = [alpha]([K.sub.e](G)), then i(G) = [i.sub.f](G):

To prove Theorem 3.1, we transform CPI and CPII to their dual maximization problems as below. Packing Problem I (PPI)

Maximize: [[SIGMA].sub.e[member of]E](G) [w.sup.(e)]

Subject To: [[SIGMA].sub.e[member of]E](C) [w.sup.(e)] [less than or equal to] 1 for each C [member of] [C.sub.G]

With: w(e) [member of] {0,1} for each e [member of] E(G).

Packing Problem II (PPII)

Maximize: [[SIGMA].sub.e[member of]E](G) [w.sup.(e)]

Subject To: [[SIGMA].sub.e[member of]E](C) [w.sup.(e)] [less than or equal to] 1 for each C [member of] [C.sub.G]

With: w(e) [greater than or equal to] 0 for each e [member of] E(G).

Note that both PPI and PPII are feasible and thus have optimal solutions, which we denote by [[beta].sub.I] (G) and [[beta].sub.II] (G), respectively. It follows at once that

[[beta].sub.II](G) [greater than or equal to] [[beta].sub.I] (G); (4)

as PPI becomes PPII after directly dropping the integral assumption. Invoking the Duality Theorem of Linear Programming [22], we arrive at

[[alpha].sub.II] (G) = [[beta].sub.II] (G): (5)

Putting together Eqs. (1), (4) and (5), we have

[[alpha].sub.I] (G) [greater than or equal to] [[alpha].sub.II] (G) = [[beta].sub.II] (G) [greater than or equal to] [[beta].sub.I] (G): (6)

Next, we consider the relationship between a graph and its edge clique graph. For any clique C of G; the edge set of C corresponds to the vertex set of a clique in [K.sub.e](G); denoted by (C); conversely, for any clique C' of [K.sub.e](G), the set of edges of G corresponding to vertices of C' must lie in the edge set of a clique of G and among all such cliques there is a unique minimal one, say [gamma]'(C'). The maps [gamma] and [gamma]' are order-preserving and induce a one-to-one correspondence between the cliques of [K.sub.e](G) and those cliques C of G which satisfy C = [gamma]'[gamma] (C). In particular, this leads to the following result.

Lemma 3.2 (Albertson and Collins [1]) [10, Proposition 1] There exists a one-to-one correspondence between nontrivial maximal cliques (intersection of nontrivial maximal cliques) of G and maximal cliques (intersection of maximal cliques) of [K.sub.e](G): Moreover, if C is a nontrivial maximal clique (intersection of maximal cliques) of G; then the corresponding clique of[K.sub.e](G) is formed by the vertices which correspond to the edges of G with both endpoints in C:

Moreover, the correspondence between the cliques of G and [K.sub.e](G) as described before implies the lemma below.

Lemma 3.3 [theta]([K.sub.e](G)) = [[alpha].sub.I] (G) and [alpha]([K.sub.e](G)) = [[beta].sub.I] (G):

From here it is a short step to finishing the proof of Theorem 3.1.

Proof of Theorem 3.1: By Lemma 3.3, we deduce from [theta]([K.sub.e](G)) = [alpha]([K.sub.e](G)) that [[alpha].sub.I] (G) = [[beta].sub.I] (G); which combined with inequality (6) leads to i(G) = [[alpha].sub.I] (G) = [[alpha].sub.II] (G) = [i.sub.f](G); as claimed.

Example 3.4 Raychaudhuri [39] demonstrates that any four-wheel-free transitively orientable graph G satisfies [theta]([K.sub.e](G)) = [alpha]([K.sub.e](G)). Thus Theorem 3.1 immediately implies that any four-wheel-free transitively orientable graph G satisfies i(G) = [i.sub.f](G):

4 Graphs whose edge clique graphs are perfect

We begin with an immediate corollary of Theorem 3.1.

Theorem 4.1 Each graph G whose edge clique graph is perfect satisfies i(G) = [i.sub.f](G):

In view of Theorem 4.1, it is of interest to investigate those graphs whose edge clique graphs are perfect.

Example 4.2 Albertson and Collins [1] show that if G is planar and 3-colorable, then [K.sub.e](G) is perfect.

Example 4.3 It is known that the edge clique graph of a chordal graph is still chordal [1, 38, 39] and hence perfect. Note that this means that Theorem 4.1 is a generalization of Theorem 1.2.

Our remaining objective in this section is to generalize the observation made in Example 4.3. To this end, we need a bit more terminology.

We think of an ordering [sigma] of V (G) as a bijection from V (G) to {1, 2, ...; [absolute value of V(G)]}. Put N(v; [sigma]) = {u [member of] N(v) : [sigma](u) > [sigma](v)}. An ordering [sigma] is a perfect elimination ordering (peo) if for each v [member of] V (G);N(v, [sigma]) induces a clique of G: Recall that a graph is chordal if and only if it possesses a peo [5, Theorem 1.2.2] [17, 21, 42]. Generalizing the concept of chordal graphs, we define a diamond-free elimination graph to be a graph whose vertex set has a generalized perfect elimination ordering (gpeo), namely an ordering [sigma] with the property that G[N(v, [sigma])] is a vertex-disjoint union of cliques for each v [member of] V (G): It is easy to see that a diamond-free elimination graph G has at most [absolute value of E(G)] maximal cliques.

A simple characterization of gpeo is as follows.

Lemma 4.4 An ordering [sigma] of V(G) is a gpeo if and only if for each v [member of] V(G) and each u [member of] N(v,[sigma]),N(v,[sigma])[intersection]N(u) induces a clique of G: In particular, if G has a gpeo and if there is v [member of] V(G) satisfying that N(v) [intersection] N(u) induces a clique of G for each u [member of] N(v); then G - v also has a gpeo.

For any ordering [sigma] of V(G), there is a unique ordering [sigma]' of V ([K.sub.e](G)) such that [sigma]'(uv) < [sigma]'(xy) if and only if either min([sigma](u), [sigma](v)) < min([sigma](x), [sigma](y)) or min([sigma](u), [sigma](v)) = min([sigma](x), [sigma](y)) but max([sigma](u), [sigma](v)) < max([sigma](x), [sigma](y)): It is not hard to see the following result which indicates the connection between chordal graphs and diamond-free elimination graphs.

Lemma 4.5 [sigma] is a gpeo of G if and only if [sigma]' is a peo of [K.sub.e](G). Hence the edge clique graph of a diamond-free elimination graph is chordal.

We are now ready to show that any diamond-free elimination graph G fulfils i(G) = [i.sub.f](G): Note that we will show in Section 6 that a diamond-free elimination graph can be recognized in polynomial time and there is a greedy algorithm to determine its intersection number directly, rather than compute its fractional intersection number via solving a linear programming problem.

Theorem 4.6 If G is a diamond-free elimination graph, then i(G) = [i.sub.f](G):

Proof: It is well-known that chordal graphs are perfect [26, 30, 51]. So, the result comes from Theorem 4.1 and Lemma 4.5, as desired.

Let us look around for some examples of diamond-free elimination graphs.

Example 4.7 As a class of graphs including all bipartite graphs, diamond-free graphs have attracted much attention. Mahadev and Wang [31, Proposition 2.8] show that a graph G is diamond-free if and only if every edge of G lies in a unique maximal clique. We thus know that the class of diamond-free graphs is a subclass of diamond-free elimination graphs. An application of Theorem 4.6, or the remark preceding Theorem 4.6, says that the intersection numbers of these graphs are easy to determine.

[FIGURE 3 OMITTED]

Example 4.8 The graph displayed in Fig. 3 is neither chordal nor diamond-free. But it has a gpeo as indicated in the figure and thus is a diamond-free elimination graph.

The following example says that the converse of the second part of Lemma 4.5 is not valid. Indeed, an edge clique graph [K.sub.e](G) is chordal exactly means that it has a peo, say [tau], and it may happen that there is no ordering [sigma] of G such that [tau] = [sigma]0:

[FIGURE 4 OMITTED]

Example 4.9 Let G be the graph as depicted on the left of Fig. 4. Since [N.sub.G](v) does not induce a vertex-disjoint union of cliques for any v [member of] V(G), G is not a diamond-free elimination graph. However, its edge clique graph, as exhibited on the right of Fig. 4, is a chordal graph.

5 Graphs satisfying i(G) = [i.sub.f](G) = [i.sub.h](G)

5.1 Maximal clique irreducible graphs

[FIGURE 5 OMITTED]

Example 5.1 For t [greater than or equal to] 3, the Tsuchiya graph [T.sub.2t] [49] is specified by setting V([T.sub.2t]) = {1, 2, ..., 2t} and E([T.sub.2t]) = {(i, i+1), (t+i, t+i+1), (i, i+t+1), (i+1, t+i), (i, i+t) : i [member of] [Z.sub.t]: For any odd integer t [greater than or equal to] 5, we take [F.sub.t] [subset or equal to] V ([K.sub.e]([T.sub.2t])) to be [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. See Fig. 5 for an illustration of [T.sub.10] and [F.sub.5]. We can check that [F.sub.t] induces a chordless odd cycle of length at least 5 in [K.sub.e]([T.sub.2t]) and hence [K.sub.e]([T.sub.2t]) is not a perfect graph. This means that we cannot use Theorem 4.1 directly to tell whether or not the Tsuchiya graph [T.sub.2t] has equal intersection number and fractional intersection number.

Besides the work in Section 4, we will develop in this subsection another consequence of Theorem 3.1. Among many applications of this result, it will enable us to find out in the next subsection that the intersection number, the fractional intersection number and the Helly intersection number of any given Tsuchiya graph are all equal, see Corollary 5.8.

A special vertex of a graph G is a vertex which is contained in only one maximal clique of G and a special edge of G is one edge which only appears in one maximal clique of G: Wallis and Zhang [32, 50] define a graph G to be maximal clique irreducible if each nontrivial maximal clique of G contains a special edge. We remark that G is maximal clique irreducible if and only if C([K.sub.e](G)) is an irreducible covering of [K.sub.e](G) [46]. We are ready to present the main theorem of this subsection.

Theorem 5.2 If G is maximal clique irreducible, then i(G) = [i.sub.f](G).

Proof: By means of Lemma 3.2, the cliques in C([K.sub.e](G)) are in one-to-one correspondence with the nontrivial cliques from C(G): Since every nontrivial clique in C(G) has a special edge, correspondingly, each member of C([K.sub.e](G)) contains a special vertex in [K.sub.e](G): Taking from each clique in C([K.sub.e](G)) one special vertex we obtain an independent set of size [absolute value of C([K.sub.e](G))] and thus [alpha]([K.sub.e](G)) [greater than or equal to] [absolute value of C([K.sub.e](G))] [greater than or equal to] [theta]([K.sub.e](G)) follows. On the other hand, by the pigeon-hole principle we know that [alpha]([K.sub.e](G)) = [alpha]([K.sub.e](G)). The conjunction of these two inequalities then implies that [theta]([K.sub.e](G)) = [alpha]([K.sub.e](G)) an so we can apply Theorem 3.1 to get i(G) = [i.sub.f](G).

We proceed with an investigation of maximal clique irreducible graphs. As we shall see, this class of graphs is characterized by i(G) = [i.sub.f](G): We will arrive at such a conclusion by taking things step by step.

As was observed in Eq. (2), we have i(G) [less than or equal to] [i.sub.h](G) for any graph G. In this regard, the next lemma shows that maximal clique irreducible graphs are some sort of extremal graphs.

Lemma 5.3 G is maximal clique irreducible if and only if i(G) = [i.sub.h](G):

Proof: We prove the backward direction by contradiction. Assume that there exists a clique C [member of] C(G) which has no special edge. This means that the union of cliques in C(G) \ {C} covers E(G): As a consequence of Lemmas 1.1 and 2.2, we then find that i(G) < [absolute value of C(G)] = [i.sub.h](G), contrary to our assumption.

Now consider the forward direction. Let C(G) = {Q1, ..., [Q.sub.[absolute value of C(G)]]}: For each nontrivial [Q.sub.i] [member of] C(G), let [S.sub.i] [not equal to] 0, be the set of its special edges. If there is a family of cliques of size less than [absolute value of C(G)] whose union covers E(G), then we can find a clique in this family intersecting with at least two different [S.sub.i]'s, which is impossible.

Theorem 5.4 If i(G) = [i.sub.h](G), then i(G) = [i.sub.f](G) = [absolute value of C(G)].

Proof: This is a consequence of Theorem 5.2 and Lemma 5.3. 2

Lemma 5.3 together with Theorem 5.4 goes through to deduce the following result.

Theorem 5.5 G is maximal clique irreducible if and only if i(G) = [i.sub.f](G) = [i.sub.h](G) = [absolute value of C(G)].

Example 5.6 Each triangle-free graph is a diamond-free graph and each edge of a diamond-free graph is a special edge. Thus, Theorem 5.5 says that each triangle-free graph G, or more generally, each diamond-free graph G, satisfies i(G) = [i.sub.h](G) = [i.sub.f](G): This strengthens our former assertion in Example 4.7.

5.2 A hierarchy of maximal clique irreducible graphs

For a graph G, an ordering [pi] of C(G) is a way to label exactly one clique from C(G) as [C.sub.i] for each i = 1, ..., [absolute value of C(G)], we express this fact by writing [pi] = ([C.sub.1], ..., C[absolute value of C(G)]): An ordering [pi] of C(G) is circular provided that the maximal cliques containing any given vertex appear in a circular consecutive order in [pi]--imagine the ordering as wrapped around a circle. A Helly circular-arc graph is the one whose set of maximal cliques has a circular ordering [5, 24, 26, 32]. We denote the class of Helly circular-arc graphs by HCA: From this definition it is easy to see that the class of interval graphs belong to HCA [21]. For any given graph we can recognize whether or not it belongs to HCA in polynomial time [5, 24].

Corollary 5.7 If G [member of] HCA, then G is maximal clique irreducible and i(G) = [i.sub.h](G) = [i.sub.f](G):

Proof: Let [pi] = {[C.sub.1], ..., C[absolute value of C(G)]} be a circular ordering of C(G). For each i [member of] Z[absolute value of C(G)], choose a vertex [u.sub.i] [member of] [C.sub.i]\ [C.sub.i+1] and a vertex [w.sub.i] [member of] [C.sub.i]\[C.sub.i-1] and then we can check that [u.sub.i][w.sub.i] [member of] E([C.sub.i]) is a special edge. By appealing to Theorem 5.5, the result follows. 2

Evidently, all Tsuchiya graphs [T.sub.2t] posed in Example 5.1 with t > 3 are contained in HCA: So by Corollary 5.7, we have the following result.

Corollary 5.8 Each Tsuchiya graph [T.sub.2t] with t > 3 satisfies i([T.sub.2t]) = ih([T.sub.2t]) = [i.sub.f] ([T.sub.2t]):

To gain more understanding of the graphs satisfying i(G) = [i.sub.h](G) = [i.sub.f](G), namely maximal clique irreducible graphs, we proceed to discuss a hierarchy of some subclasses of them and provide characterizations of them from the viewpoint of intersection representations. The bottom of this hierarchy will be the class of Helly circular-arc graphs mentioned above and the top will be the class of maximal clique irreducible graphs.

A family F of sets is said to have the strong Helly property [6] if for every pairwise intersecting subfamily F' [subset or equal to] F there exist [S.sub.1], [S.sub.2] [member of] F' such that [[intersection].sub.S[member of]F'] S = [S.sub.1] [intersection] [S.sub.2]. Weakening slightly this definition, we assert that a family F of sets has the semistrong Helly property if for every maximal pairwise intersecting subfamily F' [subset or equal to] F there exist [S.sub.1], [S.sub.2] [member of] F' such that [[intersection].sub.S[member of]F'] S = [S.sub.1] [intersection] [S.sub.2]: An intersection representation f where {f(v) : v [member of] V(G)} has the strong (semistrong) Helly property is called a strong (semistrong) Helly representation. We designate the class of graphs that have a strong Helly representation as SH and those having a semistrong Helly representation as SSH, respectively. We remark that a graph belongs to SH if and only if every induced subgraph of it belongs to SSH: It is also noteworthy that SH is nothing but the line graphs of strong Helly hypergraphs [32].

Recall that maximal clique irreducible graphs are identified by a special property of their clique structure. In contrast, SSH is characterized by the possession of a special kind of set representations. We now show that they are merely the same object defined from different points of view.

Theorem 5.9 SSH is exactly the class of maximal clique irreducible graphs. Hence, by Theorems 5.5, for any graph G, i(G) = [i.sub.h](G) = [i.sub.f](G) if and only if G [member of] SSH:

Proof: First assume that G has a semistrong Helly representation f and take arbitrarily a nontrivial maximal clique C of G. It suffices to show that C has a special edge. The semistrong Helly property of f guarantees the existence of two vertices u,w [member of] V (C) such that [bar.f](V (C)) = f(u) [intersection] f(w):We can assume u [not equal to] w, otherwise we simply use any other vertex from V (C) \ {u} [not equal to] to be the new w: We claim that the edge uw is a special edge. Actually, for any maximal clique C' which includes both u and w, we have 0 [not equal to] [bar.f](V (C")) [subset or equal to] f(u) [intersection] f(w) = f(V (C)) and hence [theta] = [bar.f](V(C) [intersection] V(C')) follows. Since f is an intersection representation of G, we know that G[V(C) [intersection] V(C')] must be a clique and then infer from the maximality of C and C' that C = C'. Of course, this means that uw is a special edge, as asserted.

For the reverse direction, assign to each v [member of] V(G) the set f(v) = {C [member of] C(G) : v [member of] V(C)}: It is easy to verify that f is an intersection representation of G: Suppose that C [member of] C(G) is trivial, say C = {x}: Clearly, f(x) = {C}: Hence, taking u = w = x, we can write [bar.f](V(C)) = f(u) [intersection] f(w): We then take up the case that C [member of] C(G) is nontrivial. For now, C has a special edge, say uw, that is to say, f(u) [intersection] f(w) = {C}: But for any v [member of] V(C) we surely have C [member of] f(v): This immediately leads to [bar.f](V(C)) = f(u) [intersection] f(w) = {C}: Thus we have come to the conclusion that f is a semistrong Helly representation of G and the proof is done.

It is obvious that SH [subset or equal to] SSH: Currently, we are not aware of any existing interesting graph class which lies in SSH SH: Anyway, we do know that SH [not equal to] SSH, as indicated by the example below.

[FIGURE 6 OMITTED]

Example 5.10 Consider the graph G demonstrated in Fig. 6 which has three size-3 maximal cliques and one size-4 maximal clique. Since each maximal clique of G has a special edge, we conclude that i(G) = [i.sub.h](G) and hence G [member of] SSH: We now verify that G [not equal to] SH: Suppose otherwise that f is a strong Helly representation of G: Then for the clique C = {a, b, c} we have, w.l.o.g., [bar.f](V(C)) = f(a) [intersection] f(b), namely f(a) [intersection] f(b) [subset or equal to] f(c). But {d, a, b} is a clique and so 0 [not equal to] f(d) [intersection] f(a) [intersection] f(b) [subset or equal to] f(d) [intersection] f(c): This is impossible as there is no edge in G connecting c and d.

A graph G is a hereditary clique-Helly graph if C(G) satisfies the strong Helly property [37, 50]. Following Prisner [37], we use the notation HCH for this class of graphs. We define the clique graph operator K(*) such that, for any graph H, K(H) is the intersection graph of the maximal cliques of H: A graph is a clique graph if it is isomorphic to K(H) for some graph H:

Two interesting results about HCH are as follows.

Lemma 5.11 (Prisner [37]) [32, p. 129] A graph is a hereditary clique-Helly graph if and only if each of its vertex-induced subgraphs is maximal clique irreducible.

Lemma 5.12 (Prisner [37]) [32, Theorem 7.34] A graph is a hereditary clique-Helly graph if and only if G = K(H) where H is another hereditary clique-Helly graph.

We are now prepared to show that HCH and SH are the same graph class.

Theorem 5.13 HCH = SH:

Proof: For any G [member of] HCH, by Lemma 5.12 we know that G is the clique graph of some hereditary clique-Helly graph H: According to the definition of a hereditary clique-Helly graph, C(H) is a family with the strong Helly property, thus implying G [member of] SH: This completes the proof of HCH [subset or equal to] SH:

Conversely, suppose G is a member of SH and f is a strong Helly representation of G: We aim to deduce that G [member of] HCH from which the theorem then follows. By Lemma 5.11, it is enough to prove that each of its vertex-induced subgraphs G" is maximal clique irreducible. Let [f|.sub.G"] be the representation f restricted to V (G'): Clearly, [f|.sub.G'] is an intersection representation of G' which satisfies the strong Helly property. By Theorem 5.9, we get that G' is maximal clique irreducible, as was to be shown. [member of]

We now go back to HCA: We will show that HCA [subset or equal to] HCH, thus strengthening Corollary 5.7. An equivalent definition of Helly circular-arc graph will be needed: A Helly circular-arc graph is the intersection graph of a Helly family of circular arcs on a circle [5, 24, 32]. We will also make use of a simple result which we single out as a lemma. A class of graphs is said to be induced-hereditary if each induced subgraph of a member of it also belongs to it [4]. It follows readily from the definition of HCA as described above that HCA is induced-hereditary.

Lemma 5.14 An induced-hereditary class of graphs belongs to HCH if and only if it is a subclass of SSH:

Proof: This is an application of the combination of Theorem 5.9 and Lemma 5.11. [member of]

Theorem 5.15 HCA [subset or equal to] HCH:

Proof: Corollary 5.7 combined with Theorem 5.9 asserts thatHCA [subset or equal to] SSH: Further applying Lemma 5.14 and our remark prior to it, this enables us to draw the conclusion, as required. [member of]

Example 5.16 It is surely true that if the size of no C [member of] C(G) exceeds [member of] then each clique in C(G) has a special edge. This observation together with Lemma 5.11 yields that the Petersen graph demonstrated in Fig. 7 is a member of HCH: But we can easily check that the maximal cliques of Petersen graph do not possess any circular ordering. This means that the Petersen graph does not belong toHCA: Consequently, we arrive at HCH \ HCA [not equal to] 0:

Summing up what we have obtained in this subsection, we can state the following result. Theorem 5.17 HCA [??] HCH = SH [??] SSH:

[FIGURE 7 OMITTED]

6 The ST weighting algorithm

In this section we will present a greedy algorithm for any given graph, which can output a set of cliques covering every edge of it. Surely, this then easily leads to a set representation of the graph and an upper bound of its intersection number. We will show that with the knowledge of a gpeo of a given diamond-free elimination graph, what comes out from this greedy algorithm is a minimum-size set representation.

Adapting the weighting algorithm of Scheinerman and Trenk [44] as mentioned in Section 1, we give the following algorithm, which we call the ST weighting algorithm.

ST Weighting Algorithm:

Input: A graph G and a vertex ordering [sigma] of G.

Initialize: Let w(C) = w(e) = 0 for every clique C and edge e of G: Mark all edges as "uncovered".

Set [G.sub.1] = G.

For i = 1 to [absolute value of V(G)] -1 do:

(1) Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For j = 1 to [k.sub.i] do:

If there is an edge e of [C.sub.i,j] incident to [[sigma].sup.-1](i) that is marked "uncovered", then

(a) Let w([C.sub.i,j]) = w(e) = 1:

(b) Mark all edges in [C.sub.i,j] "covered".

End of for loop

(2) Let [G.sub.i+1] = [G.sub.i] [[sigma].sup.1](i):

End of for loop

Output: The weight function w from E(G) [union] [C.sub.G] to {0, 1}.

For convenience, the outer For loop in the ST weighting algorithm is called the ith pass. During the ith pass there are still [k.sub.i] inner For loops which we will call iterations.

Lemma 6.1 Let [sigma] be a vertex ordering of graph G: If w is the weight function arising from the ST weighting algorithm with [sigma] as an input, we can produce an intersection representation of G of size [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof: First we show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is a feasible solution to the linear program CPII, i.e., for each e [member of] E(G), we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Notice that for i = 1, ..., n - 1, all edges incident to [[sigma].sup.1](i) will be marked "covered" at the end of the ith pass. Hence all edges of G are marked by the ST weighting algorithm. Accordingly, for any given edge e, there are i and j such that e is marked by the operation (b) during the jth iteration of the ith pass. In the same iteration, the operation (a) then assigns weight 1 to a clique C satisfying e [member of] E(C): Since the weights given to cliques in CG are from f0, 1g, this verifies our statement.

Let [Q.sub.[sigma]] be the set of cliques of G receiving weight 1 at the end of the ST weighting algorithm. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] w(C) is a feasible solution to CPII, we get that the union of the cliques in [Q.sub.[sigma]] covers E(G): It is now a simple and well-known procedure to yield the required intersection representation f of size [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for each v [member of] V(G), let f(v) = {C [member of] [Q.sub.[sigma]] : v [member of] V (C)}.

Since we can find an intersection representation for any graph and any vertex ordering with the help of the ST weighting algorithm, it is natural to consider the following question.

Question 6.2 For any graph G and its vertex ordering [sigma], can we estimate the difference between i(G) and the size of the intersection representation obtained by the ST weighting algorithm? For which kind of graph classes can we have some ordering with which the ST weighting algorithm can produce a minimum-size set representation? How to search for such a good ordering efficiently? For which class of graphs can the ST weighting algorithm lead to an approximation algorithm for deciding the intersection number and what is its performance guarantee?

In Section 4 we have seen that any chordal graph is a diamond-free elimination graph. Indeed, to prove the next theorem we follow the idea of Scheinerman and Trenk [44] in deducing Theorem 1.2.

Theorem 6.3 Let G be a diamond-free elimination graph and [sigma] a generalized perfect elimination ordering of G: If w is the weight function arising from the ST weighting algorithm with [sigma] as an input, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof: It is sufficient to prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is the optimal solution to the linear program CPI.

First observe that each time we give a clique weight 1 in applying the ST weighting algorithm, we exactly assign one edge a weight 1: Thus we get that [[SIGMA].sub.e[member of]E(G)]w(e) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] are equal, say W.

We next intend to show thatW is a feasible solution to the linear program PPII, i.e., [[SIGMA].sub.e[member of]C w(e) [less than or equal to] 1 for each C [member of] [C.sub.G]. Assume that there is at least one weight-1 edge in E(C): Since at each iteration, at most one edge is assigned weight 1, we can assume that at the jth iteration of the ith pass the first edge from E(C), say xy, receives weight 1: Since we only give weight 1 to edges incident to [[sigma].sup.-1](i) in the ith pass, we can further assume that x = [[sigma].sup.1](i): Clearly, when the (i 1)th pass terminates, all edges in E(C) n E([G.sub.i]) = {uv [member of] E(C) : min([sigma](u), [sigma](v)) < i} have been marked "covered" and will keep a weight 0 from then on. The assumption that [sigma] is a gpeo tells us that for each edge from E(C) [intersection] E([G.sub.i]) there is a unique 1 [less than or equal to] j [less than or equal to] [k.sub.i] such that this edge lies in E([C.sub.i],j), and the value j for this edge must be the same as for xy. Consequently, all edges e [not equal to] xy of E(C) [intersection] E(Gi) will be marked "covered" at the jth iteration of the ith pass and keep a weight 0 since then. This then proves that xy is the only edge of E(C) that receives a weight 1:

Finally, recall that in course of the proof of Lemma 6.1, we already show that W is a feasible solution to CPII.

Taking all things together, we know that W must be the optimal solution to CPII which then gives W = [i.sub.f](G): Since the weight function only takes value from {0, 1}, W is also the optimal solution to the integer linear program CPI, from which W = i(G) follows. [member of]

Lemma 6.1 in combination with Theorem 6.3 implies that, for any diamond-free elimination graph, if a gpeo is already known, we can produce an intersection representation of minimum size for the graph by running the ST weighting algorithm. But is it easy to tell whether or not a gpeo exists and construct a gpeo in the case that it exists? Again, we can devise a very naive way to do it: Search for a vertex v such that each set of the form N(u) [intersection] N(v), u [member of] N(v), induces a clique of G, eliminate v and all the edges incident to it, repeat the same step on the remaining graph until no vertex remained can be removed, record the sequence of vertices being deleted in order. If the input graph has a gpeo, Lemma 4.4 guarantees that we will find one when the algorithm terminates, otherwise, the algorithm halts before we delete every vertex of the graph and we can assert that there is no gpeo for the graph. It is not hard to see that this gives a O([[absolute value of V(G)].sup.5]) time algorithm for the recognition of diamond-free elimination graphs. Note that there are linear time recognition algorithms for chordal graphs [5, 32, 43, 45, 51] and there are good algorithms to enumerate all peos of a chordal graph [11]. It will be interesting if those kind of work can be generalized to produce some clever algorithms for diamond-free elimination graphs.

We have shown how to find a gpeo for a diamond-free elimination graph G and how to generate a minimum-size intersection representation of G with the help of ST weighting algorithm. We claim that the whole process can be completed in polynomial time. Indeed, when implementing the ith pass of the ST weighing algorithm on G with one of its gpeo, say [sigma], as an input, we deal with the graph with vertex set {[[sigma].sup.1](j) : j [greater than or equal to] i} and edge set of uncovered edges then. Each time we find a maximal clique containing [[sigma].sup.1](i) we cover (delete) all those edges in this clique. The number of cliques thus arise is exactly the intersection number of the graph. A bit thinking shows that the ST weighting algorithm can get the intersection number in O([[absolute value of V(G)].sup.2]) time.

Recall that, for any diamond-free elimination graph G, Lemma 4.5 says that the edge clique graph [K.sub.e](G) is chordal. This enables us to use the algorithm of Gavril [25] to obtain the value of [theta]([K.sub.e](G)) = [alpha]([K.sub.e](G)), which is exactly i(G) by Theorem 3.1. Though the construction of [K.sub.e](G) may be costly, this is another way to calculate the intersection number of a diamond-free elimination graph.

7 Family intersection number and Helly family intersection number

We use the convention that the maximal cliques of G have been indexed as C(G) = {Q1, ..., [Q.sub.[absolute value of C(G)]]}. We denote by [C.sub.v](G) the subset of C(G) consisting of those maximal cliques which contain a vertex v and let [C.sub.Y] (G) = {C [member of] C(G) : Y [subset or equal to] V(C)} for any twin set Y:

Let C(G) = [C.sub.1](G) [union] [C.sub.2](G) [union] [C.sub.3](G) be a partition of the maximal cliques of G, where

[C.sub.1](G) = {[Q.sub.i] [member of] C(G) : Q has a special vertex},

[C.sub.2](G) = {[Q.sub.i] [member of] C(G) : Q has a special edge but no special vertex}

[C.sub.3](G) = {[Q.sub.i] [member of] C(G) : Q has neither special edges nor special vertices}:

We write [R.sub.i] and [S.sub.i], respectively, for the sets of special vertices and special edges in [Q.sub.i] and let [n.sub.i] and [m.sub.i] be their respective cardinalities. Note that there are graphs G with [C.sub.3](G) = C(G) and hence all [n.sub.i] and [m.sub.i] vanish, see the complete n-partite graph [K.sub.2, ...,2] with n [greater than or equal to] 3, which is also mentioned in Example 2.4.

Our aim in this section is to boil down some knowledge about [C.sub.1](G), [C.sub.2](G) and [C.sub.3](G) to some estimates of [i.sup.*](G) and [i.sup.*.sub.h](G). We begin with a very easy and well-known result on set systems.

Lemma 7.1 [3, Theorem 1.1.1] If A is a collection of distinct subsets of an n-set such that [A.sub.i] [intersection] [A.sub.j] [not equal to] 0 for all [A.sub.i], [A.sub.j] [member of] A, than [absolute value of A], [less than or equal to] [2.sup.n-1]: Further, if [absolute value of A] < [2.sup.n-1], A can be extended to a collection of [2.sup.n-1] subsets also satisfying the given intersection property.

We use lg for base [member of] logarithm. For any complete graph [K.sub.m], an implication of Lemma 7.1 is that

[i.sup.*]([K.sub.m]) = [lg(m)] + 1: (7)

For diamond-free graphs, Mahadev andWang [31] directly make the following generalization of Lemma 7.1.

Theorem 7.2 (Mahadev and Wang) [31, Lemma 3.7.] Let G be a diamond-free graph. Then we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], where [c.sub.s] is the number of maximal cliques possessing either special vertices or special edges and [n.sub.i] is the number of special vertices in the ith maximal clique [Q.sub.i].

Inspired by Theorem 7.2, we now have a look at the lower bounds of the family intersection number [i.sup.*](G) and Helly family intersection number [i.sup.*.sub.h](G):

We have the following two simple observations, which indicate the connection between twin structure and clique structure.

Lemma 7.3 xRy if and only if [C.sub.x](G) = [C.sub.y](G):

Lemma 7.4 For any i = 1, ..., [absolute value of C(G)], [R.sub.i] is either empty or a twin set. Moreover, if Ri is nonempty, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

We deviate a bit to include a necessary condition for i(G) = [i.sup.*](G) based on the structure of twin sets.

Theorem 7.5 Let G be a graph. If i(G) = [i.sup.*](G), then each twin set Y of G with [absolute value of [C.sub.Y](G)] = 1 is a singleton set.

Proof: We shall assume the opposite, namely there exists a twin set Y with [absolute value of [C.sub.Y](G)] = 1 and [absolute value of Y] [greater than or equal to] 2. and derive a contradiction.

Since [absolute value of C(G)] = 1, there exists a unique Q [member of] [C.sub.1](G) such that [C.sub.Y] (G) = {Q}: We take two distinct vertices a, b [member of] Y: Let f be a family representation of G satisfying f(V(G)) = [i.sup.*](G): Since f(a) [not equal to] f(b), w.l.o.g., we can assume that there exists x [member of] f(a) \ f(b): Clearly, for any v [member of] V(G) \ V(Q), it holds that ({x} [union] f(b)) [intersection] f(v) = 0. A consequence of this fact is that for any set A and any v [member of] V(G) \ V (Q), whether or not f(v) [intersection] A = 0 is determined by the relationship between f(v) and A \ ({x} [union] f(b)):

We construct a new mapping f' by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

From our remark made above we see that f0 is a mutifamily representation of G satisfying f'(V(G)) [subset or equal to] f(V(G)) \ {x}: This means that [absolute value of f'(V(G))] [less than or equal to] [i.sup.*](G) - 1: So we have i(G) [less than or equal to] [absolute value of (V(G))] < [i.sup.*](G), which is the desired contradiction. [member of]

Let us switch back to our main line. We next prove that the quantity occurring in Theorem 7.2 is a general lower bound on the family intersection number.

Theorem 7.6 For every graph G, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (8)

where [c.sub.s] is the number of maximal cliques with special vertices or special edges and [n.sub.i] is the number of special vertices in the ith maximal clique [Q.sub.i].

Proof: Let f be a family representation of G of size [i.sup.*](G): Clearly, f([R.sub.i]) [intersection] f([R.sub.j]) = 0 for any two different cliques [Q.sub.1],[Q.sub.j] [member of] [C.sub.1](G): For any [Q.sub.k] [member of] [C.sub.2](G), and any edge in [S.sub.k], say ab, we assert that [bar.f]({a, b}) [not equal to] 0 must be disjoint from f(c) for any c [??] [Q.sub.k]: Otherwise, a, b, c will appear in some maximal clique of G, which must be different from [Q.sub.k] for c [??] [Q.sub.k], contradicting ab [member of] [S.sub.k]: We denote [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Our analysis above leads to the conclusion that f([R.sub.i]), [O.sub.k] are pairwise disjoint for [Q.sub.1] [member of] [C.sub.1](G),[Q.sub.k] [member of] [C.sub.2](G): It then follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (9)

Restricting the representation f to the clique G([R.sub.i]) induced by [R.sub.i], we deduce from Lemma 7.1, or more precisely, Eq. (7), that [absolute value of f([R.sub.i])] [greater than or equal to] [i.sup.*](G([R.sub.i])) = [lg(ni)] + 1: Also, we surely have [absolute value of Ok] [greater than or equal to] 1 for each [Q.sub.k] [member of] [C.sub.2](G): Thus, Eq. (9) gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (10)

Theorem 7.2 means that diamond-free graphs attain the lower bound given by Theorem 7.6. We cannot characterize all such graphs which have the family intersection number as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. But for the Helly family representations, we can do a bit better.

Theorem 7.7 For every graph G,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (11)

with equality if and only if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (12)

for each twin set Y of G, where [n.sub.i] is the number of special vertices in the ith maximal clique [Q.sub.1] and we [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] as 1 when [C.sub.Y] (G) [intersection] [C.sub.1](G) = 0.

Proof: Consider a Helly family representation f of G: For any [Q.sub.1] [member of] C(G), we deduce from the Helly property of f that [bar.f](V ([Q.sub.1])) [not equal to] 0. Moreover, since C(G) is the set of maximal cliques, the sets [bar.f](V([Q.sub.1])), i = 1, ..., [absolute value of C(G)], are pairwise disjoint. Observe that for any [Q.sub.1] [member of] [C.sub.1](G), we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. In addition, Lemma 7.1 implies [abssolute value of f([R.sub.i])] [greater than or equal to] [lg([n.sub.i])] + 1. Therefore, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (13)

establishing Eq. (11).

Assume now

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (14)

which means that the equality holds throughout Eq. (13). This then gives

(i) [absolute value of f(V([Q.sub.1]))] = 1 for [Q.sub.1] [member of] C(G) \ [C.sub.1](G)--This condition also follows from (ii) and (iii) below, therefore it will not be used in the sequel,

(ii) [absolute value of f([R.sub.i])] = [lg([n.sub.i])] + 1 for [Q.sub.1] [member of] [C.sub.1](G);

(iii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Consider a twin set Y . For any v [member of] Y, since f satisfies the Helly property, we deduce from (iii) that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (15)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Note that the statement (ii) implies that [bar.f]([R.sub.i]) cannot have more than one element, as a set of [lg([n.sub.i])] - 1 elements cannot have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] different subsets. Thus, by virtue of the Helly property, we get [absolute value of f([R.sub.i])\f([R.sub.i])] = [lg([n.sub.i])]. This in turn tells us that for each i, f([R.sub.i])\[bar.R]([R.sub.i]) has totally [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] distinct subsets. Finally, by Eq. (15) and the fact that f([R.sub.i])[intersection]f([R.sub.j]) = 0, for any i [not equal to] j, to ensure the representing sets of vertices in Y be pairwise distinct, we find then that Eq. (12) must hold.

To prove that Eq. (12) guarantees the validity of Eq. (14), we trace the argument above in the opposite direction. We construct a representation f whose underlying set is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and its cardinality matches the lower bound of [i.sup.*.sub.h](G): We assign the image of f twin set by twin set. For any twin set Y, suppose that CY (G) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], there is an injection from Y to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], say gY : For any v [member of] Y, we put f(v) = gY(v) [union] {[i.sub.1], ..., [i.sub.}. Clearly, for any u,w [member of] V(G), f(u) [intersection] f(w) [not equal to] 0, if and only if u and w are included in a common maximal clique, thereby showing that f is a representation of G: Moreover, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] when u and w are twins and f(u) [intersection] {1, 2, ..., [absolute value of C(G)]} [not equal to] f(w) [intersection] {1, 2, ..., [absolute value of C(G)]} when u and w are not twins. Hence, f is a family representation of G: Finally, as a consequence of i [member of] f(V([Q.sub.1])), i = 1, ..., [absolute value of C(G)], f must satisfy the Helly property. This completes the proof.

8 Purple graphs and intersection numbers

Owing to Theorem 7.7, we define a purple graph to be a graph G for which Eq. 14 holds.

Observe that Eq. 8 coincides with Eq. 11 when [C.sub.3](G) = [empty set] It is noteworthy that [C.sub.3](G) = [empty set] if and only if G is maximal clique irreducible, in other words, G [member of] SSH: So by Theorems 7.6 and 7.7 we have the following result.

Theorem 8.1 For any maximal clique irreducible graph G, the following statements are equivalent:

(i) G is a purple graph;

(ii) The family intersection number and the Helly family intersection number ofGare both [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] where [c.sub.s] is the number of maximal cliques with special vertices or special edges and [n.sub.i] is the number of special vertices in the ith maximal clique Qi;

(iii) Eq. 12 is valid for each twin set Y [subset or equal to] V (G):

In Example 5.6, we observe that all diamond-free graphs are maximal clique irreducible. Here comes an immediate corollary of Theorem 8.1.

Corollary 8.2 Each diamond-free graph is a purple graph.

Proof: Let G be a diamond-free graph. By Theorem 8.1 we only need to show that each twin set Y of G satisfies Eq. (12).

If Y is a singleton set, Eq. (12) is trivially true. For the remaining case, as G is diamond-free, the result of Mahadev and Wang reported in Example 4.7 implies that CY (G) has only one element, say Qj : We deduce from Lemma 7.4 that [R.sub.j] = Y and hence [Q.sub.j] [member of] [C.sub.1](G): This tells us that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], finishing the proof. 2

We remark that Theorem 7.2 can be easily seen from Theorem 8.1 and Corollary 8.2.

Theorem 8.3 For any purple graph G, the following statements are equivalent:

(i) Each twin set Y with [absolute value of [C.sub.Y] (G)] = 1 is a singleton set;

(ii) G is twin-free;

(iii) The intersection number and the family intersection number of G are equal.

Proof: (i) [right arro] (ii): To prove that G is twin-free, it suffices to show that each twin set Y of G must have size 1: Since G is purple, Theorem 7.7 asserts that Eq. (12) holds in this case. For each clique [Q.sub.i] [member of] [C.sub.Y] (G) [intersection [C.sub.1](G), if any, Lemma 7.4 implies that [R.sub.i] is a twin set of G and [C.sub.Ri] (G) = {[Q.sub.i]}: So we obtain from statement (i) that [n.sub.i] = [absolute value of][R.sub.i} = 1: By Eq. (12) it follows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

This is the result.

(ii) [right arrow] (iii): This is trivial.

(iii) [right arrow] (i): This is Theorem 7.5. 2

In view of Corollary 8.2, the equivalence between statements (ii) and (iii) in Theorem 8.3 generalizes the equivalence of statements (ii) and (iii) in Theorem 1.4. Note that the implications of (ii) [right arrow] (iii) and (iii) [right arrow] (i) in Theorem 8.3 do not rely on the fact that G is purple.

9 Unique representability

In this last section we will present some results on the unique representability problem, especially for purple graphs.

By checking the proof of the part of Eq. (12) [right arrow] Eq. (14) in establishing Theorem 7.7, we can see that all possible minimum-size Helly family representations for a purple graph G have been enumerated there. Actually, the set of such representations is in one-to-one correspondence with the set [[PI].sub.Y] {[g.sub.Y] where Y runs over all twin sets of G and [g.sub.Y] runs over all injections from Y to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] [T.sub.Y]. Especially, if G is twin-free, each twin set Y consists of only one element and the corresponding [T.sub.Y] also only consists of one element, namely the empty set. Thus we know that any twin-free purple graph G is uniquely representable with respect to Helly family representation. Clearly, any twin-free graph is uniquely representable with respect to family representation if and only if it is uniquely representable with respect to multifamily representation. It implies that G is also uniquely representable with respect to Helly multifamily representation. We point out below that a more general result holds true and has a simpler proof.

Theorem 9.1 Every graph is uniquely representable with respect to Helly multifamily representation.

Proof: For any graph G; by Lemma 2.2 we know that [i.sub.h](G) = [absolute value of C(G)]: Let f be a Helly multifamily representation of size [absolute value of C(G)]: Since f satisfies the Helly property, f(V(C)) [not equal to] 0 for each C [member of] C(G). Clearly, [bar.f](V([Q.sub.i]))[intersection](V([Q.sub.j])) = 0 for any two different cliques [Q.sub.i],[Q.sub.j] [member of] C(G). It follows that [absolute value of C(G)] [less than or equal to] [[SIGMA].sub.C[member of]C(G)] [absolute value of (V(C))] [less than or equal to] [absolute value of f(V(G))] = [absolute value of C(G)] which implies that each f(V (C)) is a singleton set. Let f(V (C)) = {[f.sup.C}. Then we know that f(v) = {[f.sup.C] : v [member of] V (C);C 2 C(G)g for each v [member of] V (G): For any two minimum-size Helly multifamily representations [f.sub.1] and [f.sub.2] of G; let [pi] be the bijection from [f.sub.1](V (G)) to [f.sub.2](V (G)) such that [pi] ([f.sup.C.sub.2] for each C [member of] C(G): It is easy to see that [pi] () [f.sub.1] = [f.sub.2].

The following result is an extension of Theorem 1.3. It means that the statement (i) in Theorem 8.3 has a lot to do with the unique representability of graphs. Our proof is similar to that used by Mahadev and Wang [31] in proving Theorem 1.4.

Theorem 9.2 Let G = (V;E) be a graph. Suppose G has a twin set Y with [absolute value of Y] > 1 and [absolute value of [C.sub.Y] (G)] = 1: Then for each family representation f of G; we can find another family representation f0 such that f(V ) = f'(V ) and there is no permutation [pi] of f'(V) such that f' = [pi] () f.

Proof: Since [absolute value of CY (G)] = 1; there exists a unique [Q.sub.i] [member of] [C.sub.1] (G) such that [C.sub.Y] (G) = {[Q.sub.i]} and, in virtue of Lemma 7.4, [R.sub.i] = Y.

If V ([Q.sub.i]) = [R.sub.i]; then [Q.sub.i] itself is a connected component of G. In addition, we have [absolute value of V ([Q.sub.i])]} = [absolute value of Y] > 1.

Thus the result follows from Theorem 1.3.

We turn to consider the case of V ([Q.sub.i]) [not equal to] [R.sub.i]: Let f be a family representation of G. For any [Q.sub.j] [member of] C(G) \ {Q.sub.i]}; we must have f([R.sub.i]) [intersection] f(V ([Q.sub.j])) = [empty set]: Since [absolute value of Y] [greater than or equal to] 2; we can take two vertices a; b [member of] [R.sub.i]. As f is a family representation, we can further assume, w.l.o.g., that there is an element x [member of] f(a) \ f(b): Observe that for any element u [member of] [R.sub.i]; it holds f(u) [not equal to] {x}; considering that f(u) [intersection] f(b) [npt equal to] [empty set]. Consequently, we have ((f(v) [union] f([R.sub.i])) \ {x}) [intersection] f(u) [not equal to] [empty set] for any v [member of] V ([Q.sub.i]) [R.sub.i] and u [member of] [R.sub.i]. Now we

construct a mapping [f.sub.1] according to the rule

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and another mapping [f.sub.2] by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Then we can check that [f.sub.1] and [f.sub.2] are both family representations of G sharing a common underlying set with f: However, the assumption V ([Q.sub.i]) [not equal to] [R.sub.i] implies that we can pick a vertex c [member of] V ([Q.sub.i])\[R.sub.i]. We clearly have [absolute value of [f.sub.2](c)]= [absolute value of [f.sub.1](c)]-1 and hence we have [absolute value of f(c)] [not equal to] [absolute value of [f.sub.1](c)] or [absolute value of f(c)] [not equal to] [absolute value of [f.sub.2](c)]. If the former holds, then take f' = [f.sub.1]; otherwise let f' = [f.sub.2].

Now we return to purple graphs.

Theorem 9.3 A purple graph G is uniquely representable with respect to family representation if and only if it is both twin-free and uniquely representable with respect to multifamily representation.

Proof: If G is uim and twin-free, then G is surely ui.

Conversely, taking into account that a graph must be uim provided it is both ui and twin-free, our task is to show that G is twin-free whenever it is purple and ui. Since G is ui, Theorem 9.2 implies that each twin set Y of G with [absolute value of [C.sub.Y] (G)] = 1 is a singleton set, namely statement (i) of Theorem 8.3 is established. Then we apply Theorem 8.3 to the purple graph G and conclude that G is twin-free, finishing the proof.

In light of Theorem 8.3 and Theorem 9.3, we have an immediate corollary.

Corollary 9.4 A purple graph G is uniquely representable with respect to family representation if and only if i*(G) = i(G) and G is uniquely representable with respect to multifamily representation.

Mahadev and Wang have proved that each diamond-free graph is uniquely representable with respect to multifamily representation [31, Theorem 3.2]. By this result and Corollary 8.2, we can see that Theorem 9.3 is stronger than asserting the equivalence of statements (i) and (ii) in Theorem 1.4, while Corollary 9.4 is stronger than claiming the equivalence of statements (i) and (iii) in Theorem 1.4, respectively.

received February 9, 2008, revised June 20, July 4, 2009, accepted July 10, 2009.

References

[1] M.O. Albertson, K.L. Collins, Duality and perfection for edges in cliques, Jounral of Combinatorial Theory Series B 36 (1984), 298-309.

[2] R. Alter, C.C. Wang, Uniquely intersectable graphs, Discrete Mathematics 18 (1977), 217-226.

[3] I. Anderson, Combinatorics of Finite Sets, Dover Publications, N.Y., 2002.

[4] M. Borowiecki, I. Broere, M. Frick, P. Mihok, G. Semanisin, A survey of hereditary properties of graphs, Discussiones Mathematicae Graph Theory 17 (1997), 5-51.

[5] A. Brandstadt, V.B. Le, J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathmatics and Appllication, 3, SIAM, Philadelphia, 1999.

[6] A. Bretto, S. Ubeda, J. Zerovnik, A polynomial algorithm for the strong Helly property, Information Processing Letters 81 (2002), 55-57.

[7] S. Butenko, W.E. Wilhelm, Clique-detection models in computational biochemistry and genomics, European Journal of Operational Research 173 (2006), 1-17.

[8] F. Cazals, C. Karande, A note on the problem of reporting maximal cliques, Theoretical Computer Science 407 (2008), 564-568.

[9] M.R. Cerioli, J.L. Szwarcfiter, A characterization of edge clique graphs, Ars Combinatoria 60 (2001), 287-292.

[10] M.R. Cerioli, J.L. Szwarcfiter, Edge clique graphs and some classes of chordal graphs, Discrete Mathematics 242 (2002), 31-39.

[11] L.S. Chandran, L. Ibarra, F. Ruskey, J. Sawada, Fast generation of all perfect elimination orderings of a chordal graph, Theoretical Computer Science 307 (2003), 303-317.

[12] G. Chartrand, S.F. Kapoor, T.A. McKee, F. Saba, Edge-clique graphs, Graphs and Combinatorics 7 (1991), 253-264.

[13] G. Chen, M.S. Jacobson, A.E. Kezdy, J. Lehel, E.R. Scheinerman, C. Wang, Clique covering the edges of a locally cobipartite graph, Discrete Mathematics 219 (2000), 17-26.

[14] H.H. Cho, S.-R. Kim, J.Y. Lee, On the graph inequality [[theta].sub.E](G) [greater than or equal to] [[theta].sub.E]([G.sup.m]), Discrete Mathematics 306 (2006), 738-744.

[15] M.S. Chung, D.B. West, The p-intersection number of a complete bipartite graph and orthogonal double coverings of a clique, Combinatorica 14 (1994), 453-461.

[16] C. Davi, The intersection number of an infinite graph, Graph Theory Notes N. Y. 47 (2004), 38-39.

[17] G. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71-76.

[18] M.C. Dourado, F. Protti, J.L. Szwarcfiter, Complexity aspects of the Helly property: Graphs and hypergraphs, The Electronic Journal of Combinatorics #DS17 (2009), 53 pp.

[19] R.D. Dutton, R.C. Brigham, A characterization of competition graphs, Discrete Applied Mathematics 6 (1983), 315-317.

[20] P. Erdos, A.W. Goodman, L. Posa, The representation of a graph by set intersections, Canadian Journal of Mathematics 18 (1966), 106-112.

[21] D.R. Fulkerson, O.A. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics 15 (1965), 835-855.

[22] D. Gale, H.W. Kuhn, A.W. Tucker, Linear Programming and the Theory of Games, in: T.C. Koopmans (Ed.), Activity Analysis of Production and Allocation, Wiley, New York, NY, 1951, pp. 317-329.

[23] F. Gavril, Intersection graphs of Helly families of subtrees, Discrete Applied Mathematics 66 (1996), 45-56.

[24] F. Gavril, Algorithms on circular-arc graphs, Networks 4 (1974), 357-369.

[25] F. Gavril, Algorithm for minimum coloring, maximal clique, minimum covering by cliques and maximum independent set of a chordal graph, SIAM Journal on Computing 1 (1972), 180-187.

[26] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second Edition, Elsevier B. V., Amsterdam, 2004.

[27] Il. Kang, S. Kim, Y. Shin, Y. Nam, Graphs satisfying inequality [theta]([G.sup.2]) [less than or equal to][theta] (G); Discrete Mathematics 250 (2002), 259-264.

[28] J. Korner, Intersection number and capacities of graphs, Discrete Mathematics 142 (1995), 169-184.

[29] L.T. Kou, L.J. Stockmeyer, C.K. Wong, Covering edges by clique with regard to keyword conflicts and intersection graphs, Communications of the ACM 21 (1978), 135-139.

[30] L. Lovasz, Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics 2 (1972), 253-267.

[31] N.V.R. Mahadev, T.-M.Wang, On uniquely intersectable graphs, Discrete Mathematics 207 (1999), 149-159.

[32] T.A. McKee, F.R. McMorris, Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathmatics and Appllication, 2, SIAM, Philadelphia, 1999.

[33] T.S. Michael, T. Quint, Sphericity, cubicity, and edge clique covers of graphs, Discrete Applied Mathematics 154 (2006), 1309-1313.

[34] R.E. Miller, D.E. Miller, A problem of maximum consistent subsets, IBM Research Report RC-240 J.T. Watson Research Center, Yorktown Heights, New York, 1960.

[35] J.W. Moon, L. Moser, On cliques in graphs, Israel J. Math. 3 (1965), 23-28.

[36] K.R. Parthasarathy, S.A. Choudum, The intersection number of K4-free graphs, Colloque sur la Theorie des Graphes (Paris, 1974), Cahiers Centre Etudes Recherche Oper 17 (1975), 301-305.

[37] E. Prisner, Hereditary clique-Helly graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 14 (1993), 216-220.

[38] A. Raychaudhuri, Intersection number and edge clique graphs of chordal and strongly chordal graphs, Congressus Numerantium 67 (1988), 197-204.

[39] A. Raychaudhuri, Edge clique graphs of some important classes of graphs, Ars Combinatoria 32 (1991), 269-278.

[40] F.S. Roberts, On the boxicity and cubicity of a graph, in: Recent Progress in Combinatorics (W.T. Tutte, ed.), Academic Press, New York, 1969, 301-310.

[41] F.S. Roberts, J.H. Spencer, A characterization of clique graphs, Jounral of Combinatorial Theory Series B 10 (1971), 102-108.

[42] D.J. Rose, Triangulated graphs and the elimination process, Journal of Mathematical Analysis and Applications 32 (1970), 597-609.

[43] D.J. Rose, R.E. Tarjan, G.S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing 5 (1976), 266-283.

[44] E.R. Scheinerman, A.N. Trenk, On the fractional intersection number of a graph, Graphs and Combinatorics 15 (1999), 341-351.

[45] R.E. Tarjan, M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs, SIAM Journal on Computing 13 (1984), 565-579.

[46] I. Tomescu, Irreducible coverings by cliques and Sperner's theorem, The Electronic Journal of Combinatorics 9 (2002), #N11, 4pp.

[47] M. Tsuchiya, On intersection numbers, total clique covers and regular graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 30 (1999), 33-43.

[48] M. Tsuchiya, On uniform intersection numbers, Ars Combinatoria 48 (1998), 225-232.

[49] M. Tsuchiya, On antichain intersection numbers, total clique covers and regular graphs, Discrete Mathematics 127 (1994), 305-318.

[50] W.D. Wallis, G.-H. Zhang, On maximal clique irreducible graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 8 (1990), 187-193.

[51] D.B. West, Introduction to Graph Theory, Second Edition, China Machine Press, 2004.

[52] Y. Wu, J. Lu, Poset, competition numbers, and interval graph, submitted, available at http://math.sjtu.edu.cn/teacher/wuyk/poset.pdf

[53] N. Zagaglia Salvi, The intersection number and point-distinguishing chromatic index of a graph, Vishwa Internat. J. Graph Theory 1 (1992), 103-109.

Jing Kong ([double dagger]) and Yaokun Wux ([section]) Department of Mathematics, Shanghai Jiao Tong University, Shanghai, 200240, China.

([dagger]) This work was supported by Science and Technology Commission of Shanghai Municipality (No. 08QA14036, 09XD1402500), Chinese Ministry of Education (No. 108056), National Natural Science Foundation of China (No. 10871128), and Ky and Yu-Fen Fan Fund of American Mathematical Society. We thank the anonymous referees for many useful comments.

([double dagger]) Current address: Department of Mathematics and System Sciences, Taishan University, 271021, Shandong, China.

([section]) Corresponding author. Email: ykwu@sjtu.edu.cn.
COPYRIGHT 2009 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Kong, Jing; Wu, Yaokun
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:9CHIN
Date:Jun 1, 2009
Words:13609
Previous Article:Ore and Erdos type conditions for long cycles in balanced bipartite graphs.
Next Article:Acyclic colourings of graphs with bounded degree.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters