BZPEER

preprint2026arXiv

Total isolation game in graphs

The total isolation game is played on a graph $G$ by two players who take turns playing a vertex such that if $S$ is the set of already played vertices, then a vertex can be selected only if it is adjacent to a vertex that belongs to a (nontrivial) component of the graph $G - N_G(S)$ of order at least $2$ or a vertex that is isolated in $G - N_G(S)$ and belongs to the set $S$ , where $N_G(S)$ is the set of vertices adjacent to a vertex in $S$ . Dominator wishes to finish the game with the minimum number of played vertices, while Staller has the opposite goal. The game total isolation number $ι_{\rm gt}(G)$ is the number of moves in the Dominator-start game where both players play optimally. We prove that if $G$ is a connected graph of order $n \ge 3$ , then $ι_{\rm gt}(G) < \frac{5}{6}n$ . Furthermore if $G$ has minimum degree at least $2$ , then we prove that $ι_{\rm gt}(G) \le \frac{3}{4}n$ . More generally, if $G$ is a connected graph of order $n \ge 3$ with minimum degree $δ$ where $δ\ge 2$ , then we prove that $ι_{\rm gt}(G) \le \left( \frac{2δ-1}{3δ-2} \right) n$ . Among other results it is proved that if $G$ is a graph of order $n$ with diameter $2$ , then $ι_{\rm gt}(G) \le \frac{2}{3}n$ .

preprint2022arXiv

Common domination perfect graphs

A dominating set in a graph $G$ is a set $S$ of vertices such that every vertex that does not belong to $S$ is adjacent to a vertex in $S$ . The domination number $γ(G)$ of $G$ is the minimum cardinality of a dominating set of $G$ . The common independence number $α_c(G)$ of $G$ is the greatest integer $r$ such that every vertex of $G$ belongs to some independent set of cardinality at least~ $r$ . The common independence number is squeezed between the independent domination number $i(G)$ and the independence number $α(G)$ of $G$ , that is, $γ(G) \le i(G) \le α_c(G) \le α(G)$ . A graph $G$ is domination perfect if $γ(H) = i(H)$ for every induced subgraph $H$ of $G$ . We define a graph $G$ as common domination perfect if $γ(H) = α_c(H)$ for every induced subgraph $H$ of $G$ . We provide a characterization of common domination perfect graphs in terms of ten forbidden induced subgraphs.

preprint2021arXiv

Minimal graphs with disjoint dominating and total dominating sets

A graph $G$ is a DTDP-graph if it has a pair $(D,T)$ of disjoint sets of vertices of $G$ such that $D$ is a dominating set and $T$ is a total dominating set of $G$ . Such graphs were studied in a number of research papers. In this paper we study further properties of DTDP-graphs and, in particular, we characterize minimal DTDP-gaphs without loops.

preprint2020arXiv

Independent Domination in Subcubic Graphs

A set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in $S$ . If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$ . In 2013 Goddard and Henning [Discrete Math 313 (2013), 839--854] conjectured that if $G$ is a connected cubic graph of order $n$ , then $i(G) \le \frac{3}{8}n$ , except if $G$ is the complete bipartite graph $K_{3,3}$ or the $5$ -prism $C_5 \, \Box \, K_2$ . Further they construct two infinite families of connected cubic graphs with independent domination three-eighths their order. They remark that perhaps it is even true that for $n > 10$ these two families are only families for which equality holds. In this paper, we provide a new family of connected cubic graphs $G$ of order $n$ such that $i(G) = \frac{3}{8}n$ . We also show that if $G$ is a subcubic graph of order $n$ with no isolated vertex, then $i(G) \le \frac{1}{2}n$ , and we characterize the graphs achieving equality in this bound.

preprint2020arXiv

The Enclaveless Competition Game

For a subset $S$ of vertices in a graph $G$ , a vertex $v \in S$ is an enclave of $S$ if $v$ and all of its neighbors are in $S$ , where a neighbor of $v$ is a vertex adjacent to $v$ . A set $S$ is enclaveless if it does not contain any enclaves. The enclaveless number $Ψ(G)$ of $G$ is the maximum cardinality of an enclaveless set in $G$ . As first observed in 1997 by Slater [J. Res. Nat. Bur. Standards 82 (1977), 197--202], if $G$ is a graph with $n$ vertices, then $γ(G) + Ψ(G) = n$ where $γ(G)$ is the well-studied domination number of $G$ . In this paper, we continue the study of the competition-enclaveless game introduced in 2001 by Phillips and Slater [Graph Theory Notes N. Y. 41 (2001), 37--41] and defined as follows. Two players take turns in constructing a maximal enclaveless set $S$ , where one player, Maximizer, tries to maximize $|S|$ and one player, Minimizer, tries to minimize~ $|S|$ . The competition-enclaveless game number $Ψ_g^+(G)$ of $G$ is the number of vertices played when Maximizer starts the game and both players play optimally. We study among other problems the conjecture that if $G$ is an isolate-free graph of order $n$ , then $Ψ_g^+(G) \ge \frac{1}{2}n$ . We prove this conjecture for regular graphs and for claw-free graphs.

preprint2019arXiv

Minimal graphs with disjoint dominating and paired-dominating sets

A subset $D\subseteq V_G$ is a dominating set of $G$ if every vertex in $V_G-D$ has a~neighbor in $D$ , while $D$ is a paired-dominating set of $G$ if $D$ is a~dominating set and the subgraph induced by $D$ contains a perfect matching. A graph $G$ is a $D\!P\!D\!P$ -graph if it has a pair $(D,P)$ of disjoint sets of vertices of $G$ such that $D$ is a dominating set and $P$ is a paired-dominating set of $G$ . The study of the $D\!P\!D\!P$ -graphs was initiated by Southey and Henning (Cent. Eur. J. Math. 8 (2010) 459--467; J. Comb. Optim. 22 (2011) 217--234). In this paper, we provide conditions which ensure that a graph is a $D\!P\!D\!P$ -graph. In particular, we characterize the minimal $D\!P\!D\!P$ -graphs.

preprint2017arXiv

On accurate domination in graphs

A dominating set of a graph $G$ is a subset $D \subseteq V_G$ such that every vertex not in $D$ is adjacent to at least one vertex in $D$ . The cardinality of a smallest dominating set of $G$ , denoted by $γ(G)$ , is the domination number of $G$ . The accurate domination number of $G$ , denoted by $γ_{\rm a}(G)$ , is the cardinality of a smallest set $D$ that is a dominating set of $G$ and no $|D|$ -element subset of $V_G \setminus D$ is a dominating set of $G$ . We study graphs for which the accurate domination number is equal to the domination number. In particular, all trees $G$ for which $γ_{\rm a}(G) = γ(G)$ are characterized. Furthermore, we compare the accurate domination number with the domination number of different coronas of a graph.

preprint2016arXiv

(Total) Domination in Prisms

With the aid of hypergraph transversals it is proved that $γ_t(Q_{n+1}) = 2γ(Q_n)$ , where $γ_t(G)$ and $γ(G)$ denote the total domination number and the domination number of $G$ , respectively, and $Q_n$ is the $n$ -dimensional hypercube. More generally, it is shown that if $G$ is a bipartite graph, then $γ_t(G \square K_2) = 2γ(G)$ . Further, we show that the bipartite condition is essential by constructing, for any $k \ge 1$ , a (non-bipartite) graph $G$ such that $γ_t (G \square K_2 ) = 2γ(G) - k$ . Along the way several domination-type identities for hypercubes are also obtained.

preprint2016arXiv

Bounds on the Game Transversal Number in Hypergraphs

Let $H = (V,E)$ be a hypergraph with vertex set $V$ and edge set $E$ of order $\nH = |V|$ and size $\mH = |E|$. A transversal in $H$ is a subset of vertices in $H$ that has a nonempty intersection with every edge of $H$ . A vertex hits an edge if it belongs to that edge. The transversal game played on $H$ involves of two players, \emph{Edge-hitter} and \emph{Staller}, who take turns choosing a vertex from $H$ . Each vertex chosen must hit at least one edge not hit by the vertices previously chosen. The game ends when the set of vertices chosen becomes a transversal in $H$ . Edge-hitter wishes to minimize the number of vertices chosen in the game, while Staller wishes to maximize it. The \emph{game transversal number}, $τ_g(H)$ , of $H$ is the number of vertices chosen when Edge-hitter starts the game and both players play optimally. We compare the game transversal number of a hypergraph with its transversal number, and also present an important fact concerning the monotonicity of $τ_g$ , that we call the Transversal Continuation Principle. It is known that if $H$ is a hypergraph with all edges of size at least~ $2$ , and $H$ is not a $4$ -cycle, then $τ_g(H) \le \frac{4}{11}(\nH+\mH)$; and if $H$ is a (loopless) graph, then $τ_g(H) \le \frac{1}{3}(\nH + \mH + 1)$. We prove that if $H$ is a $3$ -uniform hypergraph, then $τ_g(H) \le \frac{5}{16}(\nH + \mH)$, and if $H$ is $4$ -uniform, then $τ_g(H) \le \frac{71}{252}(\nH + \mH)$.

preprint2016arXiv

Hereditary Equality of Domination and Exponential Domination

We characterize a large subclass of the class of those graphs $G$ for which the exponential domination number of $H$ equals the domination number of $H$ for every induced subgraph $H$ of $G$ .

preprint2016arXiv

Locating-total dominating sets in twin-free graphs: a conjecture

A total dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex of $G$ has a neighbor in $D$ . A locating-total dominating set of $G$ is a total dominating set $D$ of $G$ with the additional property that every two distinct vertices outside $D$ have distinct neighbors in $D$ ; that is, for distinct vertices $u$ and $v$ outside $D$ , $N(u) \cap D \ne N(v) \cap D$ where $N(u)$ denotes the open neighborhood of $u$ . A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-total domination number of $G$ , denoted $LT(G)$ , is the minimum cardinality of a locating-total dominating set in $G$ . It is well-known that every connected graph of order $n \geq 3$ has a total dominating set of size at most $\frac{2}{3}n$ . We conjecture that if $G$ is a twin-free graph of order $n$ with no isolated vertex, then $LT(G) \leq \frac{2}{3}n$ . We prove the conjecture for graphs without $4$ -cycles as a subgraph. We also prove that if $G$ is a twin-free graph of order $n$ , then $LT(G) \le \frac{3}{4}n$ .

preprint2016arXiv

Location-domination and matching in cubic graphs

A dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex outside $D$ is adjacent to a vertex in $D$ . A locating-dominating set of $G$ is a dominating set $D$ of $G$ with the additional property that every two distinct vertices outside $D$ have distinct neighbors in $D$ ; that is, for distinct vertices $u$ and $v$ outside $D$ , $N(u) \cap D \neq N(v) \cap D$ where $N(u)$ denotes the open neighborhood of $u$ . A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-domination number of $G$ , denoted $γ_L(G)$ , is the minimum cardinality of a locating-dominating set in $G$ . Garijo, Gonzalez and Marquez [Applied Math. Computation 249 (2014), 487--501] posed the conjecture that for $n$ sufficiently large, the maximum value of the location-domination number of a twin-free, connected graph on $n$ vertices is equal to $\lfloor \frac{n}{2} \rfloor$ . We propose the related (stronger) conjecture that if $G$ is a twin-free graph of order $n$ without isolated vertices, then $γ_L(G)\leq \frac{n}{2}$ . We prove the conjecture for cubic graphs. We rely heavily on proof techniques from matching theory to prove our result.

preprint2016arXiv

Location-domination in line graphs

A set $D$ of vertices of a graph $G$ is locating if every two distinct vertices outside $D$ have distinct neighbors in $D$ ; that is, for distinct vertices $u$ and $v$ outside $D$ , $N(u) \cap D \neq N(v) \cap D$ , where $N(u)$ denotes the open neighborhood of $u$ . If $D$ is also a dominating set (total dominating set), it is called a locating-dominating set (respectively, locating-total dominating set) of $G$ . A graph $G$ is twin-free if every two distinct vertices of $G$ have distinct open and closed neighborhoods. It is conjectured [D. Garijo, A. Gonzalez and A. Marquez, The difference between the metric dimension and the determining number of a graph. Applied Mathematics and Computation 249 (2014), 487--501] and [F. Foucaud and M. A. Henning. Locating-total dominating sets in twin-free graphs: a conjecture. The Electronic Journal of Combinatorics 23 (2016), P3.9] respectively, that any twin-free graph $G$ without isolated vertices has a locating-dominating set of size at most one-half its order and a locating-total dominating set of size at most two-thirds its order. In this paper, we prove these two conjectures for the class of line graphs. Both bounds are tight for this class, in the sense that there are infinitely many connected line graphs for which equality holds in the bounds.

preprint2016arXiv

Relating Domination, Exponential Domination, and Porous Exponential Domination

The domination number $γ(G)$ of a graph $G$ , its exponential domination number $γ_e(G)$ , and its porous exponential domination number $γ_e^*(G)$ satisfy $γ_e^*(G)\leq γ_e(G)\leq γ(G)$ . We contribute results about the gaps in these inequalities as well as the graphs for which some of the inequalities hold with equality. Relaxing the natural integer linear program whose optimum value is $γ_e^*(G)$ , we are led to the definition of the fractional porous exponential domination number $γ_{e,f}^*(G)$ of a graph $G$ . For a subcubic tree $T$ of order $n$ , we show $γ_{e,f}^*(T)=\frac{n+2}{6}$ and $γ_e(T)\leq 2γ_{e,f}^*(T)$ . We characterize the two classes of subcubic trees $T$ with $γ_e(T)=γ_{e,f}^*(T)$ and $γ(T)=γ_e(T)$ , respectively. Using linear programming arguments, we establish several lower bounds on the fractional porous exponential domination number in more general settings.

preprint2016arXiv

Thoroughly Distributed Colorings

We consider (not necessarily proper) colorings of the vertices of a graph where every color is thoroughly distributed, that is, appears in every open neighborhood. Equivalently, every color is a total dominating set. We define $\td(G)$ as the maximum number of colors in such a coloring and $\FTD(G)$ as the fractional version thereof. In particular, we show that every claw-free graph with minimum degree at least~ $2$ has~$\FTD(G)\ge 3/2$ and this is best possible. For planar graphs, we show that every triangular disc has $\FTD(G) \ge 3/2$ and this is best possible, and that every planar graph has $\td(G) \le 4$ and this is best possible, while we conjecture that every planar triangulation has $\td(G)\ge 2$. Further, although there are arbitrarily large examples of connected, cubic graphs with $\td(G)=1$, we show that for a connected cubic graph $\FTD(G) \ge 2-o(1)$, and conjecture that it is always at least~ $2$ . We also consider the related concepts in hypergraphs.

preprint2016arXiv

Tight lower bounds on the matching number in a graph with given maximum degree

Let $k \geq 3$ . We prove the following three bounds for the matching number, $α'(G)$ , of a graph, $G$ , of order $n$ size $m$ and maximum degree at most $k$ . If $k$ is odd, then $α'(G) \ge \left( \frac{k-1}{k(k^2 - 3)} \right) n \, + \, \left( \frac{k^2 - k - 2}{k(k^2 - 3)} \right) m \, - \, \frac{k-1}{k(k^2 - 3)}$ . If $k$ is even, then $α'(G) \ge \frac{n}{k(k+1)} \, + \, \frac{m}{k+1} - \frac{1}{k}$ . If $k$ is even, then $α'(G) \ge \left( \frac{k+2}{k^2+k+2} \right) m \, - \, \left( \frac{k-2}{k^2+k+2} \right) n \, - \frac{k+2}{k^2+k+2}$ . In this paper we actually prove a slight strengthening of the above for which the bounds are tight for essentially all densities of graphs. The above three bounds are in fact powerful enough to give a complete description of the set $L_k$ of pairs $(γ,β)$ of real numbers with the following property. There exists a constant $K$ such that $α'(G) \geq γn + βm - K$ for every connected graph $G$ with maximum degree at most~ $k$ , where $n$ and $m$ denote the number of vertices and the number of edges, respectively, in $G$ . We show that $L_k$ is a convex set. Further, if $k$ is odd, then $L_k$ is the intersection of two closed half-spaces, and there is exactly one extreme point of $L_k$ , while if $k$ is even, then $L_k$ is the intersection of three closed half-spaces, and there are precisely two extreme points of $L_k$ .

preprint2016arXiv

Total Dominating Sequences in Graphs

A vertex in a graph totally dominates another vertex if they are adjacent. A sequence of vertices in a graph $G$ is called a total dominating sequence if every vertex $v$ in the sequence totally dominates at least one vertex that was not totally dominated by any vertex that precedes $v$ in the sequence, and at the end all vertices of $G$ are totally dominated. While the length of a shortest such sequence is the total domination number of $G$ , in this paper we investigate total dominating sequences of maximum length, which we call the Grundy total domination number, $γ_{\rm gr}^t(G)$ , of $G$ . We provide a characterization of the graphs $G$ for which $γ_{\rm gr}^t(G)=|V(G)|$ and of those for which $γ_{\rm gr}^t(G)=2$ . We show that if $T$ is a nontrivial tree of order~ $n$ with no vertex with two or more leaf-neighbors, then $γ_{\rm gr}^t(T) \ge \frac{2}{3}(n+1)$ , and characterize the extremal trees. We also prove that for $k \ge 3$ , if $G$ is a connected $k$ -regular graph of order~ $n$ different from $K_{k,k}$ , then $γ_{\rm gr}^t(G) \ge (n + \lceil \frac{k}{2} \rceil - 2)/(k-1)$ if $G$ is not bipartite and $γ_{\rm gr}^t(G) \ge (n + 2\lceil \frac{k}{2} \rceil - 4)/(k-1)$ if $G$ is bipartite. The Grundy total domination number is proven to be bounded from above by two times the Grundy domination number, while the former invariant can be arbitrarily smaller than the latter. Finally, a natural connection with edge covering sequences in hypergraphs is established, which in particular yields the NP-completeness of the decision version of the Grundy total domination number.

preprint2016arXiv

Trees with Equal Total Domination and Game Total Domination Numbers

In this paper, we continue the study of the total domination game in graphs introduced in [Graphs Combin. 31(5) (2015), 1453--1462], where the players Dominator and Staller alternately select vertices of $G$ . Each vertex chosen must strictly increase the number of vertices totally dominated, where a vertex totally dominates another vertex if they are neighbors. This process eventually produces a total dominating set $S$ of $G$ in which every vertex is totally dominated by a vertex in $S$ . Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game total domination number, $γ_{\rm tg}(G)$ , (respectively, Staller-start game total domination number, $γ_{\rm tg}'(G)$ ) of $G$ is the number of vertices chosen when Dominator (respectively, Staller) starts the game and both players play optimally. For general graphs $G$ , sometimes $γ_{\rm tg}(G) > γ_{\rm tg}'(G)$ . We show that if $G$ is a forest with no isolated vertex, then $γ_{\rm tg}(G) \le γ_{\rm tg}'(G)$ . Using this result, we characterize the trees with equal total domination and game total domination number.

preprint2015arXiv

Largest Domination Number and Smallest Independence Number of Forests with given Degree Sequence

For a sequence $d$ of non-negative integers, let ${\cal F}(d)$ be the set of all forests whose degree sequence is $d$ . We present closed formulas for $γ_{\max}^{\cal F}(d)=\max\{ γ(F):F\in {\cal F}(d)\}$ and $α_{\min}^{\cal F}(d)=\min\{ α(F):F\in {\cal F}(d)\}$ where $γ(F)$ and $α(F)$ are the domination number and the independence number of a forest $F$ , respectively.

preprint2015arXiv

Locating-dominating sets in twin-free graphs

A locating-dominating set of a graph $G$ is a dominating set $D$ of $G$ with the additional property that every two distinct vertices outside $D$ have distinct neighbors in $D$ ; that is, for distinct vertices $u$ and $v$ outside $D$ , $N(u) \cap D \ne N(v) \cap D$ where $N(u)$ denotes the open neighborhood of $u$ . A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-domination number of $G$ , denoted $γ_L(G)$ , is the minimum cardinality of a locating-dominating set in $G$ . It is conjectured [D. Garijo, A. González and A. Márquez. The difference between the metric dimension and the determining number of a graph. Applied Mathematics and Computation 249 (2014), 487--501] that if $G$ is a twin-free graph of order $n$ without isolated vertices, then $γ_L(G)\le \frac{n}{2}$ . We prove the general bound $γ_L(G)\le \frac{2n}{3}$ , slightly improving over the $\lfloor\frac{2n}{3}\rfloor+1$ bound of Garijo et al. We then provide constructions of graphs reaching the $\frac{n}{2}$ bound, showing that if the conjecture is true, the family of extremal graphs is a very rich one. Moreover, we characterize the trees $G$ that are extremal for this bound. We finally prove the conjecture for split graphs and co-bipartite graphs.

preprint2015arXiv

Matchings and Path Covers with applications to Domination in Graphs

Let $G$ be a graph with no isolated vertex. A matching in $G$ is a set of edges that are pairwise not adjacent in $G$ , while the matching number, $α'(G)$ , of $G$ is the maximum size of a matching in $G$ . The path covering number, $\rm{pc}(G)$ , of $G$ is the minimum number of vertex disjoint paths such that every vertex belongs to a path in the cover. We show that if $G$ has order $n$ , then $α'(G) + \frac{1}{2}\rm{pc}(G) \ge \frac{n}{2}$ and we provide a constructive characterization of the graphs achieving equality in this bound. It is known that $γ(G) \le α'(G)$ and $γ_t(G) \le α'(G) + \rm{pc}(G)$ , where $γ(G)$ and $γ_t(G)$ denote the domination and the total domination number of $G$ . As an application of our result on the matching and path cover numbers, we show that if $G$ is a graph with $δ(G) \ge 3$ , then $γ_t(G) \le α'(G) + \frac{1}{2}(\rm{pc}(G) - 1)$ , and this bound is tight. A set $S$ of vertices in $G$ is a neighborhood total dominating set of $G$ if it is a dominating set of $G$ with the property that the subgraph induced by the open neighborhood of the set $S$ has no isolated vertex. The neighborhood total domination number, $γ_{\rm nt}(G)$ , is the minimum cardinality of a neighborhood total dominating set of $G$ . We observe that $γ(G) \le γ_{\rm nt}(G) \le γ_t(G)$ . As a further application of our result on the matching and path cover numbers, we show that if $G$ is a connected graph on at least six vertices, then $γ_{\rm nt}(G) \le α'(G) + \frac{1}{2}\rm{pc}(G)$ and this bound is tight.

preprint2015arXiv

Progress Towards the Total Domination Game $\frac{3}{4}$ -Conjecture

In this paper, we continue the study of the total domination game in graphs introduced in [Graphs Combin. 31(5) (2015), 1453--1462], where the players Dominator and Staller alternately select vertices of $G$ . Each vertex chosen must strictly increase the number of vertices totally dominated, where a vertex totally dominates another vertex if they are neighbors. This process eventually produces a total dominating set $S$ of $G$ in which every vertex is totally dominated by a vertex in $S$ . Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game total domination number, $γ_{\rm tg}(G)$ , of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. Henning, Klavžar and Rall [Combinatorica, to appear] posted the $\frac{3}{4}$ -Game Total Domination Conjecture that states that if $G$ is a graph on $n$ vertices in which every component contains at least three vertices, then $γ_{\rm tg}(G) \le \frac{3}{4}n$ . In this paper, we prove this conjecture over the class of graphs $G$ that satisfy both the condition that the degree sum of adjacent vertices in $G$ is at least $4$ and the condition that no two vertices of degree $1$ are at distance $4$ apart in $G$ . In particular, we prove that by adopting a greedy strategy, Dominator can complete the total domination game played in a graph with minimum degree at least $2$ in at most $3n/4$ moves.

preprint2015arXiv

Smallest Domination Number and Largest Independence Number of Graphs and Forests with given Degree Sequence

For a sequence $d$ of non-negative integers, let ${\cal G}(d)$ and ${\cal F}(d)$ be the sets of all graphs and forests with degree sequence $d$ , respectively. Let $γ_{\min}(d)=\min\{ γ(G):G\in {\cal G}(d)\}$ , $α_{\max}(d)=\max\{ α(G):G\in {\cal G}(d)\}$ , $γ_{\min}^{\cal F}(d)=\min\{ γ(F):F\in {\cal F}(d)\}$ , and $α_{\max}^{\cal F}(d)=\max\{ α(F):F\in {\cal F}(d)\}$ where $γ(G)$ is the domination number and $α(G)$ is the independence number of a graph $G$ . Adapting results of Havel and Hakimi, Rao showed in 1979 that $α_{\max}(d)$ can be determined in polynomial time. We establish the existence of realizations $G\in {\cal G}(d)$ with $γ_{\min}(d)=γ(G)$ , and $F_γ,F_α\in {\cal F}(d)$ with $γ_{\min}^{\cal F}(d)=γ(F_γ)$ and $α_{\max}^{\cal F}(d)=α(F_α)$ that have strong structural properties. This leads to an efficient algorithm to determine $γ_{\min}(d)$ for every given degree sequence $d$ with bounded entries as well as closed formulas for $γ_{\min}^{\cal F}(d)$ and $α_{\max}^{\cal F}(d)$ .

preprint2015arXiv

Transversals in $4$ -Uniform Hypergraphs

Let $H$ be a $3$ -regular $4$ -uniform hypergraph on $n$ vertices. The transversal number $τ(H)$ of $H$ is the minimum number of vertices that intersect every edge. Lai and Chang [J. Combin. Theory Ser. B 50 (1990), 129--133] proved that $τ(H) \le 7n/18$ . Thomassé and Yeo [Combinatorica 27 (2007), 473--487] improved this bound and showed that $τ(H) \le 8n/21$ . We provide a further improvement and prove that $τ(H) \le 3n/8$ , which is best possible due to a hypergraph of order eight. More generally, we show that if $H$ is a $4$ -uniform hypergraph on $n$ vertices and $m$ edges with maximum degree $Δ(H) \le 3$ , then $τ(H) \le n/4 + m/6$ , which proves a known conjecture. We show that an easy corollary of our main result is that the total domination number of a graph on $n$ vertices with minimum degree at least~4 is at most $3n/7$ , which was the main result of the Thomassé-Yeo paper [Combinatorica 27 (2007), 473--487].

preprint2014arXiv

A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem

For $k \ge 2$ , let $H$ be a $k$ -uniform hypergraph on $n$ vertices and $m$ edges. The transversal number $τ(H)$ of $H$ is the minimum number of vertices that intersect every edge. Chvátal and McDiarmid [Combinatorica 12 (1992), 19--26] proved that $τ(H)\le ( n + \left\lfloor \frac k2 \right\rfloor m )/ ( \left\lfloor \frac{3k}2 \right\rfloor )$ . When $k = 3$ , the connected hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem were characterized by Henning and Yeo [J. Graph Theory 59 (2008), 326--348]. In this paper, we characterize the connected hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem for $k = 2$ and for all $k \ge 4$ .

preprint2014arXiv

Disjunctive Total Domination in Graphs

Let $G$ be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, $γ_t(G)$ . A set $S$ of vertices in $G$ is a disjunctive total dominating set of $G$ if every vertex is adjacent to a vertex of $S$ or has at least two vertices in $S$ at distance2 from it. The disjunctive total domination number, $γ^d_t(G)$ , is the minimum cardinality of such a set. We observe that $γ^d_t(G) \le γ_t(G)$ . We prove that if $G$ is a connected graph of order $n \ge 8$ , then $γ^d_t(G) \le 2(n-1)/3$ and we characterize the extremal graphs. It is known that if $G$ is a connected claw-free graph of order $n$ , then $γ_t(G) \le 2n/3$ and this upper bound is tight for arbitrarily large $n$ . We show this upper bound can be improved significantly for the disjunctive total domination number. We show that if $G$ is a connected claw-free graph of order $n > 10$ , then $γ^d_t(G) \le 4n/7$ and we characterize the graphs achieving equality in this bound.

preprint2014arXiv

Graphs with Large Disjunctive Total Domination Number

Let $G$ be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, $γ_t(G)$ . A set $S$ of vertices in $G$ is a disjunctive total dominating set of $G$ if every vertex is adjacent to a vertex of $S$ or has at least two vertices in $S$ at distance $2$ from it. The disjunctive total domination number, $γ^d_t(G)$ , is the minimum cardinality of such a set. We observe that $γ^d_t(G) \le γ_t(G)$ . Let $G$ be a connected graph on $n$ vertices with minimum degree $δ$ . It is known [J. Graph Theory 35 (2000), 21--45] that if $δ\ge 2$ and $n \ge 11$ , then $γ_t(G) \le 4n/7$ . Further [J. Graph Theory 46 (2004), 207--210] if $δ\ge 3$ , then $γ_t(G) \le n/2$ . We prove that if $δ\ge 2$ and $n \ge 8$ , then $γ^d_t(G) \le n/2$ and we characterize the extremal graphs.

preprint2014arXiv

Induced 2-Regular Subgraphs in k-Chordal Cubic Graphs

We show that a cubic graph $G$ of order $n$ has an induced $2$ -regular subgraph of order at least a) $\frac{n-2}{4-\frac{4}{k}}$ , if $G$ has no induced cycle of length more than $k$ , b) $\frac{5n+6}{8}$ , if $G$ has no induced cycle of length more than $4$ , and $n>6$ , and c) $\left(\frac{1}{4}+ε\right)n$ , if the independence number of $G$ is at most $\left(\frac{3}{8}-ε\right)n$ . To show the second result we give a precise structural description of cubic $4$ -chordal graphs.

preprint2014arXiv

Induced Cycles in Graphs

The maximum cardinality of an induced $2$ -regular subgraph of a graph $G$ is denoted by $c_{\rm ind}(G)$ . We prove that if $G$ is an $r$ -regular graph of order $n$ , then $c_{\rm ind}(G) \geq \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}$ and we prove that if $G$ is a cubic claw-free graph on order $n$ , then $c_{\rm ind}(G) > 13n/20$ and this bound is asymptotically best possible.

preprint2014arXiv

Trees with Large Neighborhood Total Domination Number

In this paper, we continue the study of neighborhood total domination in graphs first studied by Arumugam and Sivagnanam [Opuscula Math. 31 (2011), 519--531]. A neighborhood total dominating set, abbreviated NTD-set, in a graph $G$ is a dominating set $S$ in $G$ with the property that the subgraph induced by the open neighborhood of the set $S$ has no isolated vertex. The neighborhood total domination number, denoted by $\gnt(G)$, is the minimum cardinality of a NTD-set of $G$ . Every total dominating set is a NTD-set, implying that $γ(G) \le \gnt(G) \le \gt(G)$, where $γ(G)$ and $\gt(G)$ denote the domination and total domination numbers of $G$ , respectively. Arumugam and Sivagnanam posed the problem of characterizing the connected graphs $G$ of order $n \ge 3$ achieving the largest possible neighborhood total domination number, namely $\gnt(G) = \lceil n/2 \rceil$. A partial solution to this problem was presented by Henning and Rad [Discrete Applied Mathematics 161 (2013), 2460--2466] who showed that $5$ -cycles and subdivided stars are the only such graphs achieving equality in the bound when $n$ is odd. In this paper, we characterize the extremal trees achieving equality in the bound when $n$ is even. As a consequence of this tree characterization, a characterization of the connected graphs achieving equality in the bound when $n$ is even can be obtained noting that every spanning tree of such a graph belongs to our family of extremal trees.

preprint2013arXiv

Simultaneous Domination in Graphs

Let $F_1, F_2, ..., F_k$ be graphs with the same vertex set $V$ . A subset $S \subseteq V$ is a simultaneous dominating set if for every $i$ , $1 \le i \le k$ , every vertex of $F_i$ not in $S$ is adjacent to a vertex in $S$ in $F_i$ ; that is, the set $S$ is simultaneously a dominating set in each graph $F_i$ . The cardinality of a smallest such set is the simultaneous domination number. We present general upper bounds on the simultaneous domination number. We investigate bounds in special cases, including the cases when the factors, $F_i$ , are $r$ -regular or the disjoint union of copies of $K_r$ . Further we study the case when each factor is a cycle.

preprint2013arXiv

Total Transversals and Total Domination in Uniform Hypergraphs

The first three authors [European J. Combin. 33 (2012), 62--71] established a relationship between the transversal number and the domination number of uniform hypergraphs. In this paper, we establish a relationship between the total transversal number and the total domination number of uniform hypergraphs. We prove tight asymptotic upper bounds on the total transversal number in terms of the number of vertices, the number of edges, and the edge size.

preprint2011arXiv

Equality in a Linear Vizing-Like Relation that Relates the Size and Total Domination Number of a Graph

Let $G$ be a graph each component of which has order at least 3, and let $G$ have order $n$ , size $m$ , total domination number $γ_t$ and maximum degree $Δ(G)$ . Let $Δ= 3$ if $Δ(G) = 2$ and $Δ= Δ(G)$ if $Δ(G) \ge 3$ . It is known [J. Graph Theory 49 (2005), 285--290; J. Graph Theory 54 (2007), 350--353] that $m \le Δ(n- γ_t)$ . In this paper we characterize the extremal graphs $G$ satisfying $m = Δ(n- γ_t)$ .

preprint2011arXiv

Fair Domination in Graphs

A fair dominating set in a graph $G$ (or FD-set) is a dominating set $S$ such that all vertices not in $S$ are dominated by the same number of vertices from $S$ ; that is, every two vertices not in $S$ have the same number of neighbors in $S$ . The fair domination number, $fd(G)$ , of $G$ is the minimum cardinality of a FD-set. We present various results on the fair domination number of a graph. In particular, we show that if $G$ is a connected graph of order $n \ge 3$ with no isolated vertex, then $fd(G) \le n - 2$ , and we construct an infinite family of connected graphs achieving equality in this bound. We show that if $G$ is a maximal outerplanar graph, then $fd(G) < 17n/19$ . If $T$ is a tree of order $n \ge 2$ , then we prove that $fd(T) \le n/2$ with equality if and only if $T$ is the corona of a tree.

preprint2010arXiv

A Greedy Partition Lemma for Directed Domination

A directed dominating set in a directed graph $D$ is a set $S$ of vertices of $V$ such that every vertex $u \in V(D) \setminus S$ has an adjacent vertex $v$ in $S$ with $v$ directed to $u$ . The directed domination number of $D$ , denoted by $γ(D)$ , is the minimum cardinality of a directed dominating set in $D$ . The directed domination number of a graph $G$ , denoted $Γ_d(G)$ , which is the maximum directed domination number $γ(D)$ over all orientations $D$ of $G$ . The directed domination number of a complete graph was first studied by Erdös [Math. Gaz. 47 (1963), 220--222], albeit in disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if $α$ denotes the independence number of a graph $G$ , we show that $α\le Γ_d(G) \le α(1+2\ln(n/α))$ .

preprint2010arXiv

Directed Domination in Oriented Graphs

A directed dominating set in a directed graph $D$ is a set $S$ of vertices of $V$ such that every vertex $u \in V(D) \setminus S$ has an adjacent vertex $v$ in $S$ with $v$ directed to $u$ . The directed domination number of $D$ , denoted by $γ(D)$ , is the minimum cardinality of a directed dominating set in $D$ . The directed domination number of a graph $G$ , denoted $Γ_d(G)$ , which is the maximum directed domination number $γ(D)$ over all orientations $D$ of $G$ . The directed domination number of a complete graph was first studied by Erdös [Math. Gaz. 47 (1963), 220--222], albeit in disguised form. We extend this notion to directed domination of all graphs. If $α$ denotes the independence number of a graph $G$ , we show that if $G$ is a bipartite graph, we show that $Γ_d(G) = α$ . We present several lower and upper bounds on the directed domination number.

Michael A. Henning

Research overview

Is this your work?

36 publications

Total isolation game in graphs

Common domination perfect graphs

Minimal graphs with disjoint dominating and total dominating sets

Independent Domination in Subcubic Graphs

The Enclaveless Competition Game

Minimal graphs with disjoint dominating and paired-dominating sets

On accurate domination in graphs

(Total) Domination in Prisms

Bounds on the Game Transversal Number in Hypergraphs

Hereditary Equality of Domination and Exponential Domination

Locating-total dominating sets in twin-free graphs: a conjecture

Location-domination and matching in cubic graphs

Location-domination in line graphs

Relating Domination, Exponential Domination, and Porous Exponential Domination

Thoroughly Distributed Colorings

Tight lower bounds on the matching number in a graph with given maximum degree

Total Dominating Sequences in Graphs

Trees with Equal Total Domination and Game Total Domination Numbers

Largest Domination Number and Smallest Independence Number of Forests with given Degree Sequence

Locating-dominating sets in twin-free graphs

Matchings and Path Covers with applications to Domination in Graphs

Progress Towards the Total Domination Game 34\frac{3}{4}43​-Conjecture

Smallest Domination Number and Largest Independence Number of Graphs and Forests with given Degree Sequence

Transversals in 444-Uniform Hypergraphs

A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem

Disjunctive Total Domination in Graphs

Graphs with Large Disjunctive Total Domination Number

Induced 2-Regular Subgraphs in k-Chordal Cubic Graphs

Induced Cycles in Graphs

Trees with Large Neighborhood Total Domination Number

Simultaneous Domination in Graphs

Total Transversals and Total Domination in Uniform Hypergraphs

Equality in a Linear Vizing-Like Relation that Relates the Size and Total Domination Number of a Graph

Fair Domination in Graphs

A Greedy Partition Lemma for Directed Domination

Directed Domination in Oriented Graphs

See the researcher in context

Building this map preview

Progress Towards the Total Domination Game $\frac{3}{4}$ -Conjecture

Transversals in $4$ -Uniform Hypergraphs