Clique-to-vertex detour distance in graphs

Abstract

Let CC be a clique and vv a vertex in a connected graph GG. A clique-to-vertex C−vC−v path PP is a u−vu−v path, where u is a vertex in CC such that PP contains no vertices of CC other than uu. The clique-to-vertex distance, d(C,v)d(C,v) is the length of a smallest C−vC−v path in GG. A C−vC−v path of length d(C,v)d(C,v) is called a C−vC−v geodesic. The clique-to-vertex eccentricity e2(C)e2(C) of a clique CC in G is the maximum clique-to-vertex distance from CC to a vertex v∈Vv∈V in GG. The clique-to-vertex radius r2r2 of GG is the minimum clique-to-vertex eccentricity among the cliques of GG, while the clique-to-vertex diameter d−2d−2 of GG is the maximum cliqueto-vertex eccentricity among the cliques of GG. Also The clique-to-vertex detour distance, D(C,v)D(C,v) is the length of a longest C−vC−v path in GG. A C−vC−v path of length D(C,v)D(C,v) is called a  (C −v\) detour. The clique-to-vertex detour eccentricity eD2(C)eD2(C) of a clique CC in GG is the maximum clique-tovertex detour distance from CC to a vertex v∈Vv∈V in  (G\). The clique-to-vertex detour radius R2R2 of GG is the minimum clique-to-vertex detour eccentricity among the cliques of GG, while the clique-to-vertex detour diameter D2D2 of GG is the maximum clique-to-vertex detour eccentricity among the cliques of GG. It is shown that R2≤D2R2≤D2 for every connected graph GG and that every two positive integers a and b with 2≤a≤b2≤a≤b are realizable as the clique-tovertex detour radius and the clique-to-vertex detour diameter respectively of some connected graph. Also it is shown that for any two positive integers a and b with 2≤a≤b2≤a≤b, there exists a connected graph GG such that r2=ar2=a, R2=bR2=b and it is shown that for any two positive integers a and b with 2≤a≤b2≤a≤b, there exists a connected graph GG such that d2=ad2=a, D2=bD2=b.