Representing triangulated graphs in stars (Q1261172): Difference between revisions

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.