Search: a326207 -id:a326207
|
|
A246446
|
|
Number of nonhamiltonian graphs with n nodes.
|
|
+10
12
|
|
|
0, 2, 3, 8, 26, 108, 661, 6150, 97585, 2700050, 135841840, 12568984762, 2179513027405
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
A000088 = Cases[Import["https://oeis.org/A000088/b000088.txt", "Table"], {_, _}][[All, 2]];
A003216 = Cases[Import["https://oeis.org/A003216/b003216.txt", "Table"], {_, _}][[All, 2]];
|
|
CROSSREFS
|
Cf. A000088 (number of simple graphs on n nodes).
Cf. A003216 (number of Hamiltonian graphs on n nodes).
Cf. A126149 (number of connected nonhamiltonian graphs on n nodes).
Unlabeled simple graphs not containing a Hamiltonian path are A283420.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A326208
|
|
Number of Hamiltonian labeled simple graphs with n vertices.
|
|
+10
10
|
|
|
0, 1, 0, 1, 10, 218, 10078, 896756, 151676112, 47754337568, 28229412456056, 31665593711174080
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
A graph is Hamiltonian if it contains a cycle passing through every vertex exactly once.
|
|
LINKS
|
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 9766535.
|
|
FORMULA
|
|
|
MATHEMATICA
|
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], FindHamiltonianCycle[Graph[Range[n], #]]!={}&]], {n, 0, 4}] (* Mathematica 8.0+ *)
|
|
CROSSREFS
|
The directed version is A326204 (with loops) or A326219 (without loops).
Simple graphs not containing a Hamiltonian cycle are A326207.
Simple graphs containing a Hamiltonian path are A326206.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(7)-a(11) added using tinygraph by Falk Hüffner, Jun 21 2019
|
|
STATUS
|
approved
|
|
|
|
|
A326205
|
|
Number of n-vertex labeled simple graphs not containing a Hamiltonian path.
|
|
+10
8
|
|
|
1, 1, 1, 4, 30, 391, 9400, 398140, 30500696, 4161339596, 1058339281896, 515295969951016
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
A path is Hamiltonian if it passes through every vertex exactly once.
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], FindHamiltonianPath[Graph[Range[n], #]]=={}&]], {n, 0, 4}] (* Mathematica 10.2+ *)
|
|
CROSSREFS
|
The case for digraphs is A326213 (without loops) or A326216 (with loops).
Simple graphs with a Hamiltonian path are A326206.
Simple graphs without a Hamiltonian cycle are A326207.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A326220
|
|
Number of non-Hamiltonian labeled n-vertex digraphs (with loops).
|
|
+10
8
|
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(2) = 12 digraph edge-sets:
{} {11} {11,12} {11,12,22}
{12} {11,21} {11,21,22}
{21} {11,22}
{22} {12,22}
{21,22}
|
|
MATHEMATICA
|
Table[Length[Select[Subsets[Tuples[Range[n], 2]], FindHamiltonianCycle[Graph[Range[n], DirectedEdge@@@#]]=={}&]], {n, 4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 46336 which is incorrect *)
|
|
CROSSREFS
|
The undirected case is A326239 (with loops) or A326207 (without loops).
Digraphs (with loops) containing a Hamiltonian cycle are A326204.
Digraphs (with loops) not containing a Hamiltonian path are A326213.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A326218
|
|
Number of non-Hamiltonian labeled n-vertex digraphs (without loops).
|
|
+10
7
|
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
The a(3) = 49 edge-sets:
{} {12} {12,13} {12,13,21} {12,13,21,23}
{13} {12,21} {12,13,23} {12,13,21,31}
{21} {12,23} {12,13,31} {12,13,23,32}
{23} {12,31} {12,13,32} {12,13,31,32}
{31} {12,32} {12,21,23} {12,21,23,32}
{32} {13,21} {12,21,31} {12,21,31,32}
{13,23} {12,21,32} {13,21,23,31}
{13,31} {12,23,32} {13,23,31,32}
{13,32} {12,31,32} {21,23,31,32}
{21,23} {13,21,23}
{21,31} {13,21,31}
{21,32} {13,23,31}
{23,31} {13,23,32}
{23,32} {13,31,32}
{31,32} {21,23,31}
{21,23,32}
{21,31,32}
{23,31,32}
|
|
MATHEMATICA
|
Table[Length[Select[Subsets[Select[Tuples[Range[n], 2], UnsameQ@@#&]], FindHamiltonianCycle[Graph[Range[n], DirectedEdge@@@#]]=={}&]], {n, 4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 2896 which is incorrect *)
|
|
CROSSREFS
|
Digraphs (without loops) containing a Hamiltonian cycle are A326219.
Digraphs (without loops) not containing a Hamiltonian path are A326216.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.005 seconds
|