

A247181


Total domination number of the nhypercube graph.


1




OFFSET

1,1


COMMENTS

a(n) = size of smallest subset S of vertices of the ncube 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


LINKS

Table of n, a(n) for n=1..10.
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 dominationtype invariants of Fibonacci cubes and hypercubes, Preprint 2016; See Table 4.
Jernej Azarija, S. Klavzar, Y. Rho, and S. Sim, On dominationtype invariants of Fibonacci cubes and hypercubes, Ars Mathematica Contemporanea, 14 (2018) 387395. 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


FORMULA

a(n) = 2*A000983(n1), at least if 2<=n<=9.  Omar E. Pol, Nov 22 2014. This formula is true for all n>=2 (see AzarijaHenningKlavž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


EXAMPLE

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


CROSSREFS

Cf. A000983 (half), A323515 (number of sets).
Sequence in context: A063776 A287135 A276063 * A118406 A355811 A072488
Adjacent sequences: A247178 A247179 A247180 * A247182 A247183 A247184


KEYWORD

nonn,more,hard


AUTHOR

Jernej Azarija, Nov 22 2014


EXTENSIONS

a(10) from Jernej Azarija, Jun 30 2016


STATUS

approved



