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

Author

Miquel A. Fiol, Mar 21 2024

Keywords

• nonn

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.

Examples

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

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

• 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.

Crossrefs

Cf. A309805.

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.