On 3-Steiner simplicial orderings

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.