Graphs with Minimum Spanner \(\xi(G)\geq 2 \rho-1\)

Albert William1, Antony Kishore1, Paul Manuel2
1Department of Mathematics, Loyola College, Chennai, India
2Department of Information Science, Kuwait University, Kuwait

Abstract

The parameter \( t \) of a tree \( t \)-spanner of a graph is always bounded by \( 2\lambda \) where \( \lambda \) is the diameter of the graph. In this paper, we establish a sufficient condition for graphs to have the minimum spanner at least \( 2\rho – 1 \) where \( \rho \) is the radius. We also obtain a characterization for tree \( 3 \)-spanner admissible chordal graphs in terms of tree \( 3 \)-spanner admissibility of certain subgraphs.

Keywords: spanning subgraph, tree ¢-spanner, Petersen graph, chordal graph, split graph.