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!)
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
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
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.

License Agreements, Terms of Use, Privacy Policy. .

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