Geodesic
Extreme geodesic graphs
Czechoslovak Mathematical Journal, Tome 52 (2002) no. 4, pp. 771-780 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 ex}(G)$. A graph $G$ is an extreme geodesic graph if $g(G) = \mathop {\mathrm ex}(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.
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 ex}(G)$. A graph $G$ is an extreme geodesic graph if $g(G) = \mathop {\mathrm ex}(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.
Classification : 05C12, 05C35
Keywords: geodetic set; geodetic number; extreme order; extreme geodesic graph 
@article{CMJ_2002_52_4_a9,
     author = {Chartrand, Gary and Zhang, Ping},
     title = {Extreme geodesic graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {771--780},
     year = {2002},
     volume = {52},
     number = {4},
     mrnumber = {1940058},
     zbl = {1009.05051},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2002_52_4_a9/}
}
TY  - JOUR
AU  - Chartrand, Gary
AU  - Zhang, Ping
TI  - Extreme geodesic graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2002
SP  - 771
EP  - 780
VL  - 52
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMJ_2002_52_4_a9/
LA  - en
ID  - CMJ_2002_52_4_a9
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A Zhang, Ping
%T Extreme geodesic graphs
%J Czechoslovak Mathematical Journal
%D 2002
%P 771-780
%V 52
%N 4
%U http://geodesic.mathdoc.fr/item/CMJ_2002_52_4_a9/
%G en
%F CMJ_2002_52_4_a9
Chartrand, Gary; Zhang, Ping. Extreme geodesic graphs. Czechoslovak Mathematical Journal, Tome 52 (2002) no. 4, pp. 771-780. http://geodesic.mathdoc.fr/item/CMJ_2002_52_4_a9/

[bf] T. Bonnesen and W. Fenchel: 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. | MR

[bh:dg] F. Buckley and F. Harary: Distance in Graphs. Addison-Wesley, Redwood City, CA, 1990. | MR

[BH2] F. Buckley and F. Harary: Closed geodetic games for graphs. Congr. Numer. 47 (1985), 131–138. | MR

[BH3] F. Buckley and F. Harary: Geodetic games for graphs. Quaestiones Math. 8 (1986), 321–234. | DOI | MR

[chz:geo] G. Chartrand, F. Harary, and P. Zhang: On the geodetic number of a graph. Networks 39 (2002), 1–6. | DOI | MR

[chz:hn] G. Chartrand, F. Harary, and P. Zhang: On the hull number of a graph. Ars Combin 57 (2000), 129–138. | MR

[cl:gd] G. Chartrand and L. Lesniak: Graphs $\&$ Digraphs, third edition. Chapman $\&$ Hall, New York, 1996. | MR

[cwz:cn] G. Chartrand, C. E. Wall and P. Zhang: The convexity number of a graph. Graphs Combin. 18 (2002), 209–217. | DOI | MR

[cz:fcn] G. Chartrand and P. Zhang: The forcing convexity number of a graph. Czechoslovak Math. J. 51(126) (2001), 847–858. | DOI | MR

[cz:dgeo] G. Chartrand and P. Zhang: The geodetic number of oriented graphs. European J. Combin. 21 (2000), 181–189. | DOI | MR

[cz:rrg] G. Chartrand and P. Zhang: Realizable ratios in graph theory: geodesic parameters. Bull. Inst. Combin. Appl. 27 (1999), 69–80. | MR

[h:gt] F. Harary: Graph Theory. Addison-Wesley, Reading, MA. 1969. | MR

[h:con] F. Harary: Convexity in graphs: achievement and avoidance games. Ann. Discrete Math. 20 (1983), 323.

[h:geo] F. Harary, E. Loukakis and C. Tsouros: The geodetic number of a graph. Math. Comput. Modelling 17 (1993), 89–95. | DOI | MR

[hn:cg] F. Harary and J. Nieminen: Convexity in graphs. J. Differential Geom. 16 (1981), 185–190. | DOI | MR

[m] H. M. Mulder: The Interval Function of a Graph Mathematisch Centrum, Amsterdam. 1980. | MR

[n1] L. Nebeský: A characterization of the interval function of a connected graph. Czechoslovak Math. J. 44(119) (1994), 173–178. | MR

[n2] L. Nebeský: Characterizing of the interval function of a connected graph. Math. Bohem. 123 (1998), 137–144. | MR

[N3] M. Nečásková: A note on the achievement geodetic games. Quaestiones Math. 12 (1988), 115–119. | DOI | MR

[o:gs] P. A. Ostrand: Graphs with specified radius and diameter. Discrete Math. 4 (1973), 71–75. | DOI | MR | Zbl