Threshold Graphs and Related Topics

By N.V.R. Mahadev and U.N. Peled

Threshold graphs have a beautiful structure and possess many important mathematical properties. They have applications in many areas including computer science and psychology. Over the last 20 years the interest in threshold graphs has increased significantly, and the subject continues to attract much attention.

The book contains many open problems and research ideas which will appeal to graduate students and researchers interested in graph theory. But above all Threshold Graphs and Related Topics provides a valuable source of information for all those working in this field.

• Language: English
• Publisher: Elsevier Science
• Release date: Sep 13, 1995
• ISBN: 9780080543000

Book preview

[GJ78].

Chapter 1

Threshold Graphs

1.1 Motivation

Threshold graphs play an important role in graph theory as well as in several applied areas such as psychology, computer science, scheduling theory, etc. In fact, these graphs were discovered independently and reported in different journals by people working in different areas. Either these graphs, or a close kin of these graphs, the difference graphs, have been used implicitly in several other articles. Most properties of threshold graphs can be easily translated to properties of difference graphs and vice versa.

Chvátal and Hammer [CH73, CH77] coined the name threshold graphs and studied these graphs for their application in set-packing problems. About the same time Henderson and Zalcstein [HZ77] discovered the same graphs and called them PV-chunk definable graphs. Their discovery is motivated by applications in parallel processing. More specifically they found that these graphs can be used to control the flow of information between processors, much like the traffic lights used in controlling the flow of traffic. Ordman [Ord85] found other uses for these graphs in resource allocation problems. Ecker and Zaks [EZ77] discovered these graphs independently and investigated them for their use in graph labeling as applied to open shop scheduling. Koop [Koo86] studied cyclic scheduling and manpower allocation and found that the problem can be modeled using threshold graphs and threshold hypergraphs. Doignon et al. [DDF84] investigated a special kind of order relations called biorders, that were used in the study of learning behaviors of children. These biorders, it turns out, are simply the difference graphs. Several results of these authors were discovered independently by others in graph theory. Yannakakis [Yan82] proved in 1982 an important result in complexity theory, namely that recognizing whether or not a given poset has dimension at most three is NP-complete. At the center of his proof was the class of graphs that he called chain graphs, which are nothing but difference graphs. Cogis [Cog82a] has studied the so-called Ferrers digraphs, which are essentially the difference graphs. Perhaps the earliest use of threshold graphs is in graph theory itself, namely in the study of degree sequences of graphs. Koren [Kor73] studied those degree sequences that are not convex combinations of other degree sequences; others have studied graphs whose degree sequences majorize the degree sequences of all other graphs. In both cases it turns out that the corresponding graphs are precisely the threshold graphs.

All these examples show that threshold graphs have been used in various fields with different applications. We bring together the works of all these people and present a unified approach to their methods. We describe most of the applications of threshold graphs and their generalizations that are known. This book should be of interest to people from many different fields such as mathematical psychology, graph theory, parallel processing, resource allocations, scheduling theory, etc. We will not be surprised if new applications were discovered for these graphs, since they possess a rich and interesting structure. Several people worked on different generalizations and variations of threshold graphs. Most of these generalizations have their own applications as well. Almost 100 different articles have been written on topics related to threshold graphs in a relatively short period of time. This book brings together several important results related to threshold graphs that were scattered in various journals specializing in different disciplines.

1.2 Basic Characterizations

This chapter defines the threshold graphs and presents their basic properties. Threshold graphs have been defined by Chvátal and Hammer [CH73, CH77] as follows.

Definition 1.2.1

A graph G = (V, E) is called a threshold graph when there exist non-negative reals wv, v ∈ V and t such that

(1.1)

where w(U) = Σν∈U wν.

To paraphrase this definition, G is a threshold graph whenever one can assign vertex-weights such that a set of vertices is stable if and only if its total weight does not exceed a certain threshold (t). Yet another interpretation is that G is a threshold graph if and only if some hyperplane, called a separator, strictly separates the characteristic vectors of the stable sets of G from the characteristic vectors of the non-stable sets. In other words, the Boolean function that selects the stable sets of vertices is a threshold function [Mur79]. Figure 1.1 illustrates a threshold graph along with appropriate vertex-weights and threshold.

Figure 1.1 A threshold graph with vertex-weights and threshold.

The following definitions are used in describing the structure of threshold graphs.

Definition 1.2.2

An alternating 4-cycle of a graph G = (V, E) is a configuration consisting of distinct vertices a, b, c, d such that ab, cd ∈ E and ac, bd ∉ E. By considering the presence or absence of edges ad and bc, we see that the vertices of an alternating 4-cycle induce a path P4, a square C4, or a matching 2K2. See Figure 1.2

Figure 1.2 An alternating 4-cycle and the possible subgraphs it induces. A solid line indicates a present edge and a dashed line a missing edge.

In order to characterize threshold graphs, we introduce a partition of the vertices of any graph by their degrees as follows.

Definition 1.2.3

Let G = (V, E) be a graph whose distinct positive vertex-degrees are δ1 < … < δm, and let δ0 = 0 (even if no vertex of degree 0 exists), Δm+1 = |V| − 1. Let Di = {v ∈ V: deg(v) = δi} for i = 0,…,m. The sequence D0,…,Dm is called the degree partition of G.

The basic characterizations of threshold graphs are given by the following theorem.

Theorem 1.2.4 ([CH73, CH77, EZ77, Gol80, HZ77])

For a graph G = (V, E), the following are equivalent:

1. G is a threshold graph;

2. G does not have an alternating 4-cycle;

3. G is a split graph G(K, S) (i.e., its vertices can be partitioned into a clique K and a stable set S) and the neighborhoods of the vertices of S are nested;

4. G can be constructed from the one-vertex graph by repeatedly adding an isolated vertex or a dominating vertex;

5. the vicinal preorder of G is total;

6. for each v ∈ Dk,

(1.2)

(1.3)

in other words, for x ∈ Di and y ∈ Dj, x is adjacent to y if and only if i + j > m; Figure 1.3 illustrates this with m = 6 and m = 7;

Figure 1.3 Illustrating the degree partition of two threshold graphs. A line between Di and Dj indicates that every vertex of Di is adjacent to every vertex of Dj. An oval indicates that the included vertices form a clique.

7. 

(1.4)

8. there exist non-negative reals wv, v ∈ V and t such that for distinct vertices u and v,

(1.5)

Proof

1) ⇒ 2): If G has an alternating 4-cycle a, b, c, d with ab, cd ∈ E and ad, bc ∉ E, then

These inequalities are clearly inconsistent.

2) ⇒ 3): Let K be a largest clique in G. If V − K contained an edge ab, then by the maximality of |K|, there exist distinct vertices c, d in K with ad, bc ∉ E, creating an alternating 4-cycle on a, b, c, d, a contradiction. Thus S = V − K is a stable set and G(K, S) is a split graph. Moreover, every two vertices of S are comparable, for otherwise there is an alternating 4-cycle.

3) ⇒ 4): It is enough to show that G has an isolated vertex or a dominating vertex, for if such a vertex is removed, the remaining graph still satisfies Condition 3. We may then assume that S ≠ ø. If G has no isolated vertex in S, then the vertex u ∈ S with the smallest neighborhood has some neighbor v ∈ K. Then v is a dominating vertex of G.

4) ⇒ 1): We show by induction on the number of vertices that we can assign positive integer vertex-weights satisfying (1.1). For the one-vertex graph, let the vertex-weight and t be 1. If a graph has this property and we add a dominating vertex v, then assign v the weight t and leave the other weights and t unchanged. If a graph has this property and we add an isolated vertex v, then double the old vertex-weights, replace t by 2t + 1, and assign v the weight 1.

2) ⇒ 5): If G has two non-comparable vertices a and d, then a has a neighbor b that is not a neighbor of d, and d has a neighbor c that is not a neighbor of a, and thus there is an alternating 4-cycle a, b, c, d, contradicting Condition 2.

5) ⇒ 6): If m = 1, then D1 is a clique and Equation (1.3) is satisfied. So assume m > 1. From Condition 5 it follows that

(1.6)

Choose representatives xj ∈ Dj, j = 1,…,m. Then

(1.7)

It follows from (1.6) and (1.7) that x1 is adjacent to xm and therefore Dm ⊆ N(x1) and also N[xm] = D1 ∪ … ∪ Dm and N[Dm] = D1 ∪ … ∪ Dm. It then follows that N(x1) = Dm, since if x1 were adjacent to xj for some j < m, then N[xj] would also equal to D1 ∪ … ∪ Dm and xj would have to belong to Dm, a contradiction. From this we obtain N(D1) = Dm.

If m = 2 we are done. So assume m > 2. It now follows from (1.6) and (1.7) that x2 is adjacent to xm−1 and therefore Dm ∪ Dm−1 ⊆ N(D2). Thus N[Dm−1] = D2 ∪ … ∪ Dm and hence N(D2) = Dm ∪ Dm−1. Proceeding like this we establish Condition 6.

6) ⇒ 7): The result follows from .

7) ⇒ 6): From (1.4) with k = m and the value of δm+1 we have that δm = δm+1 − |D0| = |D1| + … + |Dm| − 1. Since D0 is the set of isolated vertices, Equation (1.3) holds for k = m. If m = 1 we are done, so assume that m > 1. From (1.4) with k = 0 and the value of δ0 we have that δ1 = |Dm| and now Equation (1.2) holds for k = 1. If m = 2 we are done, so assume m > 2. Now from (1.4) with k = m − 1 we have δm−1 = |D2| + … + |Dm| − 1. Since N(D1) = Dm, Equation (1.3) holds for k = m − 1 and hence by (1.4) with k = 1 Equation (1.2) holds for k = 2. Proceeding like this we establish Condition 6.

6) ⇒ 8): Assign the weight j to every vertex of Dj for j = 0,…,m and let t = m.

8) ⇒ 2): The proof is the same as 1) ⇒ 2).

. However, it follows easily from Condition 6 that

(1.8)

Exercises

1. Let d = (d1 ≥ … ≥ dn) be a degree sequence, and define

Prove that d is a degree sequence of a threshold graph if and only if ei = di + 1 for i = 1,…,f.

2. Show that if a graph G has exactly one pair of vertices with equal degrees, then G is a threshold graph and the equal degrees are equal to both f and df of Exercise 1 (Ruch and Gutman[RG79]).

1.3 Minimizing Integral Weights

Although we defined in Section 1.2 a threshold graph G = (V, E) as a graph having a separator with non-negative real coefficients, it is clear that we could equivalently require the separator to have non-negative integral coefficients. In that case, the vertex-weights w satisfy

(1.9)

(1.10)

Orlin [Orl77] proved the surprising result that for every threshold graph, if we minimize t subject only to the inequalities (1.9), (1.10) and w ≥ 0, then the optimum solution (w, t) is unique and integral. Moreover, it minimizes each individual w(vj) at the same time.

Theorem 1.3.1 (Orlin)

Let G = (V, E) be a threshold graph with the vicinal preorder vi ⪅ … ⪅ vn of its vertices. Consider the linear program

(1.11)

The optimum solution (w, t) of (1.11) is unique and integral, and also minimizes each w(vj). It is given by the following computation. Let s be the smallest index j such that vjvj+1 ∈ E. If no such index exists, set s = n. Then

(1.12)

where f(j) is the smallest i satisfying vivj ∈ E.

An example of the optimum solution was shown in Figure 1.1.

Proof

We show that the constraints of the linear program (1.11) impose lower bounds on t and each w(vj), and that (1.12) gives a feasible solution that meets all these bounds, hence in particular it is an optimal solution. We note first that by definition of s and by the vicinal preorder, the set S = {v1,…,vs} is stable and its complement K = {vs+1,…,vn} is a clique. The setting w(vj) = 0 for isolated vj meets the lower bound of 0 imposed by non-negativity in (1.11). It also follows from the vicinal preorder that each non-isolated vertex vj ∈ S has a neighbor v ∈ K such that vvi ∉ E for all vi vj. It then follows from (1.9) and (1.10) that w(v) + w(vj) ≥ t , and this lower bound is met by (1.12). Further, since S , which is also met by (1.12). Again, for vj ∈ K, which is met by (1.12) (note that νf(j) ∈ S).

To see that (1.12) gives a feasible solution, note first that it satisfies 0 ≤ w(ν1) ≤ … ≤ w(νn). Every edge of G has at least one endpoint in K. For each vj ∈ K, since w(νj) + w(νf(j)) = t + 1, it follows that w(vj) + w(v) ≥ t + 1 for every neighbor v of vj. Thus (1.10) is satisfied. To verify (1.9), it is enough to consider the maximal stable sets. G has exactly n − s + 1 maximal stable sets, namely S, which satisfies (1.9) with equality, and the sets {νj, ν1, …, νf(j)-1} for j > s. Since νf(j) νf(j)−1, each of the other maximal stable sets also satisfies (1.9) with equality.

Finally, we show the uniqueness of the optimum (1.12). Denote by (w, t) the optimal solution given by (1.12) and let (w′, t) be any optimal solution. Then w ≤ w′ as we have shown. Therefore, since S is stable, (1.9) on (w′, t) implies

which in turn implies that w′ agrees with w on S. A similar argument involving the set {νj, ν1, …, νf(j)−1} for j > s shows that w′ agrees with w on K.

A variation of (1.12) is given by the following result of Ordman [Ord85] (see also Henderson and Zalcstein [HZ77]):

Theorem 1.3.2

For a threshold graph with a degree partition D0,…,Dm, the optimal weights and threshold of Theorem 1.3.1 can be computed as follows:

(1.13)

where the wjsatisfy the recurrence

(1.14)

(1.15)

and t and the wj, are then given by

(1.16)

(1.17)

An explicit formula for the solution is given by

(1.18)

(1.19)

(1.20)

Proof

Formula (1.13) follows immediately from (1.12) and the fact that the Dj are the equivalence classes of the vicinal preorder ⪸. The index s , as can be readily verified from (6) of Theorem 1.2.4. Formulas (1.14), (1.15), and (1.17) are then immediate consequences of (1.12) and (1.13). Formula (1.16) follows from (1.12) and from the fact that, for m even, s is the largest index j such that νj ∈ Dm/2, and for m odd, s is the smallest index j such that νj ∈ D[m/2]. Formula (1.18) is proved by induction on j ,

Formula (1.20) follows immediately from (1.17) and (1.18). Formula (1.19) follows from (1.15), (1.16) and (1.18) as follows: for m even,

and for m odd,

1.4 Perfect Graphs and Algorithms

1.4.1 Perfect Graphs

Recall that a stable set is a set of pairwise nonadjacent vertices and a clique is a set of pairwise adjacent vertices. The stability number α(G) of a graph G is the size of a largest stable set in G and the clique number ω(G) is the size of a largest clique in G. A coloring is a partition of the vertex set into stable sets. The chromatic number χ(G) is the minimum size of a coloring and the clique cover number κ(G) is the minimum size of a partition of the vertex set into cliques. Clearly for every graph G. A graph G is called perfect if every induced subgraph G′ of G satisfies

Claude Berge [Ber61] made two conjectures on perfect graphs. The first conjecture, now called the Perfect Graph Theorem, states that a graph is perfect if and only if its complement is perfect. This result was proven by Lovász [Lov72]. The second conjecture, now called the Perfect Graph Conjecture, states that a graph is perfect if and only if it contains neither induced odd cycles of length five or more nor their complements. Several classes of graphs are known to be perfect graphs. For an introduction to perfect graphs one should refer to [Gol80]. A recent survey of various classes of perfect graphs can be found in [Bra91]. Recent results on perfect graphs can be found in [GLS82, BC84].

We define some of the important classes of perfect graphs below.

Definition 1.4.1

1. A graph is called a triangulated graph if it contains no induced cycle of size four or more.

2. A graph G = (V, E) is called an interval graph if each vertex x ∈ V can be assigned an interval i(x) such that xy ∈ E ⟷ i(x) ∩ i(y) ≠ ø.

3. A graph is called a comparability graph if its edges can be transitively oriented (i.e., whenever (x, y), (y, z) are directed arcs, so is (x, z).) The complement of a comparability graph is called a cocomparability graph. Cotriangulated and cointerval graphs are defined similarly.

4. A graph G with vertex set V = {1, 2,…,n} is called a permutation graph if there exists a permutation π of V such that ij is an edge in G if and only if(i, j) is an inversion of π (i.e., (i − j)(πi − πj) < 0).

For a good introduction to various results on triangulated, interval, comparability and permutation graphs one should refer to Golumbic [Gol80]. For instance, one can find there the following results:

• A graph G is an interval graph if and only if G is a comparability graph.

• A graph G is a permutation graph if and only if both G are comparability graphs [PLE71].

From Condition 2 of Theorem 1.2.4 it follows that threshold graphs are triangulated. In addition, threshold graphs are also comparability graphs since by Condition 5 of Theorem 1.2.4 the acyclic orientation in which (x, y) is an arc only if x y is a transitive orientation. As the complement of a threshold graph is also a threshold graph, it follows that threshold graphs are permutation graphs as well as interval graphs. Golumbic [Gol80] characterized the permutations associated with threshold graphs. It is possible to show that the threshold graphs can be represented as interval graphs using intervals of only two lengths (Exercise). If a graph can be represented as an interval graph using intervals of a single length, then it is called a unit interval graph. The complete bipartite graph K1,3(claw) is a threshold graph but not a unit interval graph.

Given a subclass of perfect graphs, one seeks to find polynomial-time algorithms for 1) recognizing the class of graphs, and for any given graph in the class, 2) finding a maximum stable set, 3) finding a maximum clique, 4) finding a minimum coloring and 5) finding a minimum cover by cliques. There are polynomial-time algorithms for problems 2) to 5) for the entire class of perfect graphs using the ellipsoid method [GLS82]. However, one is still interested in finding combinatorial-type algorithms for all the five problems for various subclasses of perfect graphs. For the four classes of perfect graphs mentioned above, all the five problems can be solved in polynomial time [Gol80]. It follows that problems 2) to 5) can be solved in polynomial time for threshold graphs as well. We give below direct algorithms for the first four problems for the class of threshold graphs. It is a simple exercise to modify the algorithm to solve the fifth problem as well.

1.4.2 Algorithms

We use Condition 4 of Theorem 1.2.4 to obtain a linear-time algorithm for recognizing a threshold graph. The algorithm removes recursively any isolated or dominating vertex that exists in the current graph. The resulting graph is the empty graph if and only if the original graph is a threshold graph. By keeping track of the type of each vertex that is removed, one can construct simultaneously a maximum stable set, a maximum clique, a minimum coloring and a minimum cover by cliques. See Figure 1.4 for the algorithm.

Figure 1.4 A linear-time algorithm to recognize and color threshold graphs. {Input: The number n of vertices and the vertex degrees in ascending order as deg(1) ≤ deg(2) ≤ … ≤ deg(n).}

Other algorithmic problems such as Hamiltonicity, total matchings and total coverings are discussed in Sections 1.6 and 1.7. When each vertex is assigned a positive integral weight, the problems of finding a stable set with largest weight and a clique with largest weight can both be solved in polynomial time for threshold graphs. For instance one can adopt the algorithm for finding a maximum weighted clique in comparability graphs (see [Gol80]) for solving these two problems on threshold graphs. A simpler way is to examine the vertices in reverse order to the order in which the algorithm removes them. Each vertex is either isolated or dominating in the graph induced by the vertices examined so far, and so can either be added to the best known stable set or replace it, and a single comparison tells which alternative is better.

1.5 Threshold and Split Completions

Consider the following problem: given a graph G, a spanning subgraph H, and a graph property P, is there a spanning subgraph T satisfying property P and such that

This problem is called the P graph sandwich problem, and T is called a P completion of H in G. Many graph sandwich problems are treated by Golumbic et al. [GKS94]. An O(n³)-time algorithm for the threshold sandwich problem was given by Hammer et al. [HIP81]. Here we give a linear time algorithms for the threshold and split sandwich problems based on [GKS94].

Put H = (V, M) (mandatory (forbidden edges). A closed walk alternating between M and F is called an alternating cycle of H relative to G, abbreviated as ALTCG(H). It may contain repeated vertices and edges of M and F.

Theorem 1.5.1

1. [HIP81] Let H be a spanning subgraph of G = (V, E). Then H has a threshold completion in G if and only if there is no ALTCG(H).

2. [GKS94, RS95] The threshold sandwich problem can be solved in time O(|E| + |V|).

Proof

Let T be any completion of H in G. Assume that C is an ALTCG(H) and consider the subgraph TC of T induced by the vertices of C. Every vertex of C has an M-neighbor in C as well as an F-neighbor in C, so it is not isolated or dominating in TC. Therefore TC violates Condition 4 of Theorem 1.2.4 and cannot be a threshold graph. Therefore T is not a threshold graph, which proves the only if part of 1.

To prove the if part, we notice that if there is no ALTCG(H), then H must have an isolated vertex (for otherwise we could grow a walk alternating between M and F without stopping until an ALTCG(H) is obtained). Let v be such a vertex, and let G′ and H′ be obtained from G and H respectively by deleting v. Since there is no ALTCG′(H′), H′ has a threshold completion T′ in G′ by induction. If v is isolated in H, add it as an isolated vertex to T, add it as a dominating vertex to T′. In both cases the resulting graph T is a completion of H in G, and T is a threshold graph by Condition 4 of Theorem 1.2.4.

The proof above gives an algorithm that either finds a threshold completion of H in G or detects an ALTCG(H). It can be implemented by maintaining the set S of vertices isolated in H , finding and deleting v ∈ Sor H, respectively, while entering them into S if they become eligible. The update takes O(degG(v)), and therefore the total work is O(|E| + |V|).

Theorem 1.5.2 ([GKS94])

The split sandwich problem can be solved in time O(|M| + |F| + |V|).

Proof

A split completion of H in G exists if and only if V can be partitioned into a set K and a set I which is stable in H. We use a Boolean variable xv for each vertex v, where xv = 1 indicates that v ∈ K and xv = 0 indicates that v ∈ I. Each edge uv ∈ M introduces the constraint xu ∨ xv = 1 and each edge uv ∈ F . The conjunction of these constraints is an instance of 2-satisfiability, which can be solved in time O(|M| + |F| + |V|) by the algorithm of Aspvall et al. [APT79].

1.6 Longest Cycles and Hamiltonicity

For a given graph G, we consider the largest length (number of vertices or edges) of a cycle in G. Recall that if the length of a longest cycle equals the number of vertices, then the graph is called Hamiltonian. It is well-known that finding the length of a longest cycle and recognizing a Hamiltonian graph are NP-complete problems [GJ78]. Minty, as reported in Chvátal and Hammer [CH77], Golumbic [Gol80, Ex. 10.6], and Harary and Peled [HP87] have characterized Hamiltonian threshold graphs.

In this section, based on [MP94], we show that the length of a longest cycle of a threshold graph G is equal to the size of a largest matching in a specially structured bipartite graph obtained from G. Moreover, because of the special structure, namely nested neighborhoods, this matching can be obtained in linear time. A longest cycle of G can also be constructed from the matching in linear time. The characterization also leads to a characterization of Hamiltonian threshold graphs. We use this characterization to prove Golumbic’s characterization and sharpen Minty’s.

Definition 1.6.1

The LCL (Largest Cycle Length) of a graph G is the largest length of a cycle of G. We denote the LCL by