The Steiner diameter of a graph

Publication date 25 January 2019

Full work available at URL https://arxiv.org/abs/1509.02801, http://bims.iranjournals.ir/article_941.html

complementary graph diameter Steiner \(k\)-diameter Steiner tree

Trees (05C05) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

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 s u b s e t e q V (G)

, the emph{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 l e q k l e q n

. Then the emph{Steiner

k

-eccentricity

e_{k} (v)

} of a vertex

v

of

G

is defined by

e_{k} (v) = m a x d (S), |, S s u b s e t e q V (G), | S | = k, a n d v i n S

. Furthermore, the emph{Steiner

k

-diameter} of

G

is

s d i a m_{k} (G) = m a x e_{k} (v), |, v i n V (G)

. In 2011, Chartrand, Okamoto and Zhang showed that

k - 1 l e q s d i a m_{k} (G) l e q n - 1

. In this paper, graphs with

s d i a m_{3} (G) = 2, 3, n - 1

are characterized, respectively. We also consider the Nordhaus-Gaddum-type results for the parameter

s d i a m_{k} (G)

. We determine sharp upper and lower bounds of

s d i a m_{k} (G) + s d i a m_{k} (o v e r l i n e G)

and

s d i a m_{k} (G) c d o t s d i a m_{k} (o v e r l i n e G)

for a graph

G

of order

n

. Some graph classes attaining these bounds are also given.

Recommendations

Cited in

(14)

This page was built for publication: The Steiner diameter of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4613728)