|
|
A371396
|
|
Maximum number of vertices of a chordal ring graph with diameter n.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|