On the problem of how to represent a graph taking into account an additional structure (Q1101469): Difference between revisions

A finite undirected graph \(G=(X,E)\) is given such that every non isolated vertex is provided with a loop. In this note is tried to express such a graph as the intersection graph of a finite hypergraph H(Y,F) by using a suitable inclusion relation between every edge and every union of edges in H. In a first problem given G and an order \(\leq\) on X and it is wanted to find an hypergraph H and a surjective function from X to F satisfying given conditions. If it is possible to find such an H, then G is called \(\leq\)-representable. In Theorem 1 is proved the equivalence between \(\leq\)-representation of G and satisfying two conditions. In a second problem is given a relation R between the elements of X and the subsets of X and it is wanted to find an hypergraph H and a surjective function from X to F satisfying two given conditions. If we can find such an H, then G is called R-representable. In Theorem 2 is proved the equivalence between R-representation of G and satisfying four conditions. This proof is a very extensive one, many lemmata and numerous distinctions of cases are necessary. Then two consequences of Theorem 2 follow: first in the case that R is a relation used in the first problem and by considering strong \(<\)-representation. In Theorem 3 a further problem with respect to a so-called U-covered graph is researched. Finally in this note are given some examples: - In Theorem 4 is proved that G is an interval graph if and only if three certain conditions are satisfied. - A necessary condition for a graph to be a circular arcgraph is deduced.