Geodetic sets in graphs

Gary Chartrand, Frank Harary, and Ping Zhang. "Geodetic sets in graphs." Discussiones Mathematicae Graph Theory 20.1 (2000): 129-138. <http://eudml.org/doc/270425>.

@article{GaryChartrand2000,
abstract = {For two vertices u and v of a graph G, the closed interval I[u,v] consists of u, v, and all vertices lying in some u-v geodesic in G. If S is a set of vertices of G, then I[S] is the union of all sets I[u,v] for u, v ∈ S. If I[S] = V(G), then S is a geodetic set for G. The geodetic number g(G) is the minimum cardinality of a geodetic set. A set S of vertices in a graph G is uniform if the distance between every two distinct vertices of S is the same fixed number. A geodetic set is essential if for every two distinct vertices u,v ∈ S, there exists a third vertex w of G that lies in some u-v geodesic but in no x-y geodesic for x, y ∈ S and \{x,y\} ≠ \{u,v\}. It is shown that for every integer k ≥ 2, there exists a connected graph G with g(G) = k which contains a uniform, essential minimum geodetic set. A minimal geodetic set S has no proper subset which is a geodetic set. The maximum cardinality of a minimal geodetic set is the upper geodetic number g⁺(G). It is shown that every two integers a and b with 2 ≤ a ≤ b are realizable as the geodetic and upper geodetic numbers, respectively, of some graph and when a < b the minimum order of such a graph is b+2.},
author = {Gary Chartrand, Frank Harary, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {geodetic set; geodetic number; upper geodetic number; distance; diameter},
language = {eng},
number = {1},
pages = {129-138},
title = {Geodetic sets in graphs},
url = {http://eudml.org/doc/270425},
volume = {20},
year = {2000},
}

TY - JOUR
AU - Gary Chartrand
AU - Frank Harary
AU - Ping Zhang
TI - Geodetic sets in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 1
SP - 129
EP - 138
AB - For two vertices u and v of a graph G, the closed interval I[u,v] consists of u, v, and all vertices lying in some u-v geodesic in G. If S is a set of vertices of G, then I[S] is the union of all sets I[u,v] for u, v ∈ S. If I[S] = V(G), then S is a geodetic set for G. The geodetic number g(G) is the minimum cardinality of a geodetic set. A set S of vertices in a graph G is uniform if the distance between every two distinct vertices of S is the same fixed number. A geodetic set is essential if for every two distinct vertices u,v ∈ S, there exists a third vertex w of G that lies in some u-v geodesic but in no x-y geodesic for x, y ∈ S and {x,y} ≠ {u,v}. It is shown that for every integer k ≥ 2, there exists a connected graph G with g(G) = k which contains a uniform, essential minimum geodetic set. A minimal geodetic set S has no proper subset which is a geodetic set. The maximum cardinality of a minimal geodetic set is the upper geodetic number g⁺(G). It is shown that every two integers a and b with 2 ≤ a ≤ b are realizable as the geodetic and upper geodetic numbers, respectively, of some graph and when a < b the minimum order of such a graph is b+2.
LA - eng
KW - geodetic set; geodetic number; upper geodetic number; distance; diameter
UR - http://eudml.org/doc/270425
ER -