### فهرست مطالب

• Volume:4 Issue:2, 2019
• تاریخ انتشار: 1398/04/26
• تعداد عناوین: 10
|
• M.A. Henning *, Teresa Haynes Pages 79-94
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\$.
Keywords: Paired-domination game, Paired-domination number, Domination game
• Ismael Gonzalez Yero *, Abel Cabrera Martinez Pages 95-107

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, 2-rainbow domination, Roman domination, tree
• M Chellali, Teresa W. Haynes *, Stephen T. Hedetniemi Pages 109-122

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
• Wei Meng *, Steffen Grueter, Yubao Guo, Manu Kapolke, Simon Meesker Pages 123-130
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\$.
Keywords: tournament, pancyclicity, t-pancyclic arc
• Stephane Bessy, Dieter Rautenbach * Pages 131-139
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.
• Peter Dankelmann * Pages 141-150
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.
Keywords: edge-connectivity, maximally edge-connected, graph
• Jason T. Hedetniemi *, Stephen T. Hedetniemi, Renu C. Renu C. Laskar, Henry Martyn Mulder Pages 151-171
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.
Keywords: Di fferent-Distance Sets, Cartesian products, graph
• Yair Caro, Adriana Hansberg * Pages 173-183
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\$.
Keywords: domination, directed domination, hypergraph
• Seyed Mahmoud Sheikholeslami *, Sakineh Nazari Moghaddam Pages 185-199

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)\$.

Keywords: Roman domination, outer-independent Roman domination, tree