Abstract. The transversal number [Formula: see text] of a hypergraph [Formula: see text] is the minimum number of vertices that intersect every edge of [Formula: see text]. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [ Discuss. Math. Graph Theory, 22 (2002), pp. 199–210] conjectured that if [Formula: see text] is a 3-regular 6-uniform hypergraph of order [Formula: see text], then [Formula: see text]. In this paper we prove this conjecture, which has become known as the Tuza–Vestergaard conjecture.

In this paper, we continue the study of power domination in graphs (see [T. W. Haynes et al., SIAM J. Discrete Math., 15 (2002), pp. 519--529; P. Dorbec et al., SIAM J. Discrete Math., 22 (2008), pp. 554--567; A. Aazami et al., SIAM J. Discrete Math., 23 (2009), pp. 1382--1399]). Power domination in graphs was birthed from the problem of monitoring an electric power system by placing as few measurement devices in the system as possible. A set of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set following a set of rules (according to Kirschoff laws) for power system monitoring. The minimum cardinality of a power dominating set of a graph is its power domination number. We show that the power domination of a connected cubic graph on $n$ vertices different from $K_{3,3}$ is at most $n/4$ and this bound is tight. More generally, we show that for $k \ge 1$, the $k$-power domination number of a connected $(k+2)$-regular graph on $n$ vertices different from $K_{k+2,k+2}$ is at most $n/(k+3)$, where the $1$-power domination number is the ordinary power domination number. We show that these bounds are tight.