The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A331554 Number of simple graphs on n vertices up to homotopy equivalence. 0
 1, 1, 2, 4, 8, 15, 27, 46, 77, 126, 204, 325, 515, 806, 1252, 1929, 2953, 4486, 6778, 10176, 15200, 22583, 33394, 49143, 72019, 105089, 152746, 221159, 319070, 458697, 657256 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS Two graphs are homotopy equivalent if their images under embeddings are homotopy equivalent in the usual topological sense. LINKS Table of n, a(n) for n=0..30. EXAMPLE For n=4, the following 8 edge sets represent the 8 distinct homotopy equivalence classes: E1={}; E2={{1,2}}; E3={{1,2},{2,3}}; E4={{1,2},{2,3},{1,3}}; E5={{1,2},{2,3},{3,4}}; E6={{1,2},{2,3},{1,3},{3,4}}; E7={{1,2},{2,3},{1,3},{2,4},{3,4}}; E8={{1,2},{2,3},{1,3},{1,4},{2,4},{3,4}}; To demonstrate that this equivalence relation is weaker than both graph isomorphism and graph homeomorphism, consider the following 4 graphs on the 6 vertices {1,2,3,4,5,6}: G1={{1,2},{1,6},{2,4},{3,4},{3,5},{3,6},{5,6}}; G2={{1,2},{1,3},{2,4},{3,5},{4,5},{4,6},{5,6}}; G3={{1,2},{1,3},{2,4},{3,4},{3,5},{4,6},{5,6}}; G4={{1,2},{1,6},{2,4},{2,6},{3,5},{4,6},{5,6}}; G1 is isomorphic to G2. G3 is homeomorphic to both G1 and G2, but it is not isomorphic to either. G4 is homotopy equivalent to G1, G2, and G3, but not isomorphic nor homeomorphic to any of them. CROSSREFS Bounded from above by A000088. Sequence in context: A125513 A054174 A239890 * A222038 A328087 A001523 Adjacent sequences: A331551 A331552 A331553 * A331555 A331556 A331557 KEYWORD nonn,more AUTHOR Christian Goodbrake, Jan 20 2020 EXTENSIONS a(27) from Christian Goodbrake, Feb 25 2020 a(28)-a(29) from Christian Goodbrake, Feb 27 2020 a(30) from Christian Goodbrake, Mar 02 2020 STATUS approved

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.

Last modified March 1 19:16 EST 2024. Contains 370443 sequences. (Running on oeis4.)