login
A371396
Maximum number of vertices of a chordal ring graph with diameter n.
3
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
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
KEYWORD
nonn
AUTHOR
Miquel A. Fiol, Mar 21 2024
STATUS
approved