- Title
- Graphs which are linked structures
- Creator
- Eggleton, Roger; Adams, Peter; MacDougall, James A.
- Relation
- Congressus Numerantium Vol. 199, p. 75-88
- Relation
- http://utilitasmathematica.org
- Publisher
- Utilitas Mathematica Publishing
- Resource Type
- journal article
- Date
- 2009
- 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.
- Subject
- graph isomorphism; factorization; linked chain; linked cycle
- Identifier
- http://hdl.handle.net/1959.13/916332
- Identifier
- uon:7962
- Identifier
- ISSN:0384-9864
- Language
- eng
- Reviewed
- Hits: 6319
- Visitors: 6244
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|