The Rotation Index Of A Graph

A rooted graph is a pair \((G, x)\), where \(G\) is a simple undirected graph and \(x \in V(G)\). If \(G\) is rooted at \(x\), its \(k\)-th rotation number \(h_k(G, x)\) is the minimum number of edges in a graph \(F\) of order \(|G| + k\) such that for every \(v \in V(F)\) we can find a copy of \(G\) in \(F\) with the root vertex \(x\) at \(v\); any such \(F\) of size \(h_k(G, x)\) is called a minimal graph. In this paper we prove that if \((G, x)\) is a rooted graph with \(d_{G}(x) = d\) then

\[p(G, x)=\lim_{k \to \infty} \frac{h_k(G, x)}{k} \]

exists and satisfies \(d/2 \leq p(G, x) \leq d\), where \(p(G, x)\) is termed the rotation index of \((G, x)\). We obtain the precise value of this parameter for several classes of rooted graphs and describe the asymptotic behaviour of corresponding minimal graphs.