A371396 Maximum number of vertices of a chordal ring graph with diameter n.

6, 14, 20, 38, 48, 74, 88, 122, 140, 182, 204, 254, 280, 338, 368, 434, 468, 542, 580, 662, 704, 794, 840, 938, 988, 1094, 1148, 1262, 1320, 1442, 1504, 1634, 1700, 1838, 1908, 2054, 2128, 2282, 2360, 2522, 2604, 2774, 2860, 3038, 3120, 3314, 3408, 3602, 3700, 3902, 4004, 4214, 4320, 4538, 4648

Offset

2,1

Comments

Given integers N (even) and c (odd) the chordal ring graph CR(N,c) is a bipartite graph with vertex set Z_N, and edges {i,i+1}, {i,i-1}, {i,i+c} if i is odd, and {i,i-c} if i is even.

If the conjecture below holds, then a(n) = 2*A309805(n) for n >= 3.

References

P. Morillo, F. Comellas, and M. A. Fiol, The optimization of chordal ring networks, Communication Technology, Eds. Q. Yasheng and W Xiuying, World Scientific,1987, pages 295--299.

Links

Table of n, a(n) for n=2..56.

B. W. Arden and H. Lee, Analysis of chordal ring networks, IEEE Trans. Comput. C-30 (1981), 291-295.

M. A. Reyes, C. Dalfó, and M. A. Fiol, Structural and Spectral Properties of Chordal Ring, Multi-ring and Mixed Graphs, arXiv:2409.00520 [math.CO2024], 2024 [See Table 6, p. 21]. Also in Symmetry 16 (2024), no. 9, 1135.

J. L. A. Yebra, M. A. Fiol, P. Morillo, and I. Alegre, The diameter of undirected graphs associated to plane tessellations, Ars Combin. 20-B (1985), 159-171.

Formula

a(n) = (3*n^2+1)/2 if n is odd.

Conjecture: a(n) = (3/2)*n^2 - n if n is even and n > 2.

Example

For diameter n=3 the maximum number of vertices a(3)=14 is attained by the Heawood graph.

Crossrefs

Cf. A309805.

Sequence in context: A236928 A064708 A064709 * A118129 A046712 A162823

Adjacent sequences: A371393 A371394 A371395 * A371397 A371398 A371399

Keyword

nonn

Author

Miquel A. Fiol, Mar 21 2024

Status

approved