A363363 -id:A363363 - cp's OEIS frontend

A363362 Number of connected weakly pancyclic graphs on n unlabeled nodes.

1, 1, 2, 6, 21, 108, 827, 10908, 259567, 11704426

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. The concept of weak pancyclicity was introduced by Brandt, Faudree, and Goddard (1998).

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

Cf. A001349, A286684, A363363, A363364.

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

a(n) = A001349(n) 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

A363362 Number of connected weakly pancyclic graphs on n unlabeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula