Graphs which are linked structures

Eggleton, Roger and Adams, Peter and MacDougall, James A. (2009) Graphs which are linked structures. Congressus Numerantium, 199 .

Full text not available from this repository.


A linked pair is a graph H = G� � G� formed from (1) a given finite graph G,(2) isomorphic induced proper subgraphs K and K*, not necessarily distinct, and (3) a graph isomorphism �: K* � K. The graph isomorphism �: G� � G� is the extension of a to G� = G so that G� � G� = K. The ingredients of the linked pair construction are the initial link G, the kernel K, the prekernel K*, and the shift �; the extended map � is the link isomorphism. Iteration of this construction for any n � 2 yields an n-linked chain �{Gr = �r(G) : 0 � r < n}, with Gr � Gr�� � K for 0 � r < n, and eventually leads to the free linked chain �{Gr = �r(G) : r � Z}. For suitable n, imposing a periodic equivalence relation on the vertices of the free linked chain yields an n-linked cycle, corresponding to requiring Gn = G� in the n-linked chain. The resultant finite graph is the union of a sequence of n induced subgraphs isomorphic to G, consecutive pairs having intersection isomorphic to K; the collapsed isomorphism, � is an automorphism of order n, All graphs with an automorphism of order n > 2, and many with an automorphism of order n = 2, are in fact n-linked cycles, and this viewpoint leads to a "generalized factorization" of such graphs.

Item Type: Article
Uncontrolled Keywords: graph isomorphism, factorization, linked chain, linked cycle
Depositing User: Dr David Allingham
Date Deposited: 28 Sep 2012 12:05
Last Modified: 28 Sep 2012 12:05

Actions (login required)

View Item