The Steiner diameter of a graph

Document Type : Research Paper

Author

Department of Mathematics‎, ‎Qinghai Normal University‎, ‎Xining‎, ‎Qinghai 810008‎, ‎China.

Abstract

‎The Steiner distance of a graph‎, ‎introduced by Chartrand‎, ‎Oellermann‎, ‎Tian and Zou in 1989‎, ‎is a natural generalization of the‎ ‎concept of classical graph distance‎. ‎For a connected graph $G$ of‎ ‎order at least $2$ and $S\subseteq V(G)$‎, ‎the Steiner‎ ‎distance $d(S)$ among the vertices of $S$ is the minimum size among‎ ‎all connected subgraphs whose vertex sets contain $S$‎. ‎Let $n,k$ be‎ ‎two integers with $2\leq k\leq n$‎. ‎Then the Steiner‎ ‎$k$-eccentricity $e_k(v)$ of a vertex $v$ of $G$ is defined by‎ ‎$e_k(v)=\max \{d(S)\,|\,S\subseteq V(G)‎, |S|=k‎, and v\in S‎‎\}$‎. ‎Furthermore‎, ‎the Steiner $k$-diameter of $G$ is‎ ‎$sdiam_k(G)=\max \{e_k(v)\,| ‎v\in V(G)\}$‎. ‎In 2011‎, ‎Chartrand‎, ‎Okamoto and Zhang showed that $k-1\leq sdiam_k(G)\leq n-1$‎. ‎In this‎ ‎paper‎, ‎graphs with $sdiam_3(G)=2,3,n-1$ are characterized‎, ‎respectively‎. ‎We also consider the Nordhaus-Gaddum-type results for‎ ‎the parameter $sdiam_k(G)$‎. ‎We determine sharp upper and lower‎ ‎bounds of $sdiam_k(G)+sdiam_k(\overline{G})$ and $sdiam_k(G)\cdot‎ ‎sdiam_k(\overline{G})$ for a graph $G$ of order $n$‎. ‎Some‎ ‎graph classes attaining these bounds are also given. 

Keywords

Main Subjects

References

‎J‎. ‎Akiyama and F‎. ‎Harary‎, A graph and its complement with‎ ‎specified properties‎, Internat‎. ‎J‎. ‎Math‎. ‎Math‎. ‎Sci.‎ ‎2 (1979)‎, ‎no‎. ‎2‎, ‎223--228‎.
‎P‎. ‎Ali‎, ‎P‎. ‎Dankelmann and S‎. ‎Mukwembi‎, Upper bounds on the Steiner diameter of a graph‎, Discrete‎ ‎Appl‎. ‎Math. 160 (2012)‎, ‎no‎. ‎12‎, ‎1845--1850‎.
‎M‎. ‎Aouchiche and P‎. ‎Hansen‎, A survey of Nordhaus-Gaddum type relations‎, Discrete Appl‎. ‎Math. 161 (2013)‎, ‎no‎. ‎4-5‎, ‎466--546‎.
‎G.S‎. ‎Bloom‎, ‎J.W‎. ‎Kennedy and L.V‎. ‎Quintas‎, A characterization of graphs of‎ ‎diameter two‎, Amer‎. ‎Math‎. ‎Monthly 95 (1988)‎, ‎no‎. ‎1‎, ‎37--38‎.
‎J.A‎. ‎Bondy and U.S.R‎. ‎Murty‎, Graph Theory‎, Grad‎. ‎Texts in Math‎. ‎244‎, ‎Springer‎, ‎2008‎.
‎F‎. ‎Buckley and F‎. ‎Harary‎, Distance in Graphs‎, Addision-Wesley‎, ‎Redwood City‎, ‎CA‎, ‎1990‎.
‎J‎. ‎Cáceresa‎, ‎A‎. ‎Márquezb and M.L‎. ‎Puertasa‎, Steiner distance and convexity in graphs‎, European J‎. ‎Combin. 29 (2008)‎, ‎no‎. ‎3‎, ‎726--736‎.
‎G‎. ‎Chartrand‎, ‎O.R‎. ‎Oellermann‎, ‎S‎. ‎Tian and H.B‎. ‎Zou‎, Steiner distance in graphs‎, Ćasopis pro‎ ‎Pĕstování Matematiky‎, ‎ 114 (1989)‎, ‎no‎. ‎4‎, ‎399--410‎.
‎G‎. ‎Chartrand‎, ‎F‎. ‎Okamoto and P‎. ‎Zhang‎, Rainbow trees in graphs and generalized‎ ‎connectivity‎, Networks 55 (2010)‎, ‎no‎. ‎4‎, ‎360--367‎.
‎F.R.K‎. ‎Chung‎, Diameter of graphs‎: ‎Old problems and new results‎, 18th Southeastern Conf‎. ‎on Combinatorics‎, ‎Graph Theory and‎ ‎Computing‎, ‎ Congr‎. ‎Numer. 60 (1987)‎, ‎295--317‎.
‎P‎. ‎Dankelmann‎, ‎H.C‎. ‎Swart and O.R‎. ‎Oellermann‎, On the average Steiner distance of graphs with prescribed properties‎, Discrete Appl‎. ‎Math. 79 (1997)‎, ‎no‎. ‎1-3‎, ‎91--103‎.
‎P‎. ‎Dankelmann‎, ‎H‎. ‎Swart and O.R‎. ‎Oellermann‎, Bounds on the Steiner diameter of a graph‎, Combinatorics‎, ‎Graph Theory‎, ‎and Algorithms‎, ‎Vol‎. ‎I‎, ‎II (Kalamazoo‎, ‎MI‎, ‎1996)‎, ‎pp‎. ‎269--279‎, ‎New Issues Press‎, ‎Kalamazoo‎, ‎1999‎.
‎D.P‎. ‎Day‎, ‎O.R‎. ‎Oellermann and H.C‎. ‎Swart‎, Steiner Distance-hereditary graphs‎, SIAM J‎. ‎Discrete Math. 7 (1994)‎, ‎no‎. ‎3‎, ‎437--442‎.
‎D.Z‎. ‎Du‎, ‎Y.D‎. ‎Lyuu and D.F‎. ‎Hsu‎, Line digraph iteration and connectivity analysis of de Bruijn and Kautz graphs‎, IEEE Trans‎.‎Comput. 42 (1994)‎, ‎no‎. ‎5‎, ‎612--616‎.
‎A‎. ‎D'Atri and M‎. ‎Moscarini‎, Distance-Hereditary graphs‎, ‎Steiner trees‎, ‎and connected‎ ‎domination‎, SIAM J‎. ‎Comput. 17 (1988)‎, ‎no‎. ‎3‎, ‎521--538‎.
‎F.J‎. ‎Meyer and D‎. ‎K‎. ‎Pradhan‎, Flip-trees‎: ‎fault-tolerant graphs with wide containers‎, IEEE‎ ‎Trans‎. ‎Comput. 37 (1988)‎, ‎no‎. ‎4‎, ‎472--478‎.
‎M.R‎. ‎Garey and D.S‎. ‎Johnson‎, Computers and Intractibility‎: ‎A Guide to‎ ‎the Theory of NP-Completeness‎, IEEE‎ ‎Trans‎. ‎Comput. Freeman & Company‎, ‎New York‎, ‎1979‎.
‎W‎. ‎Goddard‎, ‎O.R‎. ‎Oellrmann and H.C‎. ‎Swart‎, Steiner distance stable graphs‎, Discrete Math. 132 (1994)‎, ‎no‎. ‎1-3‎, ‎65--73‎.
‎W‎. ‎Goddard and O.R‎. ‎Oellrmann‎, Distance in graphs‎, ‎in‎: ‎M‎. ‎Dehmer (ed.)‎, Structural Analysis of Complex Networks‎, ‎pp‎. ‎49-- 72‎, ‎Birkhäuser‎, ‎Dordrecht‎, ‎2011‎.
‎S.L‎. ‎Hakimi‎, Steiner's problem in graph and its implications‎, Networks 1 (1971)‎, ‎no‎. ‎2‎, ‎113--133‎.
‎F.K‎. ‎Hwang‎, ‎D.S‎. ‎Richards and P‎. ‎Winter‎, The Steiner Tree Problem‎, North-Holland‎, ‎Amsterdam‎, ‎1992‎.
‎D.F‎. ‎Hsu‎, On container width and length in graphs‎, ‎groups‎, ‎and networks‎, IEICE Transaction on Fundamentals of Electronics‎, ‎Communications and Computer Science‎, ‎77 (1994) 668--680‎.
‎D.F‎. ‎Hsu and T‎. Luczak‎, On the $k$-diameter of $k$-regular $k$-connected graphs‎, Discrete Math. 133 (1994)‎, ‎no‎. ‎1-3‎, ‎291--296‎.
‎A.Y‎. ‎Levi‎, Algorithm for shortest connection of a group of graph vertices‎, Sov‎. ‎Math‎. ‎Dokl. 12 (1971) 1477--1481‎.
‎S.J‎. ‎Xu‎, Some parameters of graph and its complement‎, Discrete Math. 65 (1987)‎, ‎no‎. ‎2‎, ‎197--207‎.
Bulletin of the Iranian Mathematical Society
Volume 43, Issue 2
April 2017
Pages 439-454

Files

History

  • Receive Date: 06 August 2014
  • Revise Date: 29 November 2015
  • Accept Date: 29 November 2015

Share

How to cite

Statistics