A308568 Number of simple graphs on n vertices with bandwidth equal to diameter-based lower bound.

1, 2, 6, 14, 84, 286, 7266, 63191

Offset

2,2

Comments

Number of graphs for which the inequality bw(G) >= ceiling((n-1)/diameter(G)) holds with equality.

Equality holds for all nontrivial simple connected graphs on <= 4 nodes, so a(n) = A001349(n) for n = 2, 3, 4.

Links

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

Eric Weisstein's World of Mathematics, Graph Bandwidth

Eric Weisstein's World of Mathematics, Graph Diameter

Example

14 of the 21 graphs on 5 nodes satisfy the inequality with equality, the exceptions being K_2,3, K_1,1,3, K_1,1,1,2, W_5, the house X graph, the (4,1)-lollipop graph, and one other.

Crossrefs

Sequence in context: A055691 A072171 A371008 * A296054 A333121 A131518

Adjacent sequences: A308565 A308566 A308567 * A308569 A308570 A308571

Keyword

nonn,more

Author

Eric W. Weisstein, Jun 11 2019

Status

approved