# Extreme geodesic graphs

Czechoslovak Mathematical Journal (2002)

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

## Access Full Article

top## Abstract

top## How to cite

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

## Citations in EuDML Documents

top## NotesEmbed ?

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