Representation theorems for graphs whose vertex set is partially ordered

In the paper graphs with partially ordered vertex sets are studied. Three main problems are considered. The first problem concerns the \(<\)- representability. A graph \(G=(X,E)\) with the order relation \(<\) on X is \(<\)-representable, if there exists a hypergraph \(H=(Y,F)\) and a surjection \(p:X\to F\) such that two vertices x, y are adjacent in G if and only if \(p(x)\cap p(y)\neq \emptyset\) and \(x\leq y\) if and only if \(p(x)\subset p(y).\) The second problem concerns the strong \(<\)- representability which is a strengthening of the \(<\)-representability (p is defined on the set of all subsets of X). The third problem concerns the U-covering. Here \(G=(X,E)\) is a graph and U is a non-empty family of subsets of X with the property that \(A\in U\), \(A\subset B\subset X\) implies \(B\in U\). The graph G is U-covered, if there exists a hypergraph \(H=(Y,F)\) and a surjection \(p:X\to F\) such that x, y are adjacent in G if and only if \(p(x)\cap p(y)\neq \emptyset\) and \(A\in U\) if and only if \(\cup_{x\in A}p(x)=Y.\) The characterization theorems for the described properties are proved. At the end the applications to interval graphs and circular graphs are shown.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Representation theorems for graphs whose vertex set is partially ordered

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