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
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