A371396 - OEIS

%I #36 Sep 30 2024 09:14:49

%S 6,14,20,38,48,74,88,122,140,182,204,254,280,338,368,434,468,542,580,

%T 662,704,794,840,938,988,1094,1148,1262,1320,1442,1504,1634,1700,1838,

%U 1908,2054,2128,2282,2360,2522,2604,2774,2860,3038,3120,3314,3408,3602,3700,3902,4004,4214,4320,4538,4648

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

%C 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.

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

%D 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.

%H B. W. Arden and H. Lee, <a href="https://doi-org.recursos.biblioteca.upc.edu/10.1109/TC.1981.1675777">Analysis of chordal ring networks</a>, IEEE Trans. Comput. C-30 (1981), 291-295.

%H M. A. Reyes, C. Dalfó, and M. A. Fiol, <a href="https://doi.org/10.48550/arXiv.2409.00520">Structural and Spectral Properties of Chordal Ring, Multi-ring and Mixed Graphs</a>, arXiv:2409.00520 [math.CO2024], 2024 [See Table 6, p. 21]. Also in <a href="https://doi.org/10.3390/sym16091135">Symmetry</a> 16 (2024), no. 9, 1135.

%H J. L. A. Yebra, M. A. Fiol, P. Morillo, and I. Alegre, <a href="https://upcommons.upc.edu/handle/2117/12662">The diameter of undirected graphs associated to plane tessellations</a>, Ars Combin. 20-B (1985), 159-171.

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

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

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

%Y Cf. A309805.

%K nonn

%O 2,1

%A _Miquel A. Fiol_, Mar 21 2024