A286139 Number of connected induced (non-null) subgraphs of the n X n king graph.

1, 15, 388, 37196, 14765089, 24076152503, 159850328891568, 4290837646252661680, 463376724731585422732393, 200665409586497566263900755703, 347694350828123116321061347501951972, 2406781070555276417850396576804205226358828, 66481859567653621586313146932097075651519991887257

Offset: 1

Author

Giovanni Resta, May 03 2017

Keywords

• nonn
• hard

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..16
• Eric Weisstein's World of Mathematics, King Graph
• Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

Crossrefs

Cf. A020873 (wheel), A059020 (ladder), A059525 (grid), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286186 (friendship), A286187 (web), A286188 (gear), A286189 (rook), A285765 (queen).

Programs

Mathematica

Table[If[n<2, n, g = GraphData[{"King", {n, n}}]; -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[n^2]}]], {n, 4}]

Extensions

a(10)-a(13) from Andrew Howroyd, May 20 2017