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

## Abstract

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 |

Subjects: | UNSPECIFIED |

Faculty: | UNSPECIFIED |

Depositing User: | Dr David Allingham |

Date Deposited: | 28 Sep 2012 12:05 |

Last Modified: | 28 Sep 2012 12:05 |

URI: | https://docserver.carma.newcastle.edu.au/id/eprint/1155 |

### Actions (login required)

View Item |