[go: up one dir, main page]
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a326207 -id:a326207
Displaying 1-5 of 5 results found. page 1
     Sort: relevance | references | number | modified | created      Format: long | short | data
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
Table of n, a(n) for n=1..13.
Jan Goedgebeur, Barbara Meersman, Carol T. Zamfirescu, Graphs with few Hamiltonian Cycles, arXiv:1812.05650 [math.CO], 2018.
Eric Weisstein's World of Mathematics, Nonhamiltonian Graph
Wikipedia, Hamiltonian path
FORMULA
a(n) = A000088(n) - A003216(n).
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]];
a[n_] := A000088[[n + 1]] - A003216[[n]];
a /@ Range[13] (* Jean-François Alcover, Jan 02 2020 *)
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).
The labeled case is A326207.
The directed case is A326223 (with loops) or A326222 (without loops).
Unlabeled simple graphs not containing a Hamiltonian path are A283420.
Cf. A006125, A057864, A326205, A326206.
KEYWORD
nonn,more
AUTHOR
Eric W. Weisstein, Aug 26 2014
EXTENSIONS
a(12) from formula by Falk Hüffner, Aug 13 2017
a(13) added by Jan Goedgebeur, May 07 2019
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
Table of n, a(n) for n=0..11.
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 9766535.
Wikipedia, Hamiltonian path
Gus Wiseman, The a(5) = 218 simple graphs containing a Hamiltonian cycle.
FORMULA
A006125(n) = a(n) + A326207(n).
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], FindHamiltonianCycle[Graph[Range[n], #]]!={}&]], {n, 0, 4}] (* Mathematica 8.0+ *)
CROSSREFS
The unlabeled version is A003216.
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.
Cf. A003216, A006125, A057864, A283420.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Jun 15 2019
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
Table of n, a(n) for n=0..11.
Wikipedia, Hamiltonian path
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
Gus Wiseman, The a(4) = 30 simple graphs not containing a Hamiltonian path.
FORMULA
A006125(n) = a(n) + A326206(n).
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], FindHamiltonianPath[Graph[Range[n], #]]=={}&]], {n, 0, 4}] (* Mathematica 10.2+ *)
CROSSREFS
The unlabeled case is A283420.
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.
Cf. A003216, A006125, A057864.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Jun 14 2019
EXTENSIONS
a(7)-a(11) added from formula by Falk Hüffner, Jun 21 2019
STATUS
approved
A326220 Number of non-Hamiltonian labeled n-vertex digraphs (with loops). +10
8
1, 0, 12, 392, 46432, 20023232, 30595305216 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.
LINKS
Table of n, a(n) for n=0..6.
Wikipedia, Hamiltonian path
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 unlabeled case is A326223.
The undirected case is A326239 (with loops) or A326207 (without loops).
The case without loops is A326218.
Digraphs (with loops) containing a Hamiltonian cycle are A326204.
Digraphs (with loops) not containing a Hamiltonian path are A326213.
Cf. A000595, A002416, A003024, A003216, A246446, A326208, A326219, A326222, A326224.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Jun 15 2019
EXTENSIONS
a(5)-a(6) from Bert Dobbelaere, Jun 11 2024
STATUS
approved
A326218 Number of non-Hamiltonian labeled n-vertex digraphs (without loops). +10
7
1, 0, 3, 49, 2902 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.
LINKS
Table of n, a(n) for n=0..4.
Wikipedia, Hamiltonian path
FORMULA
A053763(n) = a(n) + A326219(n).
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
The unlabeled case is A326222.
The undirected case is A326207.
The case with loops is A326220.
Digraphs (without loops) containing a Hamiltonian cycle are A326219.
Digraphs (without loops) not containing a Hamiltonian path are A326216.
Cf. A000595, A002416, A003024, A003216, A246446, A326204, A326213, A326223, A326225.
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Jun 15 2019
STATUS
approved
page 1

Search completed in 0.005 seconds

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 31 21:24 EDT 2024. Contains 375573 sequences. (Running on oeis4.)