Half-transitive graphs of valency 4 with prescribed attachment numbers

✍ Scribed by Maru?i?, Dragan; Waller, Adrian O.

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 134 KB
• Volume: 34
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(200005)34:1<89::aid-jgt8>3.0.co;2-k

✦ Synopsis

A graph X is said to be 1 2 -transitive if its automorphism group Aut X acts vertex-and edge-, but not arc-transitively on X. Then Aut X induces an orientation of the edges of X. If X has valency 4, then this orientation gives rise to so-called alternating cycles, that is even length cycles in X whose every other vertex is the head and every other vertex is the tail of its two incident edges in the above orientation. All alternating cycles have the same length 2r(X), where r(X) is the radius of X, and any two adjacent alternating cycles intersect in the same number of vertices, called the attachment number a(X) of X. All known examples of 1 2 -transitive graphs have attachment number 1, r or 2r, where r is the radius of the graph. In this article, we construct 1 2 -transitive graphs with all other possible attachment numbers. The case of attachment number 2 is dealt with in more detail.