Radius and Diameter with respect to Cliques in Graphs

Abstract

Let $G$ be a connected graph. In this paper, we introduce the concepts of vertex-to-clique $radius$ $r_1$, vertex-to-clique $diameter$ $d_1$, clique-to-vertex $radius$ $r_2$, clique-to-vertex $diameter$ $d_2$, clique-to-clique $radius$ $r_3$, and clique-to-clique $diameter$ $d_3$ in $G$. We prove that for any connected graph, $r_i\le d_i\le 2r_i+1$ for $i=1,2,3$. We also find expressions for $d_1$, $d_2$, and $d_3$ for a tree $T$ in terms of $r_1$, $r_2$, and $r_3$ respectively, which determine the cardinality of each $Z_i(T)$, where $Z_i(T)$ is the vertex-to-clique, the clique-to-vertex, and the clique-to-clique center respectively of $T$ for $i=1,2,3$. If $G$ is a graph that is not a tree and if $g(G)$ denotes the girth of the graph, then its relation with each of $d_1$, $d_2$, and $d_3$ is discussed. We also characterize the class of graphs $G$ such that $G$ is not a tree, $d_3\ne 0$, and $g(G)=2d_3+3$.