𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter

✍ Scribed by Heather Macbeth; Jana Šiagiová; Jozef Širáň; Tomáš Vetrík

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
128 KB
Volume
64
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 range of sufficiently large degrees and diameters. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 87–98, 2010

📜 SIMILAR VOLUMES

On cubic non-Cayley vertex-transitive gr
On cubic non-Cayley vertex-transitive graphs
✍ Klavdija Kutnar,; Dragan Marušič;; Cui Zhang 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract In 1983, the second author [D. Marušič, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers __n__ there exists a non‐Cayley vertex‐transitive graph on __n__ vertices. (The term __non‐Cayley numbers__ has later been given to such integers.) Motivated by this problem,

Small vertex-transitive and Cayley graph
Small vertex-transitive and Cayley graphs of girth six and given degree: an algebraic approach
✍ Eyal Loz; Martin Mačaj; Mirka Miller; Jana Šiagiová; Jozef Širáň; Jana Tomanová 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB

We examine the existing constructions of the smallest known vertex-transitive graphs of a given degree and girth 6. It turns out that most of these graphs can be described in terms of regular lifts of suitable quotient graphs. A further outcome of our analysis is a precise identification of which of

Vertex-transitive graphs that are not Ca
Vertex-transitive graphs that are not Cayley graphs. II
✍ McKay, Brendan D.; Praeger, Cheryl E. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 881 KB

The Petersen graph on 10 vertices is the smallest example of a vertex-transitive graph that is not a Cayley graph. In 1983, D. MaruSiE asked, "For what values of n does there exist such a graph on n vertices?" We give several new constructions of families of vertex-transitive graphs that are not Cay

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

On Non-Cayley Vertex-Transitive Graphs o
On Non-Cayley Vertex-Transitive Graphs of Order a Product of Three Primes
✍ Mohammad A. Iranmanesh; Cheryl E. Praeger 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 192 KB

This paper completes the determination of all integers of the form pqr (where p, q, and r are distinct primes) for which there exists a vertex-transitive graph on pqr vertices which is not a Cayley graph.