فهرست مطالب
 Volume:4 Issue:2, 2019
 تاریخ انتشار: 1398/04/26
 تعداد عناوین: 10

Pages 7994In 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 paireddomination 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 paireddominating 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 paireddomination 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$.Keywords: Paireddomination game, Paireddomination number, Domination game

Pages 95107
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.
Keywords: Roman {2}domination, 2rainbow domination, Roman domination, tree 
Pages 109122
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.
Keywords: domination, Efficient Domination, Distance k domination 
Pages 123130Let $T$ be a nontrivial 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), 207214) showed that $h^3(T)geq3$ for any nontrivial 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$.Keywords: tournament, pancyclicity, tpancyclic arc

Pages 131139An 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(1frac{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.Keywords: broadcast independence, independence, packing

Pages 141150Let $G$ be a connected graph of order $n$ and minimum degree $delta(G)$.The edgeconnectivity $lambda(G)$ of $G$ is the minimum numberof edges whose removal renders $G$ disconnected. It is wellknown that$lambda(G) leq delta(G)$,and if $lambda(G)=delta(G)$, then$G$ is said to be maximally edgeconnected. A classical resultby Chartrand gives the sufficient condition $delta(G) geq frac{n1}{2}$for a graph to be maximally edgeconnected. We give lower bounds onthe edgeconnectivity 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.Keywords: edgeconnectivity, maximally edgeconnected, graph

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

Pages 173183ErdH{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:78.]. However, the generalization to directed runiform hypergraphs seems to be rare. Among several results, we prove the following upper and lower bounds on $ora{Gamma}_{r1}(H(n,r))$, the upper directed $(r1)$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}{r1}} le ora{Gamma}_{r1}(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$.Keywords: domination, directed domination, hypergraph

Pages 185199
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 outerindependentRoman dominating function (OIRDF) on $G$ if the set ${vin Vmid f(v)=0}$ is independent.The (outerindependent) 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)$.
Keywords: Roman domination, outerindependent Roman domination, tree 
Pages 201208Let $G=(V,E)$ be a graph. A subset $Ssubset V$ is a hop dominating setif 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$. Theconnected hop domination number of $G$, $ gamma_{ch}(G)$, is the minimum cardinality of a connected hopdominating set of $G$. A hopRoman dominating function (HRDF) of a graph $G$ is a function $f: V(G)longrightarrow {0, 1, 2} $ having the property thatfor every vertex $ v in V $ with $ f(v) = 0 $ there is avertex $ u $ with $ f(u)=2 $ and $ d(u,v)=2 $.The weight ofan HRDF $ f $ is the sum $f(V) = sum_{vin V} f(v) $. Theminimum weight of an HRDF on $ G $ is called the hop Romandomination number of $ G $ and is denoted by $ gamma_{hR}(G)$. We give an algorithmthat decides whether $gamma_{hR}(T)=2gamma_{ch}(T)$ for a giventree $T$.{bf Keywords:} hop dominating set, connected hop dominating set, hop Roman dominatingfunction.Keywords: hop dominating set, connected hop dominating set, hop Roman dominating function