# Extreme geodesic graphs

• Volume: 52, Issue: 4, page 771-780
• ISSN: 0011-4642

top

## Abstract

top
For two vertices $u$ and $v$ of a graph $G$, the closed interval $I\left[u,v\right]$ consists of $u$, $v$, and all vertices lying in some $u\text{--}v$ geodesic of $G$, while for $S\subseteq V\left(G\right)$, the set $I\left[S\right]$ is the union of all sets $I\left[u,v\right]$ for $u,v\in S$. A set $S$ of vertices of $G$ for which $I\left[S\right]=V\left(G\right)$ is a geodetic set for $G$, and the minimum cardinality of a geodetic set is the geodetic number $g\left(G\right)$. 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 $\mathrm{e}x\left(G\right)$. A graph $G$ is an extreme geodesic graph if $g\left(G\right)=\mathrm{e}x\left(G\right)$, 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, $2\le k, 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.

## How to cite

top

Chartrand, Gary, and Zhang, Ping. "Extreme geodesic graphs." Czechoslovak Mathematical Journal 52.4 (2002): 771-780. <http://eudml.org/doc/30743>.

@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 -

## References

top
1. Theorie der konvexen Körper. Springer, Berlin, 1934; transl. by L. Boron, C. Christenson, and B. Smith: Theory of Convex Bodies. BCS Associates, Moscow, ID, 1987, . MR0920366
2. Distance in Graphs, Addison-Wesley, Redwood City, CA, 1990. (1990) MR1045632
3. Closed geodetic games for graphs, Congr. Numer. 47 (1985), 131–138. (1985) MR0830675
4. 10.1080/16073606.1985.9631921, Quaestiones Math. 8 (1986), 321–234. (1986) MR0854054DOI10.1080/16073606.1985.9631921
5. 10.1002/net.10007, Networks 39 (2002), 1–6. (2002) MR1871701DOI10.1002/net.10007
6. On the hull number of a graph, Ars Combin 57 (2000), 129–138. (2000) MR1796634
7. Graphs $&$ Digraphs, third edition, Chapman Hall, New York, 1996. (1996) MR1408678
8. 10.1007/s003730200014, Graphs Combin. 18 (2002), 209–217. (2002) MR1913663DOI10.1007/s003730200014
9. 10.1023/A:1013725215238, Czechoslovak Math. J. 51(126) (2001), 847–858. (2001) MR1864046DOI10.1023/A:1013725215238
10. 10.1006/eujc.1999.0301, European J. Combin. 21 (2000), 181–189. (2000) MR1742433DOI10.1006/eujc.1999.0301
11. Realizable ratios in graph theory: geodesic parameters, Bull. Inst. Combin. Appl. 27 (1999), 69–80. (1999) MR1714291
12. Graph Theory. Addison-Wesley, Reading, MA, 1969. (1969) MR0256911
13. Convexity in graphs: achievement and avoidance games, Ann. Discrete Math. 20 (1983), 323. (1983)
14. 10.1016/0895-7177(93)90259-2, Math. Comput. Modelling 17 (1993), 89–95. (1993) MR1236514DOI10.1016/0895-7177(93)90259-2
15. 10.4310/jdg/1214436096, J. Differential Geom. 16 (1981), 185–190. (1981) MR0638785DOI10.4310/jdg/1214436096
16. The Interval Function of a Graph Mathematisch Centrum, Amsterdam, 1980. (1980) MR0605838
17. A characterization of the interval function of a connected graph, Czechoslovak Math. J. 44(119) (1994), 173–178. (1994) MR1257943
18. Characterizing of the interval function of a connected graph, Math. Bohem. 123 (1998), 137–144. (1998) MR1673965
19. 10.1080/16073606.1988.9632167, Quaestiones Math. 12 (1988), 115–119. (1988) MR0979252DOI10.1080/16073606.1988.9632167
20. 10.1016/0012-365X(73)90116-7, Discrete Math. 4 (1973), 71–75. (1973) Zbl0265.05123MR0313126DOI10.1016/0012-365X(73)90116-7

top

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.