A048192 -id:A048192 - cp's OEIS frontend

A243796 Number of graphs with n nodes that are chordal and Hamiltonian.

1, 0, 1, 2, 4, 15, 58, 360, 2793, 28761, 369545, 5914974, 116089531, 2816695796

Offset: 1

Travis Hoppe and Anna Petrone, Jun 27 2014

We generated all biconnected chordal graphs up to 14 vertices using Brendan McKay's Nauty Software and Algorithms, then used a program we wrote to identify Hamiltonian graphs. - Philip Nelson, Ammon Hepworth, Raul A. Ramirez, Dec 16 2017

Ammon Hepworth, Philip Nelson, and Raul Ramirez, Hamiltonian Cycles
Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version a1db88e
Brendan McKay's Nauty Software and Algorithms, nauty and Traces

Cf. A048192 (chordal graphs), A003216 (Hamiltonian graphs).

a(11) added using tinygraph by Falk Hüffner, Aug 15 2017

a(12)-a(14) from Philip Nelson, Dec 16 2017

A243797 Number of graphs with n nodes that are chordal and do not have a bowtie as a subgraph.

Original entry on oeis.org

1, 1, 2, 5, 10, 27, 70, 206, 613, 1942, 6259, 20840, 70528, 243276, 850281

Offset: 1

Travis Hoppe and Anna Petrone, Jun 27 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version e8699da

Cf. A048192 (chordal graphs), A242792 (bowtie free graphs).

a(11)-a(15) added using tinygraph by Falk Hüffner, Jan 17 2016

A243798 Number of connected graphs with n nodes that are chordal and have no subgraph isomorphic to the bull graph.

Original entry on oeis.org

1, 1, 2, 5, 6, 12, 25, 55, 126, 304, 745, 1893, 4893, 12916, 34562, 93844

Offset: 1

Travis Hoppe and Anna Petrone, Jun 27 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644, 2014
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 6c1dbe4

Cf. A048192 (chordal graphs), A244427 (no bull subgraphs).

Definition corrected (connected only) by Falk Hüffner, Jul 01 2018

a(11)-a(16) added using tinygraph by Falk Hüffner, Jul 01 2018

A243799 Number of connected graphs with n nodes that are chordal and are open-bowtie free.

Original entry on oeis.org

1, 1, 2, 5, 6, 13, 25, 58, 130, 316, 769, 1962, 5052, 13342, 35629, 96671

Offset: 1

Travis Hoppe and Anna Petrone, Jun 27 2014

The open bowtie graph is also known as a cricket. - Falk Hüffner, Jul 01 2018

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
F. Hüffner, tinygraph, Software for generating integer sequences based on graph properties, version 6c1dbe4.

Cf. A048192 (chordal graphs), A242791 (open-bowtie free graphs).

Definition corrected (connected only) by Falk Hüffner, Jul 01 2018

a(11)-a(16) added using tinygraph by Falk Hüffner, Jul 01 2018

A348365 Number of connected realizable graphs on n vertices.

Original entry on oeis.org

1, 1, 2, 5, 15, 58, 265

Offset: 1

Pierre-Louis Giscard, Oct 15 2021

a(n) is the number of realizable connected unlabelled graphs on n vertices. A realizable graph H is a graph for which there exists a (multi di)graph G such that the vertices of H are exactly the simple cycles of G and two vertices of H share an edge if the corresponding simple cycles in G share at least one vertex. Thus H encodes the "cycle skeleton" of G. Formally, H is the dependency graph of the trace monoid formed by the simple cycles on G equipped with the independency relation that two cycles commute if they are vertex-disjoint.

			For n = 4, a(4) = 5 because out of the 6 unlabelled connected graphs on 4 vertices only 1 is not realizable: the square.

Jean Fromentin, Pierre-Louis Giscard and Théo Karaboghossian, Why walks lead us astray in the study of graphs, arXiv:2110.15618 [math.CO], 2021.
Théo Karaboghossian, Pierre-Louis Giscard and Jean Fromentin, Trace monoids, hike monoids and number theory, slides, WACA (Calais, France 2021).

Compare with A001349 (all graphs), sequence close to A048192.

a(n) is strictly increasing, a(n+1)>a(n) and a(n) grows at least exponentially with n as n->infinity.

A367448 Number of chordal graphs on n vertices with a fixed perfect elimination ordering (e.g., 1,2,3,...,n).

Original entry on oeis.org

1, 2, 7, 39, 324, 3839, 62973, 1402792, 41946319, 1673580047, 88922215948, 6297931501377, 596303138919753, 75787556639822258, 12991109500044250083, 3018313885461813882295, 955168488432838276254520, 413639698066068492610331231, 246197679553110860511406200613, 202212713843977008653180874488520

Offset: 1

Manfred Scheucher and Robert Lauff, Jan 05 2024

nonn

a(n) is the number of sign mappings X:([n] choose 2) -> {+,-} such that for any ordered 3-tuple a

Cf. A048192.

a(n)={
  local(M=Map(Mat([1, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(proc(p,m)=for(k=0, poldegree(p), acc(p + x*(1 + x)^k, polcoef(p,k)*m)));
  for(r=1, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], proc(src[i, 1], src[i, 2])));
  vecsum(Mat(M)[,2])
} \\ Andrew Howroyd, Jan 06 2024

Terms a(12) and beyond from Andrew Howroyd, Jan 06 2024

Previous Showing 11-16 of 16 results.

cp's OEIS Frontend

A243796 Number of graphs with n nodes that are chordal and Hamiltonian.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A243797 Number of graphs with n nodes that are chordal and do not have a bowtie as a subgraph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A243798 Number of connected graphs with n nodes that are chordal and have no subgraph isomorphic to the bull graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A243799 Number of connected graphs with n nodes that are chordal and are open-bowtie free.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A348365 Number of connected realizable graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A367448 Number of chordal graphs on n vertices with a fixed perfect elimination ordering (e.g., 1,2,3,...,n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions