A363363 Number of connected unlabeled n-node graphs G that are not weakly pancyclic, i.e., there exists an integer k such that G contains a cycle that is longer than k and a cycle that is shorter than k but no cycle of length k.

0, 0, 0, 0, 0, 4, 26, 209, 1513, 12145

Offset

1,6

Links

Table of n, a(n) for n=1..10.

Stephan Brandt, Ralph Faudree, and Wayne Goddard, Weakly pancyclic graphs, Journal of Graph Theory 27 (1998), 141-176.

Formula

a(n) = A001349(n) - A363362(n).

a(n) = 0 for n <= 5, because all graphs on at most 5 nodes are weakly pancyclic.

Example

There are a(6) = 4 not weakly pancyclic graphs on 6 nodes (all of them connected):
  a cycle of length 6 with one additional edge (two different graphs);
  the complete bipartite graph K_{3,3} with one edge removed;
  K_{3,3}.

Crossrefs

Cf. A001349, A363362, A363364.

Sequence in context: A369511 A228966 A291533 * A239295 A274735 A355379

Adjacent sequences: A363360 A363361 A363362 * A363364 A363365 A363366

Keyword

nonn,more

Author

Pontus von Brömssen, May 29 2023

Status

approved