Communications in Combinatorics and Optimization
Volume:4 Issue: 2, Summer and Autumn 2019

In this paper, we continue the study of the domination game in graphs introduced by Bre{v{s}}ar, Klav{v{z}}ar, and Rall. We study the paired-domination version of the domination game which adds a matching dimension to the game. This game is played on a graph $G$ by two players, named Dominator and Pairer. They alternately take turns choosing vertices of $G$ such that each vertex chosen by Dominator dominates at least one vertex not dominated by the vertices previously chosen, while each vertex chosen by Pairer is a vertex not previously chosen that is a neighbor of the vertex played by Dominator on his previous move. This process eventually produces a paired-dominating set of vertices of $G$; that is, a dominating set in $G$ that induces a subgraph that contains a perfect matching. Dominator wishes to minimize the number of vertices chosen, while Pairer wishes to maximize it. The game paired-domination number $gpr(G)$ of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. Let $G$ be a graph on $n$ vertices with minimum degree at least~$2$. We show that $gpr(G) le frac{4}{5}n$, and this bound is tight. Further we show that if $G$ is $(C_4,C_5)$-free, then $gpr(G) le frac{3}{4}n$, where a graph is $(C_4,C_5)$-free if it has no induced $4$-cycle or $5$-cycle. If $G$ is $2$-connected and bipartite or if $G$ is $2$-connected and the sum of every two adjacent vertices in $G$ is at least~$5$, then we show that $gpr(G) le frac{3}{4}n$.

Given a graph $G=(V,E)$ and a vertex $v in V$, by $N(v)$ we represent the open neighbourhood of $v$. Let $f:Vrightarrow {0,1,2}$ be a function on $G$. The weight of $f$ is $omega(f)=sum_{vin V}f(v)$ and let $V_i={vin V colon f(v)=i}$, for $i=0,1,2$. The function $f$ is said to bebegin{itemize}item a Roman ${2}$-dominating function, if for every vertex $vin V_0$, $sum_{uin N(v)}f(u)geq 2$. The Roman ${2}$-domination number, denoted by $gamma_{{R2}}(G)$, is the minimum weight among all Roman ${2}$-dominating functions on $G$;item a Roman dominating function, if for every vertex $vin V_0$ there exists $uin N(v)cap V_2$. The Roman domination number, denoted by $gamma_R(G)$, is the minimum weight among all Roman dominating functions on $G$.end{itemize}It is known that for any graph $G$, $gamma_{{R2}}(G)leq gamma_R(G)$. In this paper, we characterize the trees $T$ that satisfy the equality above.

A set $S = {u_1,u_2, ldots, u_t}$ of vertices of $G$ is an efficientdominating set if every vertex of $G$ is dominated exactly once by thevertices of $S$. Letting $U_i$ denote the set of vertices dominated by $u_i$%, we note that ${U_1, U_2, ldots U_t}$ is a partition of the vertex setof $G$ and that each $U_i$ contains the vertex $u_i$ and all the vertices atdistance~1 from it in $G$. In this paper, we generalize the concept ofefficient domination by considering $k$-efficient domination partitions ofthe vertex set of $G$, where each element of the partition is a setconsisting of a vertex $u_i$ and all the vertices at distance~$d_i$ from it,where $d_i in {0,1, ldots, k}$. For any integer $k geq 0$, the $k$%-efficient domination number of $G$ equals the minimum order of a $k$%-efficient partition of $G$. We determine bounds on the $k$-efficientdomination number for general graphs, and for $k in {1,2}$, we give exactvalues for some graph families. Complexity results are also obtained.

Let $T$ be a non-trivial tournament. An arc is emph{$t$-pancyclic} in $T$, if it is contained in a cycle of length $ell$ for every $tleq ell leq |V(T)|$. Let $p^t(T)$ denote the number of $t$-pancyclic arcs in $T$ and $h^t(T)$ the maximum number of $t$-pancyclic arcs contained in the same Hamiltonian cycle of $T$. Moon ({em J. Combin. Inform. System Sci.}, {bf 19} (1994), 207-214) showed that $h^3(T)geq3$ for any non-trivial strong tournament $T$ and characterized the tournaments with $h^3(T)= 3$. In this paper, we generalize Moon's theorem by showing that $h^t(T)geq t$ for every $3leq tleq |V(T)|$ and characterizing the tournaments with $h^t(T)= t$. We also present all tournaments which fulfill $p^t(T)= t$.

An independent broadcast on a connected graph $G$is a function $f:V(G)to mathbb{N}_0$such that, for every vertex $x$ of $G$, the value $f(x)$ is at most the eccentricity of $x$ in $G$,and $f(x)>0$ implies that $f(y)=0$ for every vertex $y$ of $G$ within distance at most $f(x)$ from $x$.The broadcast independence number $alpha_b(G)$ of $G$is the largest weight $sumlimits_{xin V(G)}f(x)$of an independent broadcast $f$ on $G$.It is known that $alpha(G)leq alpha_b(G)leq 4alpha(G)$for every connected graph $G$,where $alpha(G)$ is the independence number of $G$.If $G$ has girth $g$ and minimum degree $delta$,we show that $alpha_b(G)leq 2alpha(G)$provided that $ggeq 6$ and $deltageq 3$or that $ggeq 4$ and $deltageq 5$.Furthermore, we show that, for every positive integer $k$,there is a connected graph $G$ of girth at least $k$ and minimum degree at least $k$ such that $alpha_b(G)geq 2left(1-frac{1}{k}right)alpha(G)$.Our results imply that lower bounds on the girth and the minimum degreeof a connected graph $G$can lower the fraction $frac{alpha_b(G)}{alpha(G)}$from $4$ below $2$, but not any further.

Let $G$ be a connected graph of order $n$ and minimum degree $delta(G)$.The edge-connectivity $lambda(G)$ of $G$ is the minimum numberof edges whose removal renders $G$ disconnected. It is well-known that$lambda(G) leq delta(G)$,and if $lambda(G)=delta(G)$, then$G$ is said to be maximally edge-connected. A classical resultby Chartrand gives the sufficient condition $delta(G) geq frac{n-1}{2}$for a graph to be maximally edge-connected. We give lower bounds onthe edge-connectivity of graphs not containing $4$-cycles that implythat forgraphs not containing a $4$-cycle Chartrand's condition can be relaxedto $delta(G) geq sqrt{frac{n}{2}} +1$, and if the graphalso contains no $5$-cycle, or if it has girth at least six,then this condition can be relaxed further,by a factor of approximately $sqrt{2}$. We construct graphsto show that for an infinite number of values of $n$both sufficient conditions are best possible apart froma small additive constant.

A set of vertices $S$ in a connected graph $G$ is a different-distance set if, for any vertex $w$ outside $S$, no two vertices in $S$ have the same distance to $w$.The lower and upper different-distance number of a graph are the order of a smallest, respectively largest, maximal different-distance set.We prove that a different-distance set induces either a special type of path or an independent set. We present properties of different-distance sets, and consider the different-distance numbers of paths, cycles, Cartesian products of bipartite graphs, and Cartesian products of complete graphs. We conclude with some open problems and questions.

ErdH{o}s [On Sch"utte problem, Math. Gaz. 47 (1963)] proved that every tournament on $n$ vertices has a directed dominating set of at most $log (n+1)$ vertices, where $log$ is the logarithm to base $2$. He also showed that there is a tournament on $n$ vertices with no directed domination set of cardinality less than $log n - 2 log log n + 1$. This notion of directed domination number has been generalized to arbitrary graphs by Caro and Henning in [Directed domination in oriented graphs, Discrete Appl. Math. (2012) 160:7--8.]. However, the generalization to directed r-uniform hypergraphs seems to be rare. Among several results, we prove the following upper and lower bounds on $ora{Gamma}_{r-1}(H(n,r))$, the upper directed $(r-1)$-domination number of the complete $r$-uniform hypergraph on $n$ vertices $H(n,r)$, which is the main theorem of this paper:[c (ln n)^{frac{1}{r-1}} le ora{Gamma}_{r-1}(H(n,r)) le C ln n,]where $r$ is a positive integer and $c= c(r) > 0$ and $C = C(r) > 0$ are constants depending on $r$.

A Roman dominating function (RDF) on a graph $G$ is a function $f : V (G) to {0, 1, 2}$satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least onevertex $v$ for which $f(v) = 2$. A Roman dominating function $f$ is called an outer-independentRoman dominating function (OIRDF) on $G$ if the set ${vin Vmid f(v)=0}$ is independent.The (outer-independent) Roman domination number $gamma_{R}(G)$ ($gamma_{oiR}(G)$) is the minimum weightof an RDF (OIRDF) on $G$. Clearly for any graph $G$, $gamma_{R}(G)le gamma_{oiR}(G)$. In this paper,we provide a constructive characterization of trees $T$ with $gamma_{R}(T)=gamma_{oiR}(T)$.

‎Let $G=(V,E)$ be a graph‎. ‎A subset $Ssubset V$ is a hop dominating set‎‎if every vertex outside $S$ is at distance two from a vertex of‎‎$S$‎. ‎A hop dominating set $S$ which induces a connected subgraph‎ ‎is called a connected hop dominating set of $G$‎. ‎The‎‎connected hop domination number of $G$‎, ‎$ gamma_{ch}(G)$,‎‎‎ ‎is the minimum cardinality of a connected hop‎‎dominating set of $G$‎. ‎A hop‎‎Roman dominating function (HRDF) of a graph $G$ is a function $‎‎f‎: ‎V(G)longrightarrow {0‎, ‎1‎, ‎2} $ having the property that‎‎for every vertex $ v in V $ with $ f(v) = 0 $ there is a‎‎vertex $ u $ with $ f(u)=2 $ and $ d(u,v)=2 $‎.‎The weight of‎‎an HRDF $ f $ is the sum $f(V) = sum_{vin V} f(v) $‎. ‎The‎‎minimum weight of an HRDF on $ G $ is called the hop Roman‎‎domination number of $ G $ and is denoted by $ gamma_{hR}(G)‎‎$‎. ‎We give an algorithm‎‎that decides whether $gamma_{hR}(T)=2gamma_{ch}(T)$ for a given‎‎tree $T$.‎‎{bf Keywords:} hop dominating set‎, ‎connected hop dominating set‎, ‎hop Roman dominating‎‎function‎.