JPRM-Vol. 1 (2016), Issue 1, pp. 45 – 59
Open Access Full-Text PDF
I. Keerthi Asir, S. Athisayanathan
Abstract: Let \(v\) be a vertex and \(C\) a clique in a connected graph \(G\). A vertex-to-clique \(u − C\) path P is a \(u − v\) path, where v is a vertex in \(C\) such that \(P\) contains no vertices of \(C\) other than \(v\). The vertex-to-clique distance, \(d(u, C)\) is the length of a smallest \(u−C\) path in \(G\). A \(u−C\) path of length \(d(u, C)\) is called a \(u − C\) geodesic. The vertex-to-clique eccentricity \(e_1(u)\) of a vertex \(u\) in \(G\) is the maximum vertex-to-clique distance from \(u\) to a clique \(C ∈ ζ\), where \(ζ\) is the set of all cliques in \(G\). The vertex-to-clique radius \(r_1\) of \(G\) is the minimum vertex-to-clique eccentricity among the vertices of \(G\), while the vertex-to-clique diameter \(d_1\) of \(G\) is the maximum vertex-to-clique eccentricity among the vertices of \(G\). Also the vertex toclique detour distance, \(D(u, C)\) is the length of a longest \(u−C\) path in \(G\). A \(u−C\) path of length \(D(u, C)\) is called a \(u−C\) detour. The vertex-to-clique detour eccentricity \(e_{D1}(u)\) of a vertex \(u\) in \(G\) is the maximum vertex-toclique detour distance from u to a clique \(C ∈ ζ\) in \(G\). The vertex-to-clique detour radius \(R_1\) of \(G\) is the minimum vertex-to-clique detour eccentricity among the vertices of \(G\), while the vertex-to-clique detour diameter \(D_1\) of \(G\) is the maximum vertex-to-clique detour eccentricity among the vertices of \(G\). It is shown that \(R_1 ≤ D_1\) for every connected graph \(G\) and that every two positive integers a and b with \(2 ≤ 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 \(a\), \(b\), \(c\) with \(2 ≤ a ≤ b < c\), there exists a connected graph G such that \(r_1 = a\), \(R_1 = b\), \(R = c\) and for any three positive integers \(a\), \(b\), \(c\) with \(2 ≤ a ≤ b < c\) and \(a + c ≤ 2b\), there exists a connected graph \(G\) such that \(d_1 = a\), \(D_1 = b\), \(D = c\).