z-logo
open-access-imgOpen Access
Graphs with large geodetic number
Author(s) -
Hossein Ahangar Abdollahzadeh,
Saeed Kosari,
Seyed Mahmoud Sheikholeslami,
Lutz Volkmann
Publication year - 2015
Publication title -
filomat
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.449
H-Index - 34
eISSN - 2406-0933
pISSN - 0354-5180
DOI - 10.2298/fil1506361a
Subject(s) - combinatorics , mathematics , geodetic datum , disjoint sets , graph , bound graph , geodesic , discrete mathematics , graph power , line graph , geometry , geodesy , geography
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$.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom