Self-Centered Super Graph of a Graph and Center Number of a Graph

Abstract

In this paper, an algorithm for constructing self-centered graphs from trees and two more algorithms for constructing self-centered graphs from a given connected graph \(G\), by adding edges are discussed. Motivated by this, a new graph theoretic parameter \(sc_r(G)\), the minimum number of edges added to form a self-centered graph from \(G\) is defined. Bounds for this parameter are obtained and exact values of this parameter for several classes of graphs are also obtained.