The total domination number $\gamma_t(G)$ of a graph $G$ is the minimum cardinality of a set $D\subseteq V(G)$ such that every vertex of $G$ has a neighbor in $D$. The annihilation number $a(G)$ is the largest integer $k$ for which the sum of the $k$ smallest degrees of $G$ is at most $|E(G)|$. A well-known conjecture, originating from Graffiti.pc and later formulated explicitly by Desormeaux, Haynes, and Henning, asserts that $\gamma_t(G)\le a(G)+1$ for every connected nontrivial graph $G$. The conjecture is known for graphs of minimum degree at least three and for several classes of graphs having vertices of degree one or two. In this paper we settle the minimum-degree-two case. More precisely, we prove $\gamma_t(G)\le a(G)+1$ for every connected graph $G$ with $\delta(G)=2$. The proof combines two sharp bounds on the total domination number with an estimate for the annihilation number. Moreover, in some specific cases, the stronger inequality $\gamma_t(G)\le a(G)$ holds.
Tuza conjectured that every finite simple graph $G$ satisfies $\tau(G) \leq 2\nu(G)$, where $\nu(G)$ is the maximum number of pairwise edge-disjoint triangles and $\tau(G)$ is the minimum number of edges whose deletion makes $G$ triangle-free. Puleo proved the conjecture for every graph of maximum average degree less t...
For a graph $G$ without isolated vertices, $\gamma(G)\le\gamma_t(G)\le 2\gamma(G)$. While graphs attaining $\gamma(G)=\gamma_t(G)$ have been studied extensively, a complete structural description in the smallest nontrivial case $\gamma(G)=2$ has remained open. We resolve this case according to girth. When $g(G)\ne 3$,...
A paired dominating set of a graph $G$ is a dominating set $D$ such that $G[D]$ has a perfect matching. The minimum size of such a set is the paired domination number $\gpr(G)$. Desormeaux and Henning conjectured that every cubic bipartite graph $G$ of order $n$ satisfies $\gpr(G)\le n/2$. We prove the conjecture in th...
For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular...
Let $G$ be a simple graph with maximum degree $\Delta\ge 3$, and let $P(G,k)$ denote its chromatic polynomial. For each positive integer $k$, the list-color function $P_{\ell}(G,k)$ is the minimum number of $L$-colorings of $G$ over all $k$-assignments $L$. In this paper, we prove that $P_{\ell}(G,k)=P(G,k)$ for every...
A dominating set $D$ of a graph $G$ is a \emph{fair dominating set} if every two vertices outside $D$ have the same number of neighbors in $D$, and the \emph{fair domination number} $\mathrm{fd}(G)$ is the minimum cardinality of such a set. Caro, Hansberg and Henning, who introduced this parameter, proved that $\mathrm...
Y. Caro, R. Škrekovski· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
