Boxicity food webs

PART III

GRAPH THEORY

224

13

Food Webs

Author: Robert A. McGuigan, Department of Mathematics, Westfield State College.

Prerequisites: The prerequisites for this chapter are basic concepts of graph theory. See Sections 9.1 and 9.2 of Discrete Mathematics and Its Applications.

Introduction A food web is a directed graph modeling the predator-prey relationship in an ecological community. We will use this directed graph to study the question of the minimum number of parameters needed to describe ecological competition. For this purpose we will consider how graphs can be represented as intersection graphs of families of sets.

We will also investigate the axiomatic description of measures of status in food webs.

Competition In an ecological system, the various species of plants and animals occupy niches defined by the availability of resources. The resources might be defined in terms of factors such as temperature, moisture, degree of acidity, amounts of nutrients,

225

226 Applications of Discrete Mathematics

and so on. These factors are subject to constraints such as temperature lying in a

certain range, pH lying within certain limits, etc. The combination of all these constraints for a species then defines a region in n-dimensional Euclidean space, where n is the number of factors. We can call this region the ecological niche of the species in question.

For example, suppose we restrict ourselves to three factors, such as tem- perature, nutrients, and pH. Assume that the temperature must be between t1 and t2 degrees, the amount of nutrients between n1 and n2 and the pH be- tween a1 and a2. Then the ecological niche these define occupies the region of 3-dimensional Euclidean space shown in Figure 1.

Figure 1. An ecological niche.

Euclidean space which has as dimensions the various factors of tempera- ture, pH, etc., is called an ecological phase space. Generally, no two distinct species will have the same ecological niche in phase space; however, two species compete if their ecological niches have non-empty intersection. A basic prin- ciple of ecology, known as the principle of competitive exclusion, dictates that species whose niches are too similar, or overlap too much, cannot coexist. If the factors defining the niche are independent, then the niche in phase space would be a box such as that in Figure 1. If the factors are not independent, i.e. the level of one depends on levels of others, then the niche would be some other type of set, e.g. convex, but not a box.

For example, consider the two factors temperature (t) and per cent humid- ity (h). We might have constraints such as: t must be between 0 and 100, and h must be between 0 and 100t − t2. In this case temperature and humidity are not independent; the possible values of h depend on the values of t. The region in two-dimensional space defined by these constraints is not a rectangle.

Our discussion of ecological communities and related concepts such as

Chapter 13 Food Webs 227

species, food webs, and competition will be somewhat oversimplified in order to make a brief presentation possible. Interested readers should consult refer- ence [1] for an in-depth treatment of these topics. Our mathematical treatment follows that of reference [6].

Food Webs It may be difficult to know all the factors which determine an ecological niche, and some factors may be relatively unimportant. Hence it is useful to start with the concept of competition and try to find the minimum number of dimensions necessary for a phase space in which competition can be represented by niche overlap.

One approach to this question is to consider the notion of the food web of an ecological community.

Definition 1 A food web of an ecological community is a directed graph with a vertex for each species in the community and a directed edge from the vertex representing species A to the vertex representing species B if and only if A preys on B.

Figure 2 shows a simple food web for a community of seven species: robin, fox, grasshopper, raccoon, salamander, milksnake, and toad.

Figure 2. A simple food web.

We can define competition using the food web. Two species compete if and only if they have a common prey. Thus, in the example of Figure 2, raccoon and fox compete (since robin is a common prey), milksnake and raccoon compete,

228 Applications of Discrete Mathematics

while salamander and robin do not compete. We use this competition relation to define a graph called the competition graph.

Definition 2 The competition graph of a food web is a simple graph with a vertex for each species. Two vertices are joined by an (undirected) edge if and only if the species they represent have a common prey.

Example 1 Find the competition graph for the food web of Figure 2.

Solution: The competition graph for this food web is shown in Figure 3.

Figure 3. A competition graph.

To represent the competition relation in phase space we want to assign to each vertex of the competition graph a subset of Euclidean space of some di- mension in such a way that two vertices are joined by an edge in the competition graph if and only if the sets assigned to these vertices have non-empty inter- section. Figure 4 shows a representation of the competition graph of Figure 3, using an interval for each vertex. We have thus represented the competition graph using only one dimension.

Figure 4. Interval representation of a competition graph.

We can now state a general mathematical problem, but first we need to develop some terminology.

Chapter 13 Food Webs 229

Definition 3 A graph is an intersection graph for a family of sets if each vertex is assigned a set in such a way that two vertices are joined by an edge if and only if the corresponding sets have non-empty intersection.

Definition 4 A graph is called an interval graph if it is the intersection graph for a family of closed intervals.

Our goal is the representation of competition graphs of families of sets in Euclidean n-space. Clearly the simplest case would be that of competition graphs that are interval graphs. This would mean that only one ecological factor is necessary to describe niche overlap.

Example 2 Find the interval graph for the family of closed intervals A = [1, 3], B = [2, 6], C = [5, 8], D = [4, 5].

Solution: We use the definition of intersection graph to obtain the graph of Figure 5.

Figure 5. An intersection graph.

Example 3 Prove that the 4-cycle graph C4 of Figure 6 is not an interval graph.

Solution: The proof depends on the order properties of the real numbers. Let the interval corresponding to vertex n be [nl, nr]. Since the intervals for vertices 1 and 2 overlap, we must have either 1l ≤ 2l ≤ 1r ≤ 2r or 2l ≤ 1l ≤ 2r ≤ 1r, Assume for specificity that 1l ≤ 2l ≤ 1r ≤ 2r. The argument for the other case is analogous.

Since the interval for vertex 3 must meet that for vertex 2 and must not meet that for vertex 1, we must have 1l ≤ 2l ≤ 1r < 3l ≤ 2r. Now the interval for vertex 4 must meet those for both vertices 1 and 3, so we have to have 1l ≤ 4l ≤ 1r and 3l ≤ 4r ≤ 3r since interval 1 lies entirely to the left of interval 3. However, since 2l ≤ 1r < 3l ≤ 2r, the intervals for vertices 2 and 4 overlap, which is forbidden.

230 Applications of Discrete Mathematics

Figure 6. A graph that is not an interval graph.

The 4-cycle can, however, be represented as the intersection graph of a family of boxes in Euclidean 2-space, as shown in Figure 7.

There are several methods known for determining whether a simple graph is an interval graph. A detailed discussion of this topic may be found in Roberts’ book [6]. We simply state the characterization due to Gilmore and Hoffman [3] without proof. Before the characterization can be stated, we need some definitions.

Figure 7. A box representation.

Definition 5 A graph H is a generated subgraph of a graph G if the vertices of H are a subset of the vertices of G and vertices in H are adjacent in H if and only if they are adjacent in G.

Definition 6 The complement of a graph G is the graph G where the vertices of G are the vertices of G, and two vertices in G are adjacent if and only if they are not adjacent in G.

Definition 7 An orientation of a graph G is an assignment of a direction to each edge in G (which makes G into a directed graph).

An orientation is transitive if whenever (u, v) and (v, w) are directed edges, then (u, w) is a directed edge.

Chapter 13 Food Webs 231

The characterization due to Gilmore and Hoffman is given by the following theorem.

Theorem 1 A graph G is an interval graph if and only if it satisfies the following two conditions:

(i) The four-cycle C4 is not a generated subgraph of G, (ii) The complement of G is transitively orientable.

Our goal in our study of ecological competition is the representation of niches in Euclidean space and competition by niche overlap. It seems desirable in an ideal representation that the factors determining the dimension of the eco- logical phase space would be independent and the niches would be represented as “boxes”, or Cartesian products of intervals. This leads us to the next part of this discussion, namely, when can we represent a graph as the intersection graph of a family of boxes in n-space.

Boxicity

Definition 8 The boxicity of a graph G is the smallest n such that G is the intersection graph of a family of boxes in Euclidean n-space.

Note that an interval graph is simply a graph with boxicity equal to 1. It is not entirely clear that every simple graph has a boxicity. The following theorem resolves this difficulty.

Theorem 2 Every graph G with n vertices is the intersection graph of a family of boxes in Euclidean n-space.

Proof: Let v1, v2, . . . , vn be the vertices of G. A box in Euclidean n-dimen- sional space is the set of all n-tuples of real numbers (x1, x2, . . . , xn) such that each xi is in some closed interval Ii. Now, for each k = 1 . . . , n and each vertex vi, define closed intervals Ik(vi) as follows.

Ik(vi) =

⎧⎪⎨ ⎪⎩

[0, 1] if i = k [1, 2] if i = k and {vi, vk} is an edge in G [2, 3] if i = k and {vi, vk} is not an edge in G.

For each vertex vi define a box B(vi) in Euclidean n-space by

B(vi) = {(x1, x2, . . . , xn) |xj ∈ Ij(vi) for j = 1, . . . , n}.

232 Applications of Discrete Mathematics

Thus, the box B(vi) corresponding to vi is the Cartesian product of the intervals Ij(vi) for j = 1, . . . , n.

Now we show that vi and vj are adjacent in G if and only if B(vi)∩B(vj) = ∅. Thus the graph G is the intersection graph of the family of boxes B(vi). First, suppose that there is an edge joining vl and vm. If k is different from both l and m, then according to the definition, Ik(vl)∩ Ik(vm) is [1, 2]∩ [1, 2], [1, 2]∩ [2, 3], or [2, 3] ∩ [2, 3]. In any case we have Ik(vl) ∩ Ik(vm) = ∅. If k=l or k=m then Ik(vl) ∩ Ik(vm) = [1, 2] ∩ [0, 1] = ∅. So, if there is an edge joining ve and vm, then for all k, Ik(vl) ∩ Ik(vm) = ∅. Hence B(vl) ∩ B(vm) = ∅.

Now suppose that B(vl)∩B(vm) = ∅. Then for each k from l to n, Ik(vl)∩ Ik(vm) = ∅. Set k = l then Il(vl) = [0, 1] and Il(vm) must be [1, 2] for the intersection to be nonempty. By definition of Il(vm), vl and vm are adjacent. Thus G is the intersection graph of the family of boxes B(vi).

This theorem shows that boxicity is well-defined. Unfortunately, there is no efficient algorithm known for determining the boxicity of a general graph. There is no characterization known for graphs of any specific boxicity other than 1.

In fact, there are not many general classes of graphs for which the boxicity is known. It is not hard to see that the boxicity of the n-cycle Cn is 2 for n = 4 or larger, and this is left as Exercise 6. Another general class of graphs for which the boxicity is known is the complete p-partite graphs. These are the graphs Kn1,n2,...,np defined as follows: there are n1 + · · ·+ np vertices partitioned into p classes, where the ith class has ni vertices. Within a class no vertices are adjacent, and every vertex in any class is adjacent to all vertices in the other classes. Roberts [6] showed that the boxicity of Kn1,...,np is equal to the number of ni that are larger than 1.

One result which helps somewhat in calculating the boxicity of a graph is due to Gabai [2]. This theorem depends on the concept of independence of a set of edges.

Definition 9 A set of edges in a graph is independent if they have no vertices in common.

Gabai’s theorem [2] is the following, stated without proof.

Theorem3 Let G be a simple graph. If the maximum size of an independent set of edges of G is k, then G has boxicity less than or equal to k. Also, if G has a generated subgraph consisting of k independent edges then the boxicity of G is greater than or equal to k.

Chapter 13 Food Webs 233

Gabai’s theorem is useful in determining the boxicity of relatively small graphs and for certain families. In any case it limits the amount of trial and error needed.

In our study of competition we search for the representation of the com- petition graph of a food web as the intersection graph of a family of sets in Euclidean n-space for some n. As a consequence of the theorem proved above, this representation is always possible. Furthermore, we can use the boxicity of the competition graph as an indicator of the minimum number of factors essential for describing competition in the community. Cohen [1] has studied more than 30 single-habitat food webs published in the ecological literature and has found that the competition graphs of all of them are interval graphs. That is, in all cases one dimension suffices to represent competition by niche overlap. It is not known whether this is a general law of ecology, but it does raise many interesting questions. In some single-habitat communities a single dimension for the niche space can be identified. It may be some obviously linear factor such as temperature, body length or depth in water. However, it may well be that more than one single dimension will work. And, of course, we can’t expect the single-niche dimension to be the same from community to community.