Steiner Distance in Graphs--A Survey

Preprint English OPEN
Mao, Yaping;
(2017)
  • Subject: Mathematics - Combinatorics
    acm: TheoryofComputation_GENERAL | Hardware_INTEGRATEDCIRCUITS | MathematicsofComputing_DISCRETEMATHEMATICS | TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
    arxiv: Mathematics::Metric Geometry | Computer Science::Computational Geometry | Computer Science::Data Structures and Algorithms

For a connected graph $G$ of order at least $2$ and $S\subseteq V(G)$, the \emph{Steiner distance} $d_G(S)$ among the vertices of $S$ is the minimum size among all connected subgraphs whose vertex sets contain $S$. In this paper, we summarize the known results on the St... View more
  • References (57)
    57 references, page 1 of 6

    [1] J. Akiyama and F. Harary, A graph and its complement with specified properties, Internat. J. Math. & Math. Sci. 2(2) (1979), 223-228.

    [2] P. Ali, The Steiner diameter of a graph with prescribed girth, Discrete Math. 313(12) (2013), 1322-1326.

    [3] H.H. Ali, A. Boals, and N.S. Sherwani, Distance stable graphs, Paper read at 2nd Internat. Conf. in Graph Theory, Combinatorics, Algorithms and Applications, San Francisco, 1989.

    [4] P. Ali, P. Dankelmann, and S. Mukwembi, Upper bounds on the Steiner diameter of a graph, Discrete Appl. Math. 160 (2012), 1845-1850.

    [5] P. Ali, S. Mukwembi, and P. Dankelmann, Steiner diameter of 3, 4 and 5-connected maximal planar graphs, Discrete Appl. Math. 179 (2014), 222-228.

    [6] B.S. Anand, M. Changat, S. Klavˇzar, I. Peterin, Convex sets in lexicographic product of graphs, Graphs Combin. 28 (2012), 77-84.

    [7] J. M. Anthonisse, The rush in a directed graph, Technical Report BN 9/71, Stiching Math. Centrum, Amsterdam, October 1971.

    [8] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013), 466-546.

    [9] M. Atici, Computational complexity of geodetic set, Internat. J. Comput. Math. 79 (2002), 587-591.

    [10] S.P. Avann, Metric ternary distributive semi-lattices, Proc. Amer. Math. Sot. 12 (l961), 407-414.

  • Related Organizations (1)
  • Metrics
Share - Bookmark