Graphs with large geodetic number
Hossein Ahangar Abdollahzadeh, Saeed Kosari, Seyed Mahmoud Sheikholeslami, Lutz Volkmann · Filomat · 2015
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 S. A subset S of vertices of G is a geodetic set if I[S] = V. The geodetic number 1(G) is the minimum cardinality of a geodetic set of G. It was shown that a connected graph G of order n ≥ 3 has geodetic number n - 1 if and only if G is the join of K1 and pairwise disjoint complete graphs Kn1,Kn2,..., Knr, that is, G = (Kn1 Kn2... Knr ) + K1, where r ≥ 2, n1, n2,...., nr are positive integers with n1 + n2 + ... + nr = n - 1. In this paper we characterize all connected graphs G of order n ≥ 3 with 1(G) = n - 2.