A185959 -id:A185959

A006799

Number of vertex-transitive graphs with n nodes.
(Formerly M0302)

+10
10

1, 2, 2, 4, 3, 8, 4, 14, 9, 22, 8, 74, 14, 56, 48, 286, 36, 380, 60, 1214, 240, 816, 188, 15506, 464, 4236, 1434, 25850, 1182, 46308, 2192, 677402, 6768, 132580, 11150, 1963202, 14602, 814216, 48462, 13104170, 52488, 9462226, 99880, 39134640, 399420, 34333800, 364724

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

REFERENCES

CRC Handbook of Combinatorial Designs, 1996, p. 649.

Brendan McKay, personal communication.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Table of n, a(n) for n=1..47.

Nino Bašić, Martin Knor, and Riste Škrekovski, On regular graphs with Šoltés vertices, arXiv:2303.11996 [math.CO], 2023.

Derek Holt and Gordon Royle, A Census of Small Transitive Groups and Vertex-Transitive Graphs, arXiv:1811.09015 [math.CO], 2018.

B. D. McKay and G. F. Royle, The transitive graphs with at most 26 vertices, Ars Combin. 30 (1990), 161-176. (Annotated scanned copy)

Brendan D. McKay, Gordon F. Royle, The transitive graphs with at most 26 vertices, Ars Combin. 30 (1990), 161-176.

G. Royle, Transitive graphs

Steven Skiena, A Database of Graphs in Combinatorica Format.

Eric Weisstein's World of Mathematics, Vertex-Transitive Graph

Eric Weisstein's World of Mathematics, Cayley Graph

FORMULA

Inverse Moebius transform of A006800. - Andrew Howroyd, Sep 18 2018

CROSSREFS

Row sums of A319367.

Cf. A006792, A006793, A006800, A185959.

KEYWORD

nonn,nice,hard

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Jun 30 2007

a(32)-a(47) from Danny Rorabaugh, Nov 26 2018

STATUS

approved

A006792

Number of n-node vertex-transitive graphs which are not Cayley graphs.
(Formerly M0009)

+10
6

2, 0, 0, 0, 0, 4, 8, 0, 4, 0, 82, 0, 0, 0, 112, 0, 132, 0, 66, 0, 1124, 0, 18170, 0, 920, 6, 4162, 0, 0, 0, 48266, 0, 242, 0, 96, 294, 0, 0

(list; graph; refs; listen; history; text; internal format)

OFFSET

10,1

REFERENCES

McKay, Brendan D.; Royle, Gordon F.; The transitive graphs with at most 26 vertices. Ars Combin. 30 (1990), 161-176.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Table of n, a(n) for n=10..47.

B. McKay, Email to N. J. A. Sloane, Jul. 1991

Brendan D. McKay, Cheryl E. Praeger, Vertex-transitive graphs which are not Cayley graphs, I. J. Austral. Math. Soc. Ser. A 56 (1994), no. 1, 53-63.

G. Royle, Transitive graphs

Steven Skiena, A Database of Graphs in Combinatorica Format.

Eric Weisstein's World of Mathematics, Noncayley Graph

FORMULA

a(n) = A006799(n) - A185959(n). - Andrew Howroyd, Nov 27 2018

CROSSREFS

Cf. A006799, A185959.

KEYWORD

nonn,more

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Jun 30 2007

a(32)-a(47) from Andrew Howroyd, Nov 27 2018

Duplicate a(32) removed by Andrew Howroyd, Sep 05 2019

STATUS

approved

A319372

Triangle read by rows: T(n,k) is the number of Cayley graphs with n nodes and valency k, (0 <= k < n).

+10
4

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 2, 2, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 2, 3, 3, 2, 1, 1, 1, 0, 2, 0, 3, 0, 2, 0, 1, 1, 1, 2, 2, 4, 4, 2, 2, 1, 1, 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 1, 1, 4, 7, 11, 13, 13, 11, 7, 4, 1, 1, 1, 0, 1, 0, 3, 0, 4, 0, 3, 0, 1, 0, 1

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,18

COMMENTS

First differs from A319367 in row 10.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..496

Gordon Royle, Transitive Graphs

Eric Weisstein's World of Mathematics, Cayley Graph

Wikipedia, Cayley graph

EXAMPLE

Triangle begins, n >= 1, 0 <= k < n:

1;

1, 1;

1, 0, 1;

1, 1, 1, 1;

1, 0, 1, 0, 1;

1, 1, 2, 2, 1, 1;

1, 0, 1, 0, 1, 0, 1;

1, 1, 2, 3, 3, 2, 1, 1;

1, 0, 2, 0, 3, 0, 2, 0, 1;

1, 1, 2, 2, 4, 4, 2, 2, 1, 1;

1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1;

1, 1, 4, 7, 11, 13, 13, 11, 7, 4, 1, 1;

1, 0, 1, 0, 3, 0, 4, 0, 3, 0, 1, 0, 1;

1, 1, 2, 3, 6, 6, 9, 9, 6, 6, 3, 2, 1, 1;

1, 0, 3, 0, 7, 0, 11, 0, 11, 0, 7, 0, 3, 0, 1;

1, 1, 3, 7, 15, 26, 39, 47, 47, 39, 26, 15, 7, 3, 1, 1;

1, 0, 1, 0, 4, 0, 7, 0, 10, 0, 7, 0, 4, 0, 1, 0, 1;

1, 1, 4, 7, 16, 23, 38, 45, 53, 53, 45, 38, 23, 16, 7, 4, 1, 1;

...

CROSSREFS

Column k=3 is aerated A319374.

Row sums are A185959.

Cf. A319367, A319368.

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Sep 17 2018

STATUS

approved

A241164

Number of 2n-vertex connected cubic vertex-transitive graphs which are Cayley graphs.

+10
2

1, 2, 2, 2, 4, 3, 4, 5, 5, 3, 11, 4, 5, 7, 10, 4, 12, 5, 10, 10, 7, 5, 32, 8, 9, 13, 13, 6, 30, 7, 26, 11, 11, 11, 36, 8, 11, 14, 29, 8, 27, 9, 16, 18, 13, 9, 90, 13, 23, 15, 20, 10, 41, 19, 35, 18, 17, 11, 100, 12, 17, 26, 82, 17, 35, 13

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,2

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 2..640, based on the work of Primož Potočnik, Pablo Spiga and Gabriel Verret

Primož Potočnik, Pablo Spiga and Gabriel Verret, A census of small connected cubic vertex-transitive graphs (see the sub-page Table.html)

G. Royle, Cubic transitive graphs

CROSSREFS

Cf. A032355, A185959.

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Apr 19 2014

STATUS

approved

A330697

Numbers k such that every vertex-transitive graph of order k is a Cayley-graph.

+10
2

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 17, 19, 21, 22, 23, 25, 27, 29, 31, 33, 37, 38, 39, 41, 43, 46, 47, 49, 53, 55, 59, 61, 62, 67, 69, 71, 73, 79, 83, 86, 87, 89, 93, 94, 95, 97, 101, 103, 107, 109, 113, 115, 118, 121, 123, 125, 127, 129, 131, 133, 134, 137, 139

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Numbers k for which A185959(k) = A006799(k).

Numbers k for which A006792(k) = 0.

In the Farrokhi reference, a Cayley number is a number k such that all vertex transitive graphs of order k are Cayley graphs.

LINKS

Table of n, a(n) for n=1..66.

M. Farrokhi D. G., List of known Cayley numbers less than or equal to 1000000

M. Farrokhi D. G., Cayley numbers

M. Farrokhi D. G., Cayley numbers (GitHub)

PROG

(GAP) # See M. Farrokhi Github repository for a GAP program.

CROSSREFS

Cf. A006792, A006799, A185959, A330698.

KEYWORD

nonn

AUTHOR

M. Farrokhi D. G., Dec 26 2019

STATUS

approved

A330698

Numbers k such that there exists a non-Cayley vertex-transitive graph of order k.

+10
2

10, 15, 16, 18, 20, 24, 26, 28, 30, 32, 34, 35, 36, 40, 42, 44, 45, 48, 50, 51, 52, 54, 56, 57, 58, 60, 63, 64, 65, 66, 68, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 88, 90, 91, 92, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112, 114, 116, 117, 119, 120, 122, 124

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

Numbers k for which A185959(k) < A006799(k).

Numbers k for which A006792(k) <> 0.

In the Farrokhi reference, a Cayley number is a number k such that all vertex transitive graphs of order k are Cayley graphs.

LINKS

Table of n, a(n) for n=1..66.

M. Farrokhi D. G., List of known non-Cayley numbers less than or equal to 1000000

M. Farrokhi D. G., Cayley numbers

M. Farrokhi D. G., Cayley numbers (GitHub)