Original graphs of link graphs

Original · EN

Let ℓ 0 be an integer, and G be a graph without loops. An ℓ-link of G is a walk of length ℓ in which consecutive edges are different. We identify an ℓ-link with its reverse sequence. The ℓ-link graph Lℓ(G) of G is defined to have vertices the ℓ-links of G, such that two vertices of Lℓ(G) are adjacent if their corresponding ℓ-links are the initial and final subsequences of an (ℓ + 1)-link of G. A graph G is called an ℓ-root of a graph H if Lℓ(G) H. For example, L₀(G) 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 K₃, and the two 1-roots are isomorphic to K₃ and K₁, ₃ respectively. This paper investigates the ℓ-roots of finite graphs. We show that every ℓ-root is a certain combination of a finite minimal ℓ-root and trees of bounded diameter. This transfers the study of ℓ-roots into that of finite minimal ℓ-roots. As a qualitative generalisation of Whitney's isomorphism theorem, we bound from above the number, size, order and maximum degree of minimal ℓ-roots of a finite graph. This work forms the basis for solving the recognition and determination problems for ℓ-link graphs in our future papers. As a byproduct, we characterise the ℓ-roots of some special graphs including cycles. Similar results are obtained for path graphs introduced by Broersma and Hoede (1989). G is an ℓ-path root of a graph H if H is isomorphic to the ℓ-path graph of G. We bound from above the number, size and order of minimal ℓ-path roots of a finite graph.