A343464 The number of n-vertex graphs that are minimally non-Hamming-embeddable.

0, 0, 0, 1, 2, 0, 1, 1, 6

Offset

1,5

Comments

For Hamming embeddability see A343463. Graph G is minimally non-Hamming-embeddable if G cannot be embedded, yet G\v is embeddable for all vertices v.

I conjecture (on admittedly weak evidence) that these graphs are always planar.

References

D. E. Knuth, The Art of Computer Programming, Volume 4B (in preparation). Section 7.2.2.3 will contain an exercise devoted to this topic.

Links

Table of n, a(n) for n=1..9.

Example

For n=5 the a(5)=2 graphs are C5 and K32.

Crossrefs

Cf. A343463.

Sequence in context: A322838 A085496 A228748 * A225094 A350594 A295859

Adjacent sequences: A343461 A343462 A343463 * A343465 A343466 A343467

Keyword

nonn,more

Author

Don Knuth, Apr 16 2021

Status

approved