A363362 -id:A363362 - cp's OEIS frontend

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

Pontus von Brömssen, May 29 2023

			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}.

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

Cf. A001349, A363362, A363364.

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

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

A363364 Least nonnegative integer k such that all non-bipartite graphs with n nodes and at least k edges are weakly pancyclic.

Original entry on oeis.org

0, 0, 0, 0, 0, 8, 11, 14, 17, 20

Offset: 1

Pontus von Brömssen, May 29 2023

A graph is weakly pancyclic if it contains cycles of all lengths between its girth and its circumference. Acyclic graphs are considered to be weakly pancyclic.
All graphs on at most 5 nodes are weakly pancyclic, so a(n) = 0 when n <= 5.
Brandt (1997) conjectures that a(n) = floor((n-1)*(n-3)/4) + 5 for n >= 6. The conjecture is false for n = 8, since there exists a (unique) non-bipartite, not weakly pancyclic graph (shown below) with 8 nodes and 13 edges, showing that a(8) >= 14. This graph contains cycles of lengths 3, 4, 5, 6, and 8, but none of length 7.
         O
        /|\
       / O \
      /  |  \
     /   O   \
    /  /   \  \
   / /       \ \
  //           \\
  O ----------- O
  \\           //
   \ \       / /
    \  \   /  /
     \   O   /
      \  |  /
       \ O /
        \|/
         O

Béla Bollobás and Andrew Thomason, Weakly pancyclic graphs, Journal of Combinatorial Theory Series B 77 (1999), 121-137.
Stephan Brandt, A sufficient condition for all short cycles, Discrete Applied Mathematics 79 (1997), 63-66.

Cf. A028309, A290743, A363362, A363363.

a(n) >= floor((n-1)*(n-3)/4) + 5 = A028309(n-1) + 2 for n >= 6 (Brandt, 1997).
a(n) <= floor((n-1)^2/4) + 2 = A290743(n-1) (Brandt, 1997).
a(n) <= floor(n^2/4) - n + 59 (Bollobás and Thomason, 1999).

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A363364 Least nonnegative integer k such that all non-bipartite graphs with n nodes and at least k edges are weakly pancyclic.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula