𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Normal Cayley Graphs and Hom-idempotent Graphs

✍ Scribed by Benoit Larose; François Laviolette; Claude Tardif

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
218 KB
Volume
19
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is said to be hom-idempotent if there is a homomorphism from G 2 to G, and weakly hom-idempotent if for some n ≥ 1 there is a homomorphism from G n+1 to G n . We characterize both classes of graphs in terms of a special class of Cayley graphs called normal Cayley graphs. This allows us to construct, for any integer n, a Cayley graph G such that G n+1 → G n → G n-1 , answering a question of Hahn, Hell and Poljak [8]. Also, we show that the Kneser graphs are not weakly hom-idempotent, generalizing a result of Albertson and Collins [1] for the Petersen graph.

📜 SIMILAR VOLUMES

Tetravalent half-edge-transitive graphs
Tetravalent half-edge-transitive graphs and non-normal Cayley graphs
✍ Xiuyun Wang; Yan-Quan Feng 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 206 KB

Let X be a vertex-transitive graph, that is, the automorphism group Aut(X ) of X is transitive on the vertex set of X . The graph X is said to be symmetric if Aut(X ) is transitive on the arc set of X . Suppose that Aut(X ) has two orbits of the same length on the arc set of X . Then X is said to be

Channel assignment on Cayley graphs
Channel assignment on Cayley graphs
✍ Patrick Bahls 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB

We address various channel assignment problems on the Cayley graphs of certain groups, computing the frequency spans by applying group theoretic techniques. In particular, we show that if G is the Cayley graph of an n-generated group with a certain kind of presentation, then (G; k, 1) ≤ 2(k +n-1). F

Isomorphic Cayley graphs on nonisomorphi
Isomorphic Cayley graphs on nonisomorphic groups
✍ Morris, Joy 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 349 KB

The issue of when two Cayley digraphs on different abelian groups of prime power order can be isomorphic is examined. This had previously been determined by Anne Joseph for squares of primes; her results are extended.

On Isomorphisms of Finite Cayley Graphs
On Isomorphisms of Finite Cayley Graphs
✍ M. Conder; C. Heng Li 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 148 KB

A Cayley graph Cay(G, S) of a group G is called a CI-graph if whenever T is another subset of G for which Cay(G, S) ∼ = Cay(G, T ), there exists an automorphism σ of G such that S σ = T . For a positive integer m, the group G is said to have the m-CI property if all Cayley graphs of G of valency m a

Large Cayley graphs and vertex-transitiv
Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
✍ Heather Macbeth; Jana Šiagiová; Jozef Širáň; Tomáš Vetrík 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract For any __d__⩾5 and __k__⩾3 we construct a family of Cayley graphs of degree __d__, diameter __k__, and order at least __k__((__d__−3)/3)^__k__^. By comparison with other available results in this area we show that our family gives the largest currently known Cayley graphs for a wide ra