Hypercube orientations with only two in-degrees

DOI10.1016/J.JCTA.2011.02.003MaRDI QIDQ543901zbMATH OpenOpenAlexFDO

Authors Steve Butler, Eric Tressler, Joe P. Buhler, Ron Graham

Publication date 17 June 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.2311

zbMATH Keywords

Hamming ballshat guessing strategieshypercubeorientations

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Abstract: We consider the problem of orienting the edges of the $n$-dimensional hypercube so only two different in-degrees $a$ and $b$ occur. We show that this can be done, for two specified in-degrees, if and only if an obvious necessary condition holds. Namely, there exist non-negative integers $s$ and $t$ so that $s+t=2^n$ and $as+bt=n{2}^{n-1}$. This is connected to a question arising from constructing a strategy for a "hat puzzle."

Recommendations

• Orientations of 2-dimensional torus networks with only two in-degrees
• Vertex Turán problems for the oriented hypercube
• Equitable hypergraph orientations
• A construction for the hat problem on a directed graph
• Oriented hypercubes

Cites work

• A note on marking lines in \([k]^n\)
• Error correction coding. Mathematical methods and algorithms
• Hat Guessing Games

Cited in

(3)

• Vertex-degree based topological indices of digraphs
• On a conjecture of Butler and Graham
• A note on marking lines in \([k]^n\)

This page was built for publication: Hypercube orientations with only two in-degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q543901)