Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/916332
- Title
- Graphs which are linked structures
- Author/Creator
-
Eggleton, Roger;
Adams, Peter;
MacDougall, James A.
- Institution
- The University of Newcastle. Faculty of Science & Information Technology, School of Mathematical and Physical Sciences
- Description
- 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.
- Relation
- Congressus Numerantium Vol. 199, p. 75-88
- Relation
- http://utilitasmathematica.org
- Date
- 2009
- Publisher
- Utilitas Mathematica Publishing
- Keyword(s)
-
graph isomorphism;
factorization;
linked chain;
linked cycle
- Resource Type
- journal article
- Identifier
- http://hdl.handle.net/1959.13/916332
- Identifier
- ISSN:0384-9864
- Reviewed
21 Visitors
22 Hits
0 Downloads
