A247181 Total domination number of the n-hypercube graph.

2, 2, 4, 4, 8, 14, 24, 32, 64, 124

Offset: 1

Author

Jernej Azarija, Nov 22 2014

Keywords

• nonn
• more
• hard

Comments

a(n) = size of smallest subset S of vertices of the n-cube Q_n such that every vertex of Q_n has a neighbor in S.

Proof for first formula can be found in the Verstraten link. - Kamiel P.F. Verstraten, Jun 10 2015

Examples

			a(1) = 2 since the complete graph on two vertices can only be totally dominated by taking both vertices.
		

Links

• J. Azarija, M. A. Henning and S. Klavžar (Total) Domination in Prisms, arXiv:1606.08143 [math.CO], 2016.
• Jernej Azarija, S. Klavzar, Y. Rho, and S. Sim, On domination-type invariants of Fibonacci cubes and hypercubes, Preprint 2016; See Table 4.
• Jernej Azarija, S. Klavzar, Y. Rho, and S. Sim, On domination-type invariants of Fibonacci cubes and hypercubes, Ars Mathematica Contemporanea, 14 (2018) 387-395. See Table 4.
• M. Henning and A. Yeo, Total domination in graphs, Springer, 2013.
• Kamiel P. F. Verstraten, A Generalization of the Football Pool Problem, Master's Thesis, Tilburg University, 2014.
• Eric Weisstein's World of Mathematics, Hypercube Graph
• Eric Weisstein's World of Mathematics, Total Domination Number

Crossrefs

Cf. A000983 (half), A323515 (number of sets).

Formula

a(n) = 2*A000983(n-1), at least if 2<=n<=9. - Omar E. Pol, Nov 22 2014. This formula is true for all n>=2 (see Azarija-Henning-Klavžar paper). - Omar E. Pol, Jul 01 2016

a(n) = A230014(n,1), at least if 1<=n<=9. - Omar E. Pol, Nov 23 2014. This formula is true for all n>=1 (in accordance with the above comment). - Omar E. Pol, Jul 01 2016

Extensions

a(10) from Jernej Azarija, Jun 30 2016