The Maker–Breaker domination game is played on a graph G by two players, called Dominator and Staller, who alternately choose a vertex that has not been played so far. Dominator wins the game if his moves form a dominating set. Staller wins if she plays all vertices from a closed neighborhood of a vertex v∈V(G). Dominator’s fast winning strategies were studied earlier. In this work, we concentrate on the cases when Staller has a winning strategy in the game. We introduce the invariant γSMB′(G) (resp., γSMB(G)) which is the smallest integer k such that, under any strategy of Dominator, Staller can win the game by playing at most k vertices, if Staller (resp., Dominator) plays first on the graph G. We prove some basic properties of γSMB(G) and γSMB′(G) and study the parameters’ changes under some operators as taking the disjoint union of graphs or deleting a cut vertex. We show that the inequality δ(G)+1≤γSMB′(G)≤γSMB(G) always holds and that for every three integers r,s,t with 2≤r≤s≤t, there exists a graph G such that δ(G)+1=r, γSMB′(G)=s, and γSMB(G)=t. We prove exact formulas for γSMB′(G) where G is a path or it is a tadpole graph which is obtained from the disjoint union of a cycle and a path by adding one edge between them.

Let G be a graph. A dominating set D⊆V(G) is a super dominating set if for every vertex x∈V(G)∖D there exists y∈D such that NG(y)∩(V(G)∖D))={x}. The cardinality of a smallest super dominating set of G is the super domination number of G. An exact formula for the super domination number of a tree T is obtained, and it is demonstrated that a smallest super dominating set of T can be computed in linear time. It is proved that it is NP-complete to decide whether the super domination number of a graph G is at most a given integer if G is a bipartite graph of girth at least 8. The super domination number is determined for all k-subdivisions of graphs. Interestingly, in half of the cases the exact value can be efficiently computed from the obtained formulas, while in the other cases the computation is hard. While obtaining these formulas, II-matching numbers are introduced and proved that they are computationally hard to determine.

Abstract For an integer , a k‐path vertex cover of a graph is a set that shares a vertex with every path subgraph of order k in G. The minimum cardinality of a k‐path vertex cover is denoted by . We give estimates—mostly upper bounds—on in terms of various parameters, including vertex degrees and the number of vertices and edges. The problem is also considered on chordal graphs and planar graphs.

A caterpillar is either a K2 or a tree on at least 3 vertices such that deleting its leaves we obtain a path of order at least 1. Given a simple undirected graph G=(V,E), a caterpillar factor of G is a set of caterpillar subgraphs of G such that each vertex v∈V belongs to exactly one of them. A caterpillar factor F is internally even if every vertex of degree degF(v)≥2 has an even degree; F is odd if degF(v) is odd for every v∈V(G). We present a linear-time algorithm that decides whether a tree admits an internally even caterpillar factor and, on the other hand, we prove that the decision problem is NP-complete on the class of planar bipartite graphs. For the odd caterpillar factor problem, we obtain similar results. It can be decided in linear time over the class of trees, but the problem is NP-complete on the class of bipartite graphs.

The $\frac{3}{4}$-Game Total Domination Conjecture posed by Henning, Klavžar, and Rall [Combinatorica, (2016)] states that if $G$ is a graph on $n$ vertices in which every component contains at least three vertices, then $\gamma_{tg}(G) \le \frac{3}{4}n$, where $\gamma_{tg}(G)$ denotes the game total domination number of $G$. Motivated by this conjecture, we raise the problem to a higher level by introducing a transversal game in hypergraphs. We define the game transversal number, $\tau_g(H)$, of a hypergraph $H$, and prove that if every edge of $H$ has size at least 2, and $H \ncong C_4$, then $\tau_g(H) \le \frac{4}{11}(n_{_H}+m_{_H})$, where $n_{_H}$ and $m_{_H}$ denote the number of vertices and edges, respectively, in $H$. Further, we characterize the hypergraphs achieving equality in this bound. As an application of this result, we prove that if $G$ is a graph on $n$ vertices with minimum degree at least 2, then $\gamma_{{tg}}(G) < \frac{8}{11} n$. As a consequence of this result, the $\frac{3}{4}$-Game Total Domination Conjecture is true over the class of graphs with minimum degree at least 2.