A296524 - OEIS

A296524

Number of connected (2*k)-regular graphs on 2*n+1 nodes with maximal diameter D(n,k) A294733 written as triangular array T(n,k), 1 <= k <= n.

1, 1, 1, 1, 2, 1, 1, 16, 4, 1, 1, 1, 266, 6, 1, 1, 5, 367860, 10786, 10, 1, 1, 19, 1

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

OFFSET

1,5

COMMENTS

The next term a(24) corresponding to the 6-regular graphs on 15 nodes is conjectured to be 1. It seems that there exists only one graph with diameter A294733(24)=4. Its adjacency matrix is

1 2 3 4 5 6 7 8 9 0 1 2 3 4 5

1 . 1 1 1 1 1 1 . . . . . . . .

2 1 . 1 1 1 1 1 . . . . . . . .

3 1 1 . 1 1 1 1 . . . . . . . .

4 1 1 1 . 1 1 1 . . . . . . . .

5 1 1 1 1 . 1 1 . . . . . . . .

6 1 1 1 1 1 . . 1 . . . . . . .

7 1 1 1 1 1 . . 1 . . . . . . .

8 . . . . . 1 1 . 1 1 1 1 . . .

9 . . . . . . . 1 . 1 1 . 1 1 1

10 . . . . . . . 1 1 . . 1 1 1 1

11 . . . . . . . 1 1 . . 1 1 1 1

12 . . . . . . . 1 . 1 1 . 1 1 1

13 . . . . . . . . 1 1 1 1 . 1 1

14 . . . . . . . . 1 1 1 1 1 . 1

15 . . . . . . . . 1 1 1 1 1 1 .

The distance of 4 is achieved between nodes 1 and 13. None of the remaining 1470293674 graphs seems to have a diameter > 3.

The conjecture is confirmed using Markus Meringer's GenReg program. Aside from the 1 shown 6-regular graph on 15 nodes with diameter 4 there are 870618932 graphs with diameter 2 and 599674742 graphs with diameter 3. - Hugo Pfoertner, Dec 19 2017

REFERENCES

For references see A294733.

LINKS

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

M. Meringer, GenReg, Generation of regular graphs.

EXAMPLE

Degree r

2 4 6 8 10 12 14 16

n --------------------------------------

3 | 1 Diameter A294733

| 1 Number of graphs with this diameter (this sequence)

5 | 2 1

| 1 1

7 | 3 2 1

| 1 2 1

9 | 4 2 2 1

| 1 16 4 1

11 | 5 4 2 2 1

| 1 1 266 6 1

13 | 6 5 2 2 2 1

| 1 5 367860 10786 10 1

15 | 7 6 4 2 2 2 1

| 1 19 1 ? ? 17 1

17 | 8 7 >=4 2 2 2 2 1

| 1 33 ? ? ? ? 25 1

a(12)=1 corresponds to the only 4-regular graph on 11 nodes with diameter 4.

Its adjacency matrix is

1 2 3 4 5 6 7 8 9 0 1

1 . 1 1 1 1 . . . . . .

2 1 . 1 1 1 . . . . . .

3 1 1 . 1 1 . . . . . .

4 1 1 1 . . 1 . . . . .

5 1 1 1 . . 1 . . . . .

6 . . . 1 1 . 1 1 . . .

7 . . . . . 1 . . 1 1 1

8 . . . . . 1 . . 1 1 1

9 . . . . . . 1 1 . 1 1

10 . . . . . . 1 1 1 . 1

11 . . . . . . 1 1 1 1 .

A shortest walk along 4 edges is required to reach node 9 from node 1.

All others of the A068934(60)=265 4-regular graphs on 11 nodes have smaller diameters, i.e., 37 with diameter 2 and 227 with diameter 3.

CROSSREFS

Cf. A068934, A294733, A296525, A296526, A296620.

Sequence in context: A132318 A078089 A095836 * A303935 A156697 A173504

Adjacent sequences: A296521 A296522 A296523 * A296525 A296526 A296527

KEYWORD

nonn,tabl,hard,more

AUTHOR

Hugo Pfoertner, Dec 14 2017

STATUS

approved