A353212 Hadwiger number of the n-path complement graph.

1, 1, 2, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, 15, 16, 16, 17, 18, 19, 19, 20, 21, 22, 22, 23, 24, 25, 25, 26, 27, 28, 28, 29, 30, 31, 31, 32, 33, 34, 34, 35, 36, 37, 37, 38, 39, 40, 40, 41, 42, 43, 43, 44, 45, 46, 46, 47, 48, 49, 49, 50, 51, 52, 52

Offset: 1

Author

Eric W. Weisstein, Apr 30 2022

Keywords

• nonn
• easy

Comments

A contraction in the complement of any set of paths reduces the total number of edges in the complement by at most 4. This gives an upper bound for the Hadwiger number which is obtainable for all path lengths except 4 and 5. In particular, for n >= 6, the complement of a P_n reduces to the complement of a P_{n-4} union 3 universal nodes by contracting the second and second to last nodes of the path. With P_8 and P_9 the 2nd and 6th nodes should be contracted (instead of reducing to P_4 or P_5 respectively). - Andrew Howroyd, Jun 18 2025

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Hadwiger Number.
• Eric Weisstein's World of Mathematics, Path Complement Graph.
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Crossrefs

Cf. A037915.

Programs

PARI

a(n) = (3*n + 1)\4 - (n==4||n==5) \\ Andrew Howroyd, Jun 18 2025

Formula

a(n) = floor((3*n + 1)/4) = A037915(n+1) for n >= 6. - Andrew Howroyd, Jun 18 2025

Extensions

a(16) onwards from Andrew Howroyd, Jun 18 2025