login
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
OFFSET
0,3
COMMENTS
Two graphs are homotopy equivalent if their images under embeddings are homotopy equivalent in the usual topological sense.
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