×

On 3-Steiner simplicial orderings. (English) Zbl 1221.05042

Summary: Let \(G\) be a connected graph and \(S\) a nonempty set of vertices of \(G\). A Steiner tree for \(S\) is a connected subgraph of \(G\) containing \(S\) that has a minimum number of edges. The Steiner interval for \(S\) is the collection of all vertices in \(G\) that belong to some Steiner tree for \(S\).
Let \(k\geq 2\) be an integer. A set \(X\) of vertices of \(G\) is \(k\)-Steiner convex if it contains the Steiner interval of every set of \(k\) vertices in \(X\). A vertex \(x\in X\) is an extreme vertex of \(X\) if \(X\setminus \{x\}\) is also \(k\)-Steiner convex. We call such vertices \(k\)-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.

MSC:

05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bilbao, J. M.; Edelman, P. H., The Shapley value on convex geometries, Discrete Appl. Math., 103, 33-40 (2000) · Zbl 0955.91002
[2] A. Brandstädt, V.B. Le, J.P. Spinrad, Graph classes: A survey, SIAM Monograph on Discrete Mathematics and Applications, Philidelphia, 1999; A. Brandstädt, V.B. Le, J.P. Spinrad, Graph classes: A survey, SIAM Monograph on Discrete Mathematics and Applications, Philidelphia, 1999
[3] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman and Hall: Chapman and Hall New York · Zbl 0890.05001
[4] Dragan, F. F.; Nicolai, F.; Brandstädt, A., Convexity and \(H H D\)-free graphs, SIAM J. Discrete Math., 12, 119-135 (1999) · Zbl 0916.05060
[5] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Alg. Disc. Math., 7, 433-444 (1986) · Zbl 0591.05056
[6] Jamison, B.; Olariu, S., On the semi-perfect elimination, Adv. Appl. Math., 9, 364-376 (1988) · Zbl 0684.05020
[7] Kubicka, E.; Kubicki, G.; Oellermann, O. R., Steiner intervals in graphs, Discrete Math., 81, 181-190 (1998) · Zbl 0898.05044
[8] M. Nielsen, O.R. Oellermann, Steiner trees and convex geometries (submitted for publication); M. Nielsen, O.R. Oellermann, Steiner trees and convex geometries (submitted for publication) · Zbl 1191.05037
[9] Oellermann, O. R.; Puertas, M. L., Steiner intervals and Steiner geodetic numbers in distance hereditary graphs, Discrete Math., 307, 88-96 (2007) · Zbl 1113.05030
[10] Rose, D.; Tarjan, R. E.; Leuker, G., Algorithm aspects of vertex elimination, SIAM J. Comput., 5, 266-283 (1976) · Zbl 0353.65019
[11] Tarjan, R. E.; Yannakakis, M., Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 566-579 (1984) · Zbl 0545.68062
[12] Van de Vel, M. J.L., Theory of Convex Structures (1993), North-Holland: North-Holland Amsterdam · Zbl 0785.52001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.