### Graphs with Large Geodetic Number

#### Abstract

For two vertices $u$ and $v$ of a graph $G$, the set $I[u, v]$

consists of all vertices lying on some $u-v$ geodesic in $G$. If

$S$ is a set of vertices of $G$, then $I[S]$ is the union of all

sets $I[u,v]$ for $u, v \in S$. A subset $S$ of vertices of $G$ is

a {\em geodetic set} if $I[S]=V$. The {\em geodetic number}

$g(G)$ is the minimum cardinality of a geodetic set of $G$. It was

shown that a connected graph $G$ of order $n\ge 3$ has geodetic

number $n-1$ if and only if $G$ is the join of $K_1$ and pairwise

disjoint complete graphs $K_{n_1} ,K_{n_2},\ldots, K_{n_r}$, that

is, $G=(K_{n_1}\cup K_{n_2}\cup\ldots K_{n_r})+ K_1$, where $r\ge

2$, $n_1, n_2,\ldots, n_r$ are positive integers with $n_1+n_2

+\ldots+ n_r =n - 1$. In this paper we characterize all connected

graphs $G$ of order $n\ge 3$ with $g(G)=n-2$.

consists of all vertices lying on some $u-v$ geodesic in $G$. If

$S$ is a set of vertices of $G$, then $I[S]$ is the union of all

sets $I[u,v]$ for $u, v \in S$. A subset $S$ of vertices of $G$ is

a {\em geodetic set} if $I[S]=V$. The {\em geodetic number}

$g(G)$ is the minimum cardinality of a geodetic set of $G$. It was

shown that a connected graph $G$ of order $n\ge 3$ has geodetic

number $n-1$ if and only if $G$ is the join of $K_1$ and pairwise

disjoint complete graphs $K_{n_1} ,K_{n_2},\ldots, K_{n_r}$, that

is, $G=(K_{n_1}\cup K_{n_2}\cup\ldots K_{n_r})+ K_1$, where $r\ge

2$, $n_1, n_2,\ldots, n_r$ are positive integers with $n_1+n_2

+\ldots+ n_r =n - 1$. In this paper we characterize all connected

graphs $G$ of order $n\ge 3$ with $g(G)=n-2$.

#### Full Text:

PDF### Refbacks

- There are currently no refbacks.