Original graphs of link graphs

Let $\mathrm{\ell }⩾0$ be an integer, and $G$ be a graph without loops. An $\mathrm{\ell }$-link of $G$ is a walk of length $\mathrm{\ell }$ in which consecutive edges are different. We identify an $\mathrm{\ell }$-link with its reverse sequence. The $\mathrm{\ell }$-link graph ${\mathbb{L}}_{\mathrm{\ell }}(G)$ of $G$ is defined to have vertices the $\mathrm{\ell }$-links of $G$, such that two vertices of ${\mathbb{L}}_{\mathrm{\ell }}(G)$ are adjacent if their corresponding $\mathrm{\ell }$-links are the initial and final subsequences of an $(\mathrm{\ell }+1)$-link of $G$. A graph $G$ is called an $\mathrm{\ell }$-root of a graph $H$ if ${\mathbb{L}}_{\mathrm{\ell }}(G)\cong H$. For example, ${\mathbb{L}}_0(G)\cong G$. And the $1$-link graph of a simple graph is the line graph of that graph. Moreover, let $H$ be a finite connected simple graph. Whitney’s isomorphism theorem (1932) states if $H$ has two connected nonnull simple $1$-roots, then $H\cong K_3$, and the two $1$-roots are isomorphic to $K_3$ and $K_{1,3}$ respectively. This paper investigates the $\mathrm{\ell }$-roots of finite graphs. We show that every $\mathrm{\ell }$-root is a certain combination of a finite minimal $\mathrm{\ell }$-root and trees of bounded diameter. This transfers the study of $\mathrm{\ell }$-roots into that of finite minimal $\mathrm{\ell }$-roots. As a qualitative generalisation of Whitney’s isomorphism theorem, we bound from above the number, size, order and maximum degree of minimal $\mathrm{\ell }$-roots of a finite graph. This work forms the basis for solving the recognition and determination problems for $\mathrm{\ell }$-link graphs in our future papers. As a byproduct, we characterise the $\mathrm{\ell }$-roots of some special graphs including cycles. Similar results are obtained for path graphs introduced by Broersma and Hoede (1989). $G$ is an $\mathrm{\ell }$-path root of a graph $H$ if $H$ is isomorphic to the $\mathrm{\ell }$-path graph of $G$. We bound from above the number, size and order of minimal $\mathrm{\ell }$-path roots of a finite graph.