Representing triangulated graphs in stars (Q1261172)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Representing triangulated graphs in stars |
scientific article |
Statements
Representing triangulated graphs in stars (English)
0 references
31 August 1993
0 references
A graph \(G\) is called representable in a tree \(T\), if \(G\) is isomorphic to the intersection graph of a family of subtrees of \(T\). Stars are generalizations of trees with at most one vertex of degree greater than 2. By generalizing the methods and the notions in investigating interval graphs so-called star graphs are characterized which are representable in some subdivision of the \(K_{1,n}\). Especially for the finite case an algorithm is given to recognize such a star graph in time \(O(mn^ 2)\), where \(n\) and \(m\) are the number of vertices and edges of the graph. Further this concept can be generalized to essentially infinite graphs by using ``tree-like'' partially ordered sets (``posets'') \((P,\leq)\). A graph is called representable in some poset \((P,\leq)\) if it is the intersection graph of some family \((P_ v\mid v\in V(G))\) of subsets of \(P\) such that two vertices \(v\) and \(u\) of \(G\) are adjacent exactly if \(P_ v\cap P_ u\neq\varnothing\), and the family of these connected sets is called a representation of \(G\) in \(P\). In the present paper a \(\sigma\)-star \((\sigma\) a cardinal number) is treated as poset \((S,\leq)\) with a smallest element 0, where \(P\backslash\{0\}\) is the disjoint union of totally ordered sets \(L_ i\), \(i\in I\) and \(\#(I)=\sigma\). By a \(\sigma\)-star graph is ment a graph which is representable in some \(\sigma\)-star. These graphs are summarized under the name star graphs. Star graphs are triangulated.
0 references
triangulated graphs
0 references
representable
0 references
tree
0 references
intersection graph
0 references
interval graphs
0 references
star graph
0 references
partially ordered sets
0 references
representation
0 references
star graphs
0 references
0 references