Extreme geodesic graphs

@article{Chartrand2002,
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\text\{--\}v$ geodesic of $G$, while for $S \subseteq V(G)$, the set $I[S]$ is the union of all sets $I[u, v]$ for $u, v \in S$. A set $S$ of vertices of $G$ for which $I[S]=V(G)$ is a geodetic set for $G$, and the minimum cardinality of a geodetic set is the geodetic number $g(G)$. A vertex $v$ in $G$ is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in $G$ is its extreme order $\mathop \{\mathrm \{e\}x\}(G)$. A graph $G$ is an extreme geodesic graph if $g(G) = \mathop \{\mathrm \{e\}x\}(G)$, that is, if every vertex lies on a $u\text\{--\}v$ geodesic for some pair $u$, $ v$ of extreme vertices. It is shown that every pair $a$, $ b$ of integers with $0 \le a \le b$ is realizable as the extreme order and geodetic number, respectively, of some graph. For positive integers $r, d,$ and $k \ge 2$, it is shown that there exists an extreme geodesic graph $G$ of radius $r$, diameter $d$, and geodetic number $k$. Also, for integers $n$, $ d, $ and $k$ with $2 \le d < n$, $2 \le k < n$, and $n -d - k +1 \ge 0$, there exists a connected extreme geodesic graph $G$ of order $n$, diameter $d$, and geodetic number $k$. We show that every graph of order $n$ with geodetic number $n-1$ is an extreme geodesic graph. On the other hand, for every pair $k$, $ n$ of integers with $2 \le k \le n-2$, there exists a connected graph of order $n$ with geodetic number $k$ that is not an extreme geodesic graph.},
author = {Chartrand, Gary, Zhang, Ping},
journal = {Czechoslovak Mathematical Journal},
keywords = {geodetic set; geodetic number; extreme order; extreme geodesic graph; geodetic set; geodetic number; extreme order; extreme geodesic graph},
language = {eng},
number = {4},
pages = {771-780},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Extreme geodesic graphs},
url = {http://eudml.org/doc/30743},
volume = {52},
year = {2002},
}

TY - JOUR
AU - Chartrand, Gary
AU - Zhang, Ping
TI - Extreme geodesic graphs
JO - Czechoslovak Mathematical Journal
PY - 2002
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 52
IS - 4
SP - 771
EP - 780
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\text{--}v$ geodesic of $G$, while for $S \subseteq V(G)$, the set $I[S]$ is the union of all sets $I[u, v]$ for $u, v \in S$. A set $S$ of vertices of $G$ for which $I[S]=V(G)$ is a geodetic set for $G$, and the minimum cardinality of a geodetic set is the geodetic number $g(G)$. A vertex $v$ in $G$ is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in $G$ is its extreme order $\mathop {\mathrm {e}x}(G)$. A graph $G$ is an extreme geodesic graph if $g(G) = \mathop {\mathrm {e}x}(G)$, that is, if every vertex lies on a $u\text{--}v$ geodesic for some pair $u$, $ v$ of extreme vertices. It is shown that every pair $a$, $ b$ of integers with $0 \le a \le b$ is realizable as the extreme order and geodetic number, respectively, of some graph. For positive integers $r, d,$ and $k \ge 2$, it is shown that there exists an extreme geodesic graph $G$ of radius $r$, diameter $d$, and geodetic number $k$. Also, for integers $n$, $ d, $ and $k$ with $2 \le d < n$, $2 \le k < n$, and $n -d - k +1 \ge 0$, there exists a connected extreme geodesic graph $G$ of order $n$, diameter $d$, and geodetic number $k$. We show that every graph of order $n$ with geodetic number $n-1$ is an extreme geodesic graph. On the other hand, for every pair $k$, $ n$ of integers with $2 \le k \le n-2$, there exists a connected graph of order $n$ with geodetic number $k$ that is not an extreme geodesic graph.
LA - eng
KW - geodetic set; geodetic number; extreme order; extreme geodesic graph; geodetic set; geodetic number; extreme order; extreme geodesic graph
UR - http://eudml.org/doc/30743
ER -