Containment Graphs, Posets, and Related Classes of Graphs

Abstract: In this paper, we introduce the notion of the containment graph of a family of sets and containment classes of graphs and posets. Let

Z

be a family of nonempty sets. We call a (simple, finite) graph G = (V, E) a

Z

-containment graph provided one can assign to each vertex

v_{i} i n V

a set

S_{i} i n Z

such that

v_{i} v_{j} i n E

if and only if

S_{i} s u b s e t S_{j}

or

S_{j} s u b s e t S_{i}

. Similarly, we call a (strict) partially ordered set

P = (V, <)

a

Z

-containment poset if to each

v_{i} i n V

we can assign a set

S_{i} i n Z

such that

v_{i} < v_{j}

if and only if

S_{i} s u b s e t S_{j}

. Obviously,

G

is the comparability graph of

P

. We give some basic results on containment graphs and investigate the containment graphs of iso-oriented boxes in

d

-space. We present a characterization of those classes of posets and graphs that have containment representations by sets of a specific type, and we extend our results to ``injective containment classes. After that we discuss similar characterizations for intersection, overlap, and disjointedness classes of graphs. Finally, in the last section we discuss the nonexistence of a characterization theorem for ``strong containment classes of graphs.

Review text

[For the entire collection see Zbl 0699.00014.] We introduce the notion of the containment graph of a family of sets and containment classes of graphs and posets. Let \(\Sigma\) be a family of nonempty sets. We call a (simple, finite) graph \(G=(V,E)\) a \(\Sigma\)- containment graph provided one can assign to each vertex \(v_ i\in V\) a set \(S_ i\in\Sigma\) such that \(v_ i v_ j\in E\) if and only if \(S_ i\subset S_ j\) or \(S_ i\supset S_ j\). Similarly, we call a (strict) partially ordered set \(P=(V,<)\) a \(\Sigma\)-containment poset if to each \(v_ i\in V\) we can assign a set \(S_ i\in\Sigma\) such that \(v_ i<v_ j\) if and only if \(S_ i\subset S_ j\). Obviously, \(G\) is the comparability graph of \(P\). The function \(f: V\to\Sigma\), which assigns sets of \(\Sigma\) to elements of \(V\) by \(f(v_ i)=S_ i\), is called a \(\Sigma\)-containment representation for \(G\) and \(P\), or simply a \(\Sigma\)-representation. There are two approaches that one might take in investigating containment graphs. In the first, one restricts the family of sets \(\Sigma\) to a certain type (such as intervals on a line, circles in the plane, paths in a tree) and then asks what class of graphs is obtained. In the second approach, one begins with a class \(\mathbb{C}\) of comparability graphs and asks whether \(\mathbb{C}\) can be characterized as the family of containment graphs of some family of sets. In the next section we give some basic results on containment graphs and investigate the containment graphs of iso-oriented boxes in \(d\)-space. In the section following we present a characterization of those classes of posets and graphs that have containment representations by sets of a specific type. In the next section we present an alternative characterization, and then in the following section we extend our results to ``injective containment classes. After that we discuss similar characterizations for intersection, overlap, and disjointedness classes of graphs. Finally, in the last section we discuss the nonexistence of a characterization theorem for ``strong containment classes of graphs. Unless specifically stated otherwise, all graphs and posets are assumed to be finite.

Recommendations

Cited in

(26)

This page was built for publication: Containment Graphs, Posets, and Related Classes of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972134)