MATEMATIQKI VESNIK

59 (2007), 9–13

UDK 519.175

originalni nauqni rad research paper

SOME PROPERTIES OF ORDERED HYPERGRAPHS

Ch. Eslahchi and A. M. Rahimi

Abstract. In this paper, all graphs and hypergraphs are finite. For any ordered hypergraph H, the associated graph G_{H} of H is defined. Some basic graph-theoretic properties of H and G_{H} are compared and studied in general and specially via the largest negative real root of the clique polynomial of G_{H}. It is also shown that any hypergraph H contains an ordered subhypergraph whose associated graph reflects some graph-theoretic properties of H. Finally, we define the depth of a hypergraph H and introduce a constructive algorithm for coloring of H.

1. Introduction

Throughout this paper, all graphs and hypergraphs are assumed to be finite. In this work, we extend and apply, in a natural way, some of the concepts and results of [2] to ordered hypergraphs. A nonempty set S together with a total ordering “≤” defined on S is called a totally or linearly ordered set. For any two distinct elements a and b in a totally ordered set S, either a < b or b < a. Given any two distinct elements a and b in S with a < b, we define the closed interval [a, b] to be the set {x ∈ S | a ≤ x ≤ b}. For the ease of writing, we use the notation I(a, b) to indicate the interval [a, b] or [b, a] whenever a < b or b < a, respectively.

Definition 1. A hypergraph H = (V, E) with the vertex set V and edge set E is said to be ordered whenever V is a totally ordered set and for every edge e in E, there exist two distinct vertices x and y in V such that e = I(x, y).

By H − x, we mean the ordered subhypergraph of H which is obtained by removing x and all edges containing x. Moreover, for any edge e = I(x, y) of H, H − I(x, y) is the ordered subhypergraph of H which is obtained by just removing e from H and its order is exactly the same order as defined on V (H).

Definition 2. An interval cycle of an ordered hypergraph H is an alternating sequence of distinct vertices v_{1}, v_{2}, …, v_{k} and edges e_{1}, e_{2}, …, e_{k} of H such that I(v_{i}, v_{i} + 1) = e_{i} for all 1 ≤ i ≤ k where v_{k} + 1 = v_{1}.

AMS Subject Classification: 05C65, 05C99

Keywords and phrases: Hypergraph, Clique Polynomial, Interval cycle.

An interval girth of an ordered hypergraph H, containing an interval cycle, is the minimum size of the length of all interval cycles of H and is denoted by Ig(H). We follow [1] for the classical definition of a hypergraph cycle (resp., girth). A cycle in a hypergraph H is an alternating sequence of distinct vertices and edges of the form v_{1}, e_{1}, v_{2}, e_{2}, …, v_{k}, e_{k}, v_{1}, such that v_{i}, v_{i} + 1 is in e_{i} for all 1 ≤ i ≤ k − 1 with v_{k}, v_{1} ∈ e_{k}. The girth of a hypergraph H, containing a cycle, is the shortest size of the length of cycles of H.

Note that every interval cycle is a cycle but the converse is not true in general which implies g(H) < ig(H). For example, the ordered hypergraph H with the vertex set {1, 2, 3, 4, 5} (with usual ordering) and edge set {I(1, 4), I(3, 5), I(2, 5)} has a 3-cycle but does not have any interval cycles.

Definition 3. For a given ordered hypergraph H, the associated graph of H is defined to be the simple graph G_{H} with the vertex set V (G_{H}) = V (H) and any 2-element set of distinct vertices x, y ∈ V (G_{H}) is an edge in G_{H} whenever I(x, y) is an edge of H.

Remark 1. It is clear that every interval cycle of an ordered hypergraph H is a cycle in its associated graph. Consequently, the interval girth of H is equal to the girth of G_{H}.

We end this section by recalling some of the results from [2]. The authors in [2], by an elementary method, have shown that the clique polynomial of a simple graph G always has a negative real root whose largest one is denoted by ξ_{G} ≥ −1. From this, they have presented a simple argument on Turan’s Theorem that in any triangle-free graph, the number of edges is always less than or equal to \frac{n^{2}}{4} where n is the number of vertices of G. They have also shown that for any induced (resp., spanning) subgraph G′ of G, ξ_{G′} ≤ ξ_{G} (resp., ξ_{G′} ≥ ξ_{G}). By applying these facts, they verified that the following results are always true for any simple graph G.

Proposition 1. For every simple graph G with n vertices, the following results are true:

1. Let α(G) be the independence number of G. Then α(G) ≤ \frac{−1}{ξ_{G}}.

2. χ(G) ≥ −|V (G)|ξ_{G}.

3. Suppose G is not complete and let g(G) be the girth of G Then g(G) ≤ \frac{−1}{ξ_{G}^{2}+ξ_{G}}.

4. If G is not a complete graph and og(G) denotes the smallest size of the length of odd cycles of G, then og(G) ≤ \frac{−1}{ξ_{G}^{2}+ξ_{G}}.

5. If n ≥ 4 and ξ_{G} > \frac{1}{2}(−1 + \sqrt{1 − \frac{4}{n}}), then G is not Hamiltonian.

6. If n ≥ 2 and ξ_{G} > −1 + \sqrt{1 − \frac{2}{n}} , then G does not have any perfect matching.

2. The associated graph of an ordered hypergraph

In this section, We shall exploit an ordered hypergraph as a bridge between its associated simple graph and its ambient hypergraph H to find sharp upper bounds for the chromatic number of H and an upper bound for the girth of H.

Theorem 2. The following results are always true in any ordered hypergraph H.

1. H is 2-colorable.

2. α(H) ≥ \frac{n}{2} where α(H) (resp., n) is the independence number (resp., number of vertices) of H.

3. For any non-negative integer m, there exists an ordered hypergraph H such that χ(G_{H}) − χ(H) ≥ m or equivalently, χ(G_{H}) ≥ m + 2.

4. Turan’s theorem: If H is triangle-free, then |E(H)| ≤ \frac{|V (H)|^{2}}{4} .

Proof. Let V (H) = {x_{1}, x_{2}, …, x_{n}} where x_{i} < x_{j} if and only if i < j. We assign color 1 to the vertices with odd subscripts and 2 to the other vertices. Consequently, this color assignment is a two coloring of H. Part 2 can be followed directly from part 1. Part 3 is an immediate consequence of part 2 and Theorem 3. Part 4 follows from Turan’s theorem on graphs, |E(H)| = |E(G_{H})|, and the fact that every triangle free ordered hypergraph is also interval triangle free which implies G_{H} is a triangle free graph.

In the following example we show that the converse of part 1 in the above theorem is not true in general.

Example 1. Let H be a hypergraph with the vertex set V (H) = {1, 2, 3, 4, 5} and edge set E(H) = {{1, 2, 3}, {1, 2, 4}, {1, 2, 5}}. Now, it is not difficult to show that H is 2-colorable which can not be ordered by our definition.

Theorem 3. For every simple graph G, there exists an ordered hypergraph H whose associated graph G_{H} is isomorphic to G.

Proof. The proof by induction on the number of vertices of G. Obviously, the result is valid for n = |V (G)| = 3. Let n ≥ 3 be an integer and G a simple graph with n+1 vertices. Let G′ = G − x be a subgraph of G where x ∈ V (G) is an arbitrary vertex. Now, by induction hypothesis, there exists an ordered hypergraph H′ whose associated graph is isomorphic to G′. We construct an ordered hypergraph H by adding x to V (H′) to get V (H) = V (H′) ∪ x and defining an order on V (H) as follows: Suppose “≤′” is the order relation on H’. We define “≤” to be the extension of “≤′” on V (H) by assuming that y ≤ x for all y ⊂ V (H′) and I(a, x) is an edge in H whenever there is an edge between a and x in G. By this construction, G is isomorphic to G_{H}.

Remark 2. In the above theorem, we can also construct H by assuming that x is the smallest element in the vertex set of H.

Remark 3. Every hypergraph contains an induced ordered subhypergraph. For example, any minimal edge of an arbitrary hypergraph H with its vertices is an induced ordered subhypergraph of H.

Theorem 4. Let M be an induced ordered subhypergraph of a hypergraph H. Then g(H) ≤ g(M) ≤ Ig(M) ≤ −1/ξ_{G_{M}}^{2} + ξ_{G_{M}}. This inequality is also valid whenever g(H) is replaced by the shortest length of odd cycles of H.

Proof. Clearly, the girth of H is at most the girth of M. Now, the proof can be followed directly by applying Remark 1 and Proposition 1.

Next, by applying the fact that any arbitrary hypergraph H contains a maximal induced ordered subhypergraph, we can obtain an upper bound for the chromatic number of H.

Lemma 5. Let M be a maximal induced ordered subhypergraph of the hypergraph H and H_{1} = H − M. Then χ(H) ≤ χ(H_{1}) + 2.

Proof. It suffices to color M by two colors and H_{1} by χ(H_{1}) new colors different from colors of M.

The following example shows that the bound in the above theorem is sharp. Example 2. Let M be an ordered hypergraph and H′ be an arbitrary hy-

pergraph such that V (M) ∩ V (H′) = ∅. Let H be the hypergraph with the vertex set V (H) = V (M) ∪ V (H′) and the edge set E(H) = E(M) ∪ E(H′) ∪ {{x, y} | x ∈ V (M), y ∈ V (H′)}. By this construction, M is a maximal induced ordered subhypergraph of H and χ(H) = χ(H′) + 2.

In order to write the next definition, we construct a sequence H_{1}, H_{2}, …, H_{l} of subhypergraphs of H with l ≥ 1 as follows: H_{1} a maximal induced ordered subhypergraph of H, H_{2} a maximal induced ordered subhypergraph of H − H_{1}, …, H_{l−1} a maximal induced ordered subhypergraph of H − ⋃_{1≤j≤l−2} H_{j} and H_{l} = H − ⋃_{1≤j≤l−1} H_{j} is an induced ordered subhypergraph of H. The sequence H_{1}, H_{2}, …, H_{l} is called an extracted sequence of subhypergraphs of H.

Definition 4. The depth of an hypergraph H, denoted by d(H), is the minimum length of all extracted sequences of subhypergraphs of H.

Theorem 6. For any hypergraph H, we have χ(H) ≤ 2d(H).

Proof. The proof by induction on the depth of H. If d(H) = 1 then H is an ordered hypergraph and χ(H) = 2d(H). Now suppose the result is true for any hypergraph H′ with d(H′) < d(H). Let H_{1}, H_{2}, …, H_{l} be an extracted sequences of subhypergraphs of H. Consider the hypergraph H′ = H − H_{1}. By Lemma 5 we have χ(H) ≤ χ(H′) + 2. Now, since d(H′) = d(H) − 1, the result is straightforward by induction hypothesis.

By a complete hypergraph H, we mean a hypergraph such that every subset with at least two elements of its vertex set is an edge of H. Note that the subhypergraphs generated by two vertices are the only maximal induced ordered subhypergraphs of H. Therefore we can conclude that the depth of H is [\frac{|V (H)|}{2}]+1 or [\frac{|V (H)|}{2}] whenever |V (H)| is odd or even, respectively. Moreover, a complete hypergraph with an even number of vertices is an example of a sharp bound for the above theorem.

Next, we introduce a greedy algorithm to construct an ordered subhypergraph in an arbitrary hypergraph.

Algorithm. Let H be an arbitrary hypergraph.

Step 1. Choose two arbitrary vertices x_{1} and x_{2} in H. we assume an order on the set {x_{1}, x_{2}} by x_{1} < x_{2}.

Step 2. Let A = {a_{1}, a_{2}, ⋯, a_{k}} be a subset of V (H) with the order relation < such that the induced subhypergraph of H generated by (A, <) is an ordered subhypergraph of H. Choose a vertex x ∈ V (H) − A and consider the orders x < a_{1} < a_{2} < ⋯ < a_{k}, a_{1} < x < a_{2} < ⋯ < a_{k}, …, and a_{1} < a_{2} < ⋯ < a_{k} < x on the set A ∪ {x}. If A ∪ {x} with one of the above orders (for example a_{1} < a_{2} < ⋯ < a_{j} < x < a_{j+1} < ⋯ < x_{k}) constructs an induced ordered subhypergraph of H, set A = A ∪ {x} with this order and go to step 2. If there is no such vertex,

write A

set H = H − A and go to step 1. If H = ∅, the algorithm is done.

Remark. We can obtain a coloring for a hypergraph H, by coloring the ordered subhypergraphs of H which are constructed in the above algorithm.

REFERENCES

[1] C. Berge, Graphs and Hypergraphs, New York: Elsevier, 1973.

[2] H. Hajiabolhassan and M. L. Mehrabadi, On clique polynomials, Australasian Journal of Combinatorics, 18 (1998), 313–316.

(received 24.09.2005)

Department of Mathematical Sciences, Shahid Beheshti University, Tehran, Iran Institute for Studies in Theoretical Physics and Mathematics, P.O. Box: 19395-5746, Tehran, Iran.

E-mail: ch-eslahchi@sbu.ac.ir, amrahimi@ipm.ir