Vertex cover number, which is one of the most basic graph invariants, can be viewed as the smallest number of vertices that hit (or that belong to) every subgraph $K_2$ in a graph $G$. In this paper, we consider the next two smallest cases of connected graphs, which are the path $P_ 3$ and the cycle $C_3$ ; the problem is to minimize the set of vertices that hit every subgraph $H$ in $G$ , where $H$ is one of the two graphs. We focus on computational aspects of these two variations of the vertex cover number. We show that both problems are NP-complete even in the class of graphs that have no induced cycles of length $t$, where $t\in\{4,\ldots, 8\}$ (in fact, in the $P_3$-hitting case, the problem is NP-complete in even smaller family of graphs, where also triangles are forbidden). On the positive side, we prove a complementary result that in graphs with no induced $P_4$ (the so-called cographs) both problems become linear. Moreover, we consider a generalization of cographs -- $P_4$-tidy graphs, for which we establish an efficient algorithm for both problems.
COBISS.SI-ID: 18568025
The $2$-domination number $\gamma_2(G)$ of a graph $G$ is the minimum cardinality of a set $S\subseteq V(G)$ such that every vertex from $V(G)\setminus S$ is adjacent to at least two vertices in $S$. The annihilation number $a(G)$ is the largest integer $k$ such that the sum of the first $k$ terms of the non-decreasing degree sequence of $G$ is at most the number of its edges. It was conjectured that $\gamma_2(G) \leq a(G) +1$ holds for every connected graph $G$. The conjecture was earlier confirmed, in particular, for graphs of minimum degree $3$, for trees, and for block graphs. In this paper, we disprove the conjecture by proving that the $2$-domination number can be arbitrarily larger than the annihilation number. On the positive side we prove the conjectured bound for a large subclass of bipartite, connected cacti, thus generalizing a result of Jakovac from [Discrete Appl. Math. 260 (2019) 178--187].
COBISS.SI-ID: 18966105
Domination game (Brešar et al. in SIAM J Discrete Math 24:979-991, 2010) and total domination game (Henning et al. in Graphs Comb 31:1453-1462 (2015) are by now well established games played on graphs by two players, named Dominator and Staller. In this paper, Z-domination game, L-domination game, and LL-domination game are introduced as natural companions of the standard domination games. Versions of the Continuation Principle are proved for the new games. It is proved that in each of these games the outcome of the game, which is a corresponding graph invariant, differs by at most one depending whether Dominator or Staller starts the game. The hierarchy of the five domination games is established. The invariants are also bounded with respect to the (total) domination number and to the order of a graph. Values of the three new invariants are determined for paths up to a small constant independent from the length of a path. Several open problems and a conjecture are listed. The latter asserts that the L-domination game number is not greater than 6/7 of the order of a graph.
COBISS.SI-ID: 18819673