On the problem of how to represent a graph taking into account an additional structure (Q1101469): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q5570136 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5615282 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Transitiv orientierbare Graphen / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Representation of a finite graph by a set of intervals on the real line / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4138414 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Characterization problems for graphs, partially ordered sets, lattices, and families of sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Structure theorems for some circular-arc graphs / rank | |||
Normal rank |
Latest revision as of 16:58, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the problem of how to represent a graph taking into account an additional structure |
scientific article |
Statements
On the problem of how to represent a graph taking into account an additional structure (English)
0 references
1988
0 references
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.
0 references
hypergraph
0 references
representation
0 references
0 references