Vertex-to-clique detour distance in graphs

Abstract

Let vv be a vertex and CC a clique in a connected graph GG. A vertex-to-clique u−Cu−C path P is a u−vu−v path, where v is a vertex in CC such that PP contains no vertices of CC other than vv. The vertex-to-clique distance, d(u,C)d(u,C) is the length of a smallest u−Cu−C path in GG. A u−Cu−C path of length d(u,C)d(u,C) is called a u−Cu−C geodesic. The vertex-to-clique eccentricity e1(u)e1(u) of a vertex uu in GG is the maximum vertex-to-clique distance from uu to a clique C∈ζC∈ζ, where ζζ is the set of all cliques in GG. The vertex-to-clique radius r1r1 of GG is the minimum vertex-to-clique eccentricity among the vertices of GG, while the vertex-to-clique diameter d1d1 of GG is the maximum vertex-to-clique eccentricity among the vertices of GG. Also the vertex toclique detour distance, D(u,C)D(u,C) is the length of a longest u−Cu−C path in GG. A u−Cu−C path of length D(u,C)D(u,C) is called a u−Cu−C detour. The vertex-to-clique detour eccentricity eD1(u)eD1(u) of a vertex uu in GG is the maximum vertex-toclique detour distance from u to a clique C∈ζC∈ζ in GG. The vertex-to-clique detour radius R1R1 of GG is the minimum vertex-to-clique detour eccentricity among the vertices of GG, while the vertex-to-clique detour diameter D1D1 of GG is the maximum vertex-to-clique detour eccentricity among the vertices of GG. It is shown that R1≤D1R1≤D1 for every connected graph GG and that every two positive integers a and b with 2≤a≤b2≤a≤b are realizable as the vertex-to-clique detour radius and the vertex-to-clique detour diameter, respectively, of some connected graph. Also it is shown that for any three positive integers aa, bb, cc with 2≤a≤b<c2≤a≤b<c, there exists a connected graph G such that r1=ar1=a, R1=bR1=b, R=cR=c and for any three positive integers aa, bb, cc with 2≤a≤b<c2≤a≤b<c and a+c≤2ba+c≤2b, there exists a connected graph GG such that d1=ad1=a, D1=bD1=b, D=cD=c.