کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649407 | 1342453 | 2009 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On 3-Steiner simplicial orderings On 3-Steiner simplicial orderings](/preview/png/4649407.png)
Let GG be a connected graph and SS a nonempty set of vertices of GG. A Steiner tree for SS is a connected subgraph of GG containing SS that has a minimum number of edges. The Steiner interval for SS is the collection of all vertices in GG that belong to some Steiner tree for SS. Let k≥2k≥2 be an integer. A set XX of vertices of GG is kk-Steiner convex if it contains the Steiner interval of every set of kk vertices in XX. A vertex x∈Xx∈X is an extreme vertex of XX if X∖{x}X∖{x} is also kk-Steiner convex. We call such vertices kk-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering.
Journal: Discrete Mathematics - Volume 309, Issue 19, 6 October 2009, Pages 5828–5833