Bound Graph Polysemy

Paul J. Tanenbaum

U.S. Army Research Laboratory Aberdeen Proving Ground, Maryland 21005-5068 U.S.A.

                           pjt@arl.army.mil

Submitted: January 26, 2000; Accepted: August 15, 2000

Abstract

Bound polysemy is the property of any pair (G_{1}, G_{2}) of graphs on a shared vertex set V for which there exists a partial order on V such that any pair of vertices has an upper bound precisely when the pair is an edge in G_{1} and a lower bound precisely when it is an edge in G_{2}. We examine several special cases and prove a characterization of the bound polysemic pairs that illuminates a connection with the squared graphs.

2000 Mathematics Subject Classification. Primary 05C62, 06A07.

1 Introduction

McMorris and Zaslavsky [9] define an upper bound graph as any graph whose vertices may be partially ordered in such a way that distinct vertices have an upper bound if and only if they are adjacent. This class of graphs has been studied widely [1, 2, 3, 4, 8] since its introduction. An excellent current survey of the field may be found in [7].

It is straightforward to see that the lower bound graphs, defined analogously, constitute precisely the same class. In general, a poset realizes two graphs simultaneously: one is its upper bound graph and another, its lower bound graph. These graphs may be thought of as two meanings of the poset, two answers to the question, “What is this poset trying to tell me?”

We call a pair of graphs G_{1} = (V, E_{1}) and G_{2} = (V, E_{2}) on a common vertex set bound polysemic provided there exists a partial order ≤ on V such that distinct u, v ∈ V have an upper bound in (V, ≤) if and only if uv ∈ E_{1} and a lower bound if and only if uv ∈ E_{2}. If such a partial order exists, the poset (V, ≤) is called a bound polysemic realization of (G_{1}, G_{2}).

Polysemic pairs of graphs are introduced in [12], which addresses intersection polysemy: the pairs of intersection graphs that arise from families of sets and of those sets’ complements. Notions of polysemy for posets are explored in [11] and [13].

Although they do not highlight the polysemy phenomenon, Lundgren, Maybee, and McMorris [6] and Bergstrand and Jones [2] investigate a closely related problem. Call a pair of graphs G_{1} and G_{2} for which |V (G_{1})| = |V (G_{2})| unlabeled bound polysemic provided that they are isomorphic, respectively, to graphs H_{1} and H_{2} that are themselves bound polysemic. A result in [6] amounts to a characterization of the unlabeled bound polysemic pairs. In some contexts where it is important to contrast it with unlabeled bound polysemy, we refer to bound polysemy as labeled.

Consider the morphisms that carry adjacency in the graphs to boundedness (above and below, respectively) in the poset, and assume without loss of generality that the graphs have the same vertex set. In the case of unlabeled polysemy, the two morphisms are independent of one another, whereas in the labeled case a single morphism does double duty. We think of the two cases in terms of labeling because if one tagged the vertices with their images under these morphisms, precisely the labeled case would result in a consistent assignment of tags.

We present here a characterization of the labeled bound polysemic pairs, which hints at a connection to the squared graphs. The remainder of this section gives some basic definitions. Section 2 surveys several results by way of background. Section 3 discusses known results for unlabeled bound polysemy. Section 4 addresses several special cases of bound polysemy. Section 5 proves more general results, including our characterization of the bound polysemic pairs. And Section 6 concludes with some open problems.

All graphs considered here are finite and simple. The open neighborhood of a vertex v in a graph (V, E) is the set N(v) = {u ∈ V | uv ∈ E}, and the closed neighborhood is the set N[v] = N(v) ∪ {v}. A clique in a graph is any complete induced subgraph and need not be maximal with that property. Cliques are often identified with their vertex sets. A vertex v is simplicial in some graph provided that N(v) is a clique. An edge clique cover of a graph G is a set E of cliques of G such that every edge uv of G, seen as a 2-set, is contained in some member of E.

All posets P = (X, ≤) considered here are finite and reflexive. Where several partial orders are being discussed, we sometimes append subscripts to their symbols, as ≤_{P}, to avoid ambiguity. The height of a poset is the maximum cardinality h of any chain x_{1} < x_{2} < ⋯ < x_{h} in the poset. A poset is bipartite provided that its height is at most 2. The upset of an element x in a poset P = (X, ≤) is the set X_{≥}(x) = {y ∈ X | y ≥ x}. The set max(P) of maximals of P contains precisely those elements x ∈ X for which X_{≥}(x) = {x}. The downset X_{≤}(x) of x and the minimals min(P) of P are defined analogously. An element y of P covers another element x provided that x < y and there exists no z ∈ X with x < z < y.

The dual of a poset P = (X, ≤) is the poset P^{d} = (X, ≥) obtained by reversing the sense of every comparability of P. Poset duality runs throughout this topic: pairs of dual concepts include upsets and downsets, minimality and maximality, and boundedness above and below. And by dualizing posets we obtain an immediate proof that bound polysemy is a symmetric relation on the graphs with a given vertex set.

The comparability graph of a poset (X, ≤) has vertex set X and an edge xy for each comparability x < y. A poset is connected precisely when its comparability graph is connected. A fence is a poset whose comparability graph is a path.

For further definitions, notation, and background information, see for instance [14] and [15].

2 Background

Among the previous results that we use are four characterizations of the upper bound graphs. The first one is an easy observation. The other, more interesting, characterizations are taken from the literature.

Observation 1 The upper (resp. lower) bound graph of a poset is exactly the intersection graph of the upsets (resp. downsets) of the poset.

Theorem 2 (McMorris and Zaslavsky) A graph is an upper bound graph if and only if it has an edge clique cover E = {Q_{1}, …, Q_{r}} for which there exists a system {v_{1}, …, v_{r}} of distinct representatives such that v_{i} ∈ Q_{j} precisely when i = j.

The next characterization makes use of the notion of an ordered edge cover of a graph G—an edge clique cover {Q_{1}, …, Q_{n}} of G together with a labeling {v_{1}, …, v_{n}} of V (G) such that each v_{i} is in Q_{i} and if v_{i} ∈ Q_{j}, then i ≤ j and Q_{i} ⊆ Q_{j}.

Theorem 3 (Lundgren and Maybee [5]) A graph G is an upper bound graph if and only if it has an ordered edge cover.

The proof of Theorem 2 proceeds by establishing a straightforward identity between the graph’s distinct representatives and their corresponding cliques on the one hand, and the poset’s maximals and their respective downsets on the other. In much the same way, Theorem 3 may be proven [6] by identifying the vertex labeling and cliques of the graph with a linear extension and all the downsets of the poset.

The third characterization was published independently in [1] and [3].

Theorem 4 (Bergstrand and Jones, Cheston et al.) A graph is an upper bound graph if and only if each of its edges is in the closed neighborhood of some simplicial vertex.

Another class of graphs that has been characterized in terms of edge clique covers is the squared graphs. A graph G = (V, E) is squared provided that there exists a graph S on V such that u, v ∈ V are adjacent in G if and only if d_{S}(u, v) ≤ 2. Such a graph S is called a square root of G. This notion of multiplication is motivated by the identification of a graph with its adjacency matrix. Mukhopadhyay [10] characterized the squared graphs as follows.

Theorem 5 (Mukhopadhyay) A graph on V = {v_{1}, …, v_{n}} has a square root if and only if it has an edge clique cover E = {Q_{1}, …, Q_{n}} with the properties that

1. for 1 ≤ i ≤ n, v_{i} ∈ Q_{i} and

2. for 1 ≤ i < j ≤ n, v_{i} ∈ Q_{j} if and only if v_{j} ∈ Q_{i}.

3 The Unlabeled Case

Recall that unlabeled bound polysemy consists in a pair of graphs that are isomorphic, respectively, to the upper and lower bound graphs of a single poset. Lundgren, Maybee, and McMorris [6] give a characterization of these pairs.

Theorem 6 (Lundgren, Maybee, and McMorris) Given graphs G_{1} and G_{2} with the same number of vertices, the following are equivalent:

1. G_{1} and G_{2} are unlabeled bound polysemic.

2. G_{1} is (isomorphic to) the intersection graph of some ordered edge cover of G_{2}.

3. G_{2} is (isomorphic to) the intersection graph of some ordered edge cover of G_{1}.

This result follows from Observation 1 and Theorem 3. Its third condition, for instance, translates to the assertion that G_{1} has an upper bound realization whose downsets, under intersection, yield G_{2}.

Bergstrand and Jones [2] provide the first examples of graphs that we would describe as unlabeled bound polysemic with themselves. A representative member G of one family of such graphs is shown in Figure 1. Any graph in this family consists

[figure: u; v; u′; p′_{1}; p_{1}; q_{1}; q_{2}; v′; q′_{1}; q′_{2}; (a) G; p_{1}; u′; v′; q_{1}; q_{2}; p′_{1}; u; v; q′_{1}; q′_{2}; (b) A realization P of (G, G)]

Figure 1: A graph that is unlabeled bound polysemic with itself

of cliques K_{u} and K_{v} that intersect in an edge uv and that each have at least one other vertex, together with |K_{u}|−3 pendant vertices p_{1}, …, p_{|K_{u}|−3} adjacent to u and |K_{v}| − 3 pendant vertices q_{1}, …, q_{|K_{v}|−3} adjacent to v. It is clear that G is the upper bound graph of the poset P in Figure 1b: the annotation in the figure encodes the morphism carrying adjacency to boundedness above. And since P is isomorphic to its own dual, we have also that G is isomorphic to the lower bound graph of P. So P is an unlabeled bound polysemic realization of G.

Although G is unlabeled bound polysemic (with itself), it is not bound polysemic. To see this, consider any upper bound realization P′ of G. Each of q_{1} and q_{2} must have an upper bound in P′ with v and with no other vertex, so each is comparable to v and to no other. Thus v <_{P′} q_{1}, q_{2}. But then v is a lower bound for q_{1} and q_{2}. So every lower bound graph of P′ must include edge q_{1}q_{2}, which G lacks. It follows that no upper bound realization of G is also a lower bound realization.

4 Special Cases of Labeled Bound Polysemy

We begin our investigation of (labeled) bound polysemy with results for several special cases. In contrast to the examples described in Section 3—graphs that are unlabeled bound polysemic with themselves—our first theorem characterizes the analogous class in the labeled case. In order to establish that characterization, we use the following lemma.

Lemma 7 If a connected poset P has the property that any pair of elements has an upper bound if and only if it has a lower bound, then P has a maximum and a minimum.

Proof. Note that the connectedness of P implies that for any elements a and b of P = (X, ≤) there is a fence F = (Y, ≤_{F}) induced in P with a and b as its endpoints. We show by induction on the cardinality of F that there exist α_{F} , ω_{F} ∈ X such that α_{F} ≤ f ≤ ω_{F} for all f ∈ F. In particular, then, a and b have both an upper and a lower bound.

The base cases |F | = 0, 1, 2 are trivial. For the inductive step, let |F | > 2 and assume that b is minimal in F (the dual case may be argued analogously). Let F′ = F − b and consider α_{F′}, ω_{F′} ∈ X as are guaranteed to exist by the inductive hypothesis. Since b <_{F} f_{i} for some f_{i} ∈ Y, we also have b < f_{i} ≤ ω_{F′}, so b and α_{F′} have an upper bound. This means that they also have a lower bound α. So we choose ω_{F} = ω_{F′} and α_{F} = α, and they have the required property.

Thus, every pair of elements of P has both an upper bound and a lower bound, so P must have a maximum and a minimum.

Theorem 8 A graph is bound polysemic with itself if and only if it is a disjoint union of cliques.

Proof. It is straightforward to see that any disjoint union G of cliques is bound polysemic with itself. For each clique, construct a linear order on its vertices. Then the sum of these chains realizes (G, G).

Conversely, let G = (V, E) be any graph and P be a bound polysemic realization of (G, G). It is clear that any pair of elements of P has an upper bound if and only if it has a lower bound, so by Lemma 7 distinct maximals (resp. minimals) must be in separate components of P. So G must be a disjoint union of cliques.

Corollary 9 Every edgeless graph is bound polysemic with itself but with no other graph.

Proof. That G = (V, ∅) is bound polysemic with itself follows immediately from Theorem 8. In particular, the only upper bound realization of G is the antichain on V, so it is clear that no graph on V with at least one edge is bound polysemic with G.

Theorem 10 No graph with more than one vertex is bound polysemic with its complement.

Proof. Let P = (V, ≤) be an upper bound realization of a graph G = (V, E) with n > 1 vertices. If P is an antichain, then E is empty and the conclusion follows from Corollary 9. On the other hand, if there exist u ≤ v in P, then they have an upper bound, so uv ∈ E. But they have a lower bound, too, even though uv ∉ \overline{E}. So no upper bound realization of G is also a lower bound realization of \overline{G}.

Theorem 11 An n-vertex graph G is bound polysemic with K_{n} if and only if G is an upper bound graph with a vertex of degree n − 1.

Proof. Suppose G and K_{n} to be bound polysemic. We show that Δ(G) = n − 1. Any lower bound realization of K_{n} has a minimum, since distinct minimals of a poset cannot have a lower bound and thus cannot be adjacent in a lower bound graph. But a minimum of a poset has an upper bound with every element, so the minimum of any realization of (G, K_{n}) has degree n − 1 in G.

Conversely, let G be an upper bound graph and suppose there exists a vertex v of degree n − 1 in G. If G ≅ K_{n}, then the result follows from Theorem 8. Otherwise, v is not simplicial, so by Theorem 4 there exists an upper bound realization P′ of G − v. Then the poset P obtained from P′ by adding v as a minimum is an upper bound realization of G. And since v is a lower bound for every pair of elements, P is also a lower bound realization of K_{n}.

Theorem 12 A graph G = (V, E_{G}) is bound polysemic with a tree T = (V, E_{T}) if and only if G is complete and T is a star.

Proof. Let T be a star and select v ∈ V with degree Δ(T). Then the poset P for which min(P) = {v} and max(P) = V \ {v} is an upper bound realization of T. In the trivial case of |V | = 2, P and P^{d} are the only upper bound realizations of T. For |V | ≠ 2, P itself is the only upper bound realization of T. This follows from the facts that no distinct x, y ∈ V \{v} can even have an upper bound—so they certainly cannot be comparable—and that if any x were incomparable to v, then x and v would have some upper bound y ≠ v, which would imply xy ∈ E(G). Note too that the lower bound graph of P, and of P^{d} in the case |V | = 2, is the complete graph on V.

Conversely, suppose T is not a star. Then |V | = n ≥ 4, so T has a leaf u, and the neighbor v of u has degree strictly less than n − 1. Thus there exists w ∈ V not adjacent to v and the u-w path has length at least 4, so T contains an induced P_{4}. But neither vertex of the internal edge e of an induced P_{4} can be simplicial, and T is K_{3}-free. So e is not in the closed neighborhood of any simplicial vertex, and it follows from Theorem 4 that T is not an upper bound graph.

5 General Results

In their proof of Theorem 2, McMorris and Zaslavsky use a construction that demonstrates that any upper bound realization may be assumed without loss of generality to be bipartite. When we consider bound polysemy, the situation becomes only slightly more complicated. To begin with, take the example illustrated in Figure 2. It may

[figure: a; b; c; d; e; (a) G_{1}; a; b; c; d; e; (b) G_{2}; a; b; c; d; e; (c) A realization P]

Figure 2: A bound polysemic pair with no bipartite realization

easily be verified that the poset P in Figure 2c is a bound polysemic realization of (G_{1}, G_{2}), the pair in Figure 2a and b. How much flexibility does one have in constructing a realization of G_{1} and G_{2}? Since neither c nor e is adjacent to a in G_{1} and c is not adjacent to e in G_{2}, {a, c, e} must be an antichain. Furthermore, b must have lower bounds with each of a, c, and d, and it is the only element that can possibly be comparable to a. So b must be below the other three. Dually, d is the only element that can be comparable to e, and must be above b, c, and e. Thus, P is the unique bound polysemic realization of (G_{1}, G_{2}), and, in particular, G_{1} and G_{2} have no bipartite realization.

Our next two results show that, while bound polysemic realizations of height less than 3 are something of a special case, height at most 3 may always be assumed.

Theorem 13 A bound polysemic pair has a bipartite realization if and only if no triple of vertices induces a triangle in both graphs. Furthermore, if no such triple exists, then every realization is bipartite.

Proof. Let G_{1} = (V, E_{1}) and G_{2} = (V, E_{2}) be bound polysemic. It is a simple matter to verify that if some distinct u, v, w ∈ V induce a triangle in both graphs, then no realization of (G_{1}, G_{2}) is bipartite. Contrapositively, if they have a bipartite realization, then no such triple exists.

On the other hand, if any realization P = (V, ≤) has height at least 3, then there exist u < v < w in V, so {u, v, w} induces a triangle in each graph and every realization has height at least 3.

Theorem 14 For any poset P = (X, ≤), let P′ = (X, ≤′) be the height-3 poset for which

≤′ = ⋃_{y∈max(P)}{(x, y) | x ≤ y} ∪ ⋃_{y∈min(P)}{(y, x) | x ≥ y}.

Then P and P′ have the same upper bound graph and the same lower bound graph.

Proof. It is clear that if a, b ∈ X have an upper bound in P, then they have one that is maximal, so they also have an upper bound in P′. Conversely, any upper bound for elements a and b of P′ is also an upper bound of a and b in P. So the two posets have the same upper bound graph and, dually, the same lower bound graph.

We now present our main result—a characterization of the bound polysemic pairs that blends the flavors of Theorems 2 and 5.

Theorem 15 Graphs G_{1} = (V, E_{1}) and G_{2} = (V, E_{2}) are bound polysemic if and only if there exist edge clique covers E_{1} = {Q_{1,1}, …, Q_{1,r}} of G_{1} and E_{2} = {Q_{2,1}, …, Q_{2,s}} of G_{2} and disjoint systems R_{1} = {v_{1,1}, …, v_{1,r}} and R_{2} = {v_{2,1}, …, v_{2,s}} of distinct representatives of E_{1} and E_{2}, respectively, with the properties that

1. v_{k,i} ∈ Q_{k,j} precisely when i = j,

2. ⋃_{i=1}^{r} Q_{1,i} = ⋃_{i=1}^{s} Q_{2,i}, and

3. Q_{1,i} ∩ Q_{2,j} is nonempty only if v_{1,i} ∈ Q_{2,j} and v_{2,j} ∈ Q_{1,i}.

Proof. Property 1 is simply the necessary and sufficient condition in Theorem 2 for G_{1} and G_{2} to be (upper or lower) bound graphs, independent of one another. Properties 2 and 3 together with the requirement that the two systems R_{1} and R_{2} be disjoint give us the polysemy, as we now prove. Our approach is similar to the one used for Theorems 2 and 3—we establish for some poset P = (V, ≤) the following identity:

R_{1} ↔ max(P) \ min(P) Q_{1,i} ↔ V_{≤}(v_{1,i}) R_{2} ↔ min(P) \ max(P) Q_{2,i} ↔ V_{≥}(v_{2,i}) .  (1)

We begin by showing that the conditions are necessary for any realization P. Define E_{1}, E_{2}, R_{1}, and R_{2} as in (1). It is clear that R_{1} and R_{2} are disjoint. It also follows immediately, since ≤ is reflexive and no maximal (resp. minimal) can be in the downset (resp. upset) of any other, that property 1 holds. Furthermore, v ∈ V is in some downset in E_{1} (resp. upset in E_{2}) only if v is not isolated in P, which, in turn, is the case only if v is in one of the upsets in E_{2} (resp. downsets in E_{1}). So property 2 holds. And finally, if there exists any v ∈ Q_{1,i} ∩ Q_{2,j}, then v_{2,j} ≤ v ≤ v_{1,i}; so property 3 holds by transitivity.

Conversely, suppose the edge clique covers E_{1} and E_{2} and their respective systems R_{1} and R_{2} of distinct representatives exist. We construct a bound polysemic realization P = (V, ≤) of (G_{1}, G_{2}) by defining

\begin{aligned}≤ & = & ⋃_{i=1}^{r}\{(v, v_{1,i}) | v ∈ Q_{1,i}\} ∪ ⋃_{i=1}^{s}\{(v_{2,i}, v) | v ∈ Q_{2,i}\} \\ & & ∪ \{(v, v) | v ∈ V \ (R_{1} ∪ R_{2})\}. \end{aligned}  (2)

It is clear from its definition and property 1 that ≤ is reflexive. Property 1 also ensures that if u ≤ v and either u ∈ R_{1} or v ∈ R_{2}, then u = v. So if both u ≤ v and v ≤ u, then u = v. In other words, ≤ is antisymmetric. Is it transitive? If there exist distinct u, v, w ∈ V with u ≤ v and v ≤ w, then w ∈ R_{1} and u ∈ R_{2}. So v ∈ Q_{1,i} ∩ Q_{2,j}, where w = v_{1,i} and u = v_{2,j}. But then it follows from property 3 that w ∈ Q_{2,j} and u ∈ Q_{1,i}, and either one of these memberships ensures that u ≤ w. So ≤ is a partial order.

It remains to demonstrate that G_{1} and G_{2} are the upper and lower bound graphs of P, respectively. We prove the case for G_{1}—the other may be obtained from a dual argument. As a preliminary step, we prove that max(P) \ min(P) ⊆ R_{1}. The opposite containment is immediate, so the two sets are in fact equal. To see this, consider any nonminimal maximal v. There must exist u ≠ v for which (u, v) is a member of the first or second term of (2). If the comparability is in the first term, then v ∈ R_{1} trivially. If the comparability appears in the second term only, then v is in some Q_{2,i}, so it follows from property 2 that v is also in some Q_{1,j}, and thus, from property 1 that v = v_{i,j} ∈ R_{1}.

Finally, is G_{1} indeed the upper bound graph of P? Any edge uv of G_{1} is in at least one clique Q_{1,i} ∈ E_{1}. As a result, u and v have v_{1,i} as an upper bound in P. Conversely, if distinct u, v ∈ V have an upper bound, then there exists w ∈ max(P)\min(P) = R_{1}, say w = v_{1,i}, such that u ≤ w and v ≤ w. If the comparability (u, w) is a member of the first term of (2), then u ∈ Q_{1,i}. Otherwise, the comparability is in the second term, so u = v_{2,j} for some j and w ∈ Q_{1,i} ∩ Q_{2,j}. Thus, by property 3, u is again in Q_{1,i}. By a parallel argument, v, too, is in Q_{1,i}, so u and v are adjacent in G_{1}.

The similarity of the statements of Theorems 15 and 5 suggests that bound polysemy and squared graphs are related concepts. The connection between these concepts is captured in the following theorem.

Theorem 16 If graphs G_{1} = (V, E_{1}) and G_{2} = (V, E_{2}) have a bound polysemic realization P that is bipartite, then G_{3} = (V, E_{1} ∪E_{2}) is a squared graph with a square root equal to the underlying graph of the Hasse diagram of P.

Proof. We may call G_{3} the either bound graph of P, since any distinct elements of V are adjacent in G_{3} if and only if they have either an upper or a lower bound in P. It is immediate for any poset, regardless of height, that its comparability graph is a square root of its either bound graph. It only remains to demonstrate that the extra condition that P be bipartite is sufficient to ensure that the underlying graph H of the Hasse diagram of P is also a square root of G_{3}.

Note that the closed neighborhood in H of any w ∈ V is

N_{H}[w] = \{ \begin{matrix}V_{≤}(w), & w ∈ max(P) \\ V_{≥}(w), & w ∈ min(P) \end{matrix} .

Note too that d_{H}(u, v) ≤ 2 if and only if either (1) u and v are comparable, (2) they are minimals below some common maximal, or (3) they are maximals above some common minimal. But these three cases are equivalent, respectively, to (1′) u and v have both an upper and a lower bound, (2′) they have an upper bound, and (3′) they have a lower bound.

The following theorem is a further parallel to a result from [9]. It shows that the bound polysemic pairs—like the upper bound graphs—cannot be characterized in terms of forbidden subgraphs.

Theorem 17 For any graphs G_{1} = (V, E_{1}) and G_{2} = (V, E_{2}) on a common vertex set, there exists a bound polysemic pair {G′_{1}, G′_{2}} such that G_{1} is an induced subgraph of G′_{1} and G_{2} is an induced subgraph of G′_{2}.

Proof. For any edge clique covers E_{1} = {Q_{1,1}, …, Q_{1,r}} of G_{1} and E_{2} = {Q_{2,1}, …, Q_{2,s}} of G_{2}, we enlarge our set of vertices to

V′ = V ∪ {q_{1,1}, …, q_{1,r}} ∪ {q_{2,1}, …, q_{2,s}},

where none of the q_{k,i} is in V. Next we define a partial order P = (V′, ≤), in which {q_{1,1}, …, q_{1,r}}, V, and {q_{2,1}, …, q_{2,s}} are antichains and every v ∈ V is covered by exactly those q_{1,i} for which v ∈ Q_{1,i} and covers exactly those q_{2,i} for which v ∈ Q_{2,i}. Finally, let G′_{1} and G′_{2} be the upper and lower bound graphs, respectively, of P. Then G′_{1} and G′_{2} are bound polysemic by construction and each G_{k} is the subgraph of G′_{k} induced by V.

6 Open Problems

We have seen that ((V, ∅), (V, ∅)), (K_{1,n−1}, K_{n}), and the pair in Figure 2 each have a unique bound polysemic realization. Other such pairs may be obtained from the graphs with unique upper bound realizations, which are characterized by McMorris and Myers [8]. It remains an open problem to completely characterize all the bound polysemic pairs that have unique representations.

An interesting algorithmic problem is the recognition of bound polysemy. Although Theorem 17 precludes one line of attack, Bergstrand and Jones [1] overcame an analogous situation, using Theorem 4 to obtain an O(n^{3}) algorithm to recognize upper bound graphs.

Another open problem is the extension of our results by generalizing the posets to directed graphs. The analog of a poset’s upper (resp. lower) bound graph is a digraph’s competition (resp. common enemy) graph. It would be interesting to investigate what one might call competition polysemy.

References

[1] D. J. Bergstrand and K. F. Jones, On upper bound graphs of partially ordered sets, Congr. Numer. 66 (1988), 185–193.

[2] , Graphs that are both the upper and lower bound graphs of a poset, Ars Combin. 28 (1989), 109–121.

[3] G. A. Cheston, E. O. Hare, S. T. Hedetniemi, and R. C. Laskar, Simplicial graphs, Congr. Numer. 67 (1988), 105–113.

[4] H. Era and M. Tsuchiya, On upper bound graphs whose complements are also upper bound graphs, Discrete Math. 179 (1998), 103–109.

[5] J. R. Lundgren and J. S. Maybee, A characterization of upper bound graphs, Congr. Numer. 40 (1983), 189–193.

[6] J. R. Lundgren, J. S. Maybee, and F. R. McMorris, Two-graph inversion of competition graphs and upper bound graphs, Congr. Numer. 67 (1988), 136–144.

[7] T. A. McKee and F. R. McMorris, Topics in intersection graph theory, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, Philadelphia, 1999.

[8] F. R. McMorris and G. T. Myers, Some uniqueness results for upper bound graphs, Discrete Math. 44 (1983), 321–323.

[9] F. R. McMorris and T. Zaslavsky, Bound graphs of a partially ordered set, J. Combin. Inform. System Sci. 7 (1982), 134–138.

[10] A. Mukhopadhyay, The square root of a graph, J. Combin. Theory 2 (1967), 290–295.

[11] P. J. Tanenbaum, Simultaneous representation of interval and intervalcontainment orders, Order 13 (1996), 339–350.

[12] , Simultaneous intersection representation of pairs of graphs, J. Graph Theory 32 (1999), 171–190.

[13] P. J. Tanenbaum and S. Whitesides, Simultaneous dominance representation of multiple posets, Order 13 (1996), 351–364.

[14] W. T. Trotter, Combinatorics and partially ordered sets: Dimension theory, Johns Hopkins Series in Mathematical Sciences, Johns Hopkins Univ. Press, Baltimore, 1992.

[15] D. B. West, Introduction to graph theory, Prentice Hall, Upper Saddle River, NJ,