Title: | Extreme geodesic graphs (English) |

Author: | Chartrand, Gary |

Author: | Zhang, Ping |

Language: | English |

Journal: | Czechoslovak Mathematical Journal |

ISSN: | 0011-4642 (print) |

ISSN: | 1572-9141 (online) |

Volume: | 52 |

Issue: | 4 |

Year: | 2002 |

Pages: | 771-780 |

Summary lang: | English |

. | |

Category: | math |

. | |

Summary: | 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. (English) |

Keyword: | geodetic set |

Keyword: | geodetic number |

Keyword: | extreme order |

Keyword: | extreme geodesic graph |

MSC: | 05C12 |

MSC: | 05C35 |

idZBL: | Zbl 1009.05051 |

idMR: | MR1940058 |

. | |

Date available: | 2009-09-24T10:56:37Z |

Last updated: | 2020-07-03 |

Stable URL: | http://hdl.handle.net/10338.dmlcz/127763 |

. | |

Reference: | [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 0920366 |

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

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

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

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

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

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

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

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

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

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

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

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

Reference: | [h:geo] F. Harary, E. Loukakis and C. Tsouros: The geodetic number of a graph.Math. Comput. Modelling 17 (1993), 89–95. MR 1236514, 10.1016/0895-7177(93)90259-2 |

Reference: | [hn:cg] F. Harary and J. Nieminen: Convexity in graphs.J. Differential Geom. 16 (1981), 185–190. MR 0638785, 10.4310/jdg/1214436096 |

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

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

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

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

Reference: | [o:gs] P. A. Ostrand: Graphs with specified radius and diameter.Discrete Math. 4 (1973), 71–75. Zbl 0265.05123, MR 0313126, 10.1016/0012-365X(73)90116-7 |

. |

Files | Size | Format | View |
---|---|---|---|

CzechMathJ_52-2002-4_10.pdf | 345.8Kb | application/pdf |
View/ |