Extreme Geodesic Graphs
Gary Chartrand, Ping Zhang · Czechoslovak Mathematical Journal · 2002
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 − v geodesic of G , while for S ⫅ V ( G ), the set I [ S ] is the union of all sets I [ u , v ] for u , v ε 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 ex( G ). A graph G is an extreme geodesic graph if g ( G ) = ex( G ), that is, if every vertex lies on a u − v geodesic for some pair u , v of extreme vertices. It is shown that every pair a , b of integers with 0 ⩽ a ⩽ b is realizable as the extreme order and geodetic number, respectively, of some graph. For positive integers r , d , and k ⩾ 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 ⩽ d > n , 2 ⩽ k > n , and n − d − k + 1 ⩾ 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 ⩽ k ⩽ n − 2, there exists a connected graph of order n with geodetic number k that is not an extreme geodesic graph.