2020-08-05T02:52:21Z
http://comb-opt.azaruniv.ac.ir/?_action=export&rf=summon&issue=2279
Communications in Combinatorics and Optimization
Commun. Comb. Optim.
2538-2128
2538-2128
2019
4
2
Paired-Domination Game Played in Graphs
M.A.
Henning
Teresa
Haynes
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$.
Paired-domination game
Paired-domination number
Domination game
2019
12
01
79
94
http://comb-opt.azaruniv.ac.ir/article_13851_54f7f80cbf84f62b513594201751c9dc.pdf
Communications in Combinatorics and Optimization
Commun. Comb. Optim.
2538-2128
2538-2128
2019
4
2
A characterization of trees with equal Roman 2-domination and Roman domination numbers
Ismael
Gonzalez Yero
Abel
Cabrera Martinez
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 be<br />begin{itemize}<br />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$;<br />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$.<br />end{itemize}<br />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.
Roman ${2}$-domination
$2$-rainbow domination
Roman domination
tree
2019
12
01
95
107
http://comb-opt.azaruniv.ac.ir/article_13850_e789cd5a865ff841296b9739ea34aec1.pdf
Communications in Combinatorics and Optimization
Commun. Comb. Optim.
2538-2128
2538-2128
2019
4
2
k-Efficient partitions of graphs
M
Chellali
Teresa W.
Haynes
Stephen T.
Hedetniemi
A set $S = {u_1,u_2, ldots, u_t}$ of vertices of $G$ is an efficient<br />dominating set if every vertex of $G$ is dominated exactly once by the<br />vertices of $S$. Letting $U_i$ denote the set of vertices dominated by $u_i$%<br />, we note that ${U_1, U_2, ldots U_t}$ is a partition of the vertex set<br />of $G$ and that each $U_i$ contains the vertex $u_i$ and all the vertices at<br />distance~1 from it in $G$. In this paper, we generalize the concept of<br />efficient domination by considering $k$-efficient domination partitions of<br />the vertex set of $G$, where each element of the partition is a set<br />consisting of a vertex $u_i$ and all the vertices at distance~$d_i$ from it,<br />where $d_i in {0,1, ldots, k}$. For any integer $k geq 0$, the $k$%<br />-efficient domination number of $G$ equals the minimum order of a $k$%<br />-efficient partition of $G$. We determine bounds on the $k$-efficient<br />domination number for general graphs, and for $k in {1,2}$, we give exact<br />values for some graph families. Complexity results are also obtained.
domination
Efficient Domination
Distance-$k$ domination
2019
12
01
109
122
http://comb-opt.azaruniv.ac.ir/article_13852_478f6dfde08ed596744a7773348bc29a.pdf
Communications in Combinatorics and Optimization
Commun. Comb. Optim.
2538-2128
2538-2128
2019
4
2
t-Pancyclic Arcs in Tournaments
Wei
Meng
Steffen
Grueter
Yubao
Guo
Manu
Kapolke
Simon
Meesker
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$.
tournament
pancyclicity
t-pancyclic arc
2019
12
01
123
130
http://comb-opt.azaruniv.ac.ir/article_13853_b838a366c1fd609997bcb3c6948d3b01.pdf
Communications in Combinatorics and Optimization
Commun. Comb. Optim.
2538-2128
2538-2128
2019
4
2
Girth, minimum degree, independence, and broadcast independence
Stephane
Bessy
Dieter
Rautenbach
An independent broadcast on a connected graph $G$<br />is a function $f:V(G)to mathbb{N}_0$<br />such that, for every vertex $x$ of $G$, <br />the value $f(x)$ is at most the eccentricity of $x$ in $G$,<br />and $f(x)>0$ implies that $f(y)=0$ <br />for every vertex $y$ of $G$ within distance at most $f(x)$ from $x$.<br />The broadcast independence number $alpha_b(G)$ of $G$<br />is the largest weight $sumlimits_{xin V(G)}f(x)$<br />of an independent broadcast $f$ on $G$.<br /><br />It is known that $alpha(G)leq alpha_b(G)leq 4alpha(G)$<br />for every connected graph $G$,<br />where $alpha(G)$ is the independence number of $G$.<br />If $G$ has girth $g$ and minimum degree $delta$,<br />we show that <br />$alpha_b(G)leq 2alpha(G)$<br />provided that <br />$ggeq 6$ and $deltageq 3$<br />or that $ggeq 4$ and $deltageq 5$.<br />Furthermore, <br />we show that, <br />for every positive integer $k$,<br />there is a connected graph $G$ of girth at least $k$ and minimum degree at least $k$ <br />such that <br />$alpha_b(G)geq 2left(1-frac{1}{k}right)alpha(G)$.<br />Our results imply that <br />lower bounds on the girth and the minimum degree<br />of a connected graph $G$<br />can lower the fraction $frac{alpha_b(G)}{alpha(G)}$<br />from $4$ below $2$, but not any further.
broadcast independence
independence
packing
2019
12
01
131
139
http://comb-opt.azaruniv.ac.ir/article_13855_71bcf08def5ae349eb3026397d2e7723.pdf
Communications in Combinatorics and Optimization
Commun. Comb. Optim.
2538-2128
2538-2128
2019
4
2
On the edge-connectivity of C_4-free graphs
Peter
Dankelmann
Let $G$ be a connected graph of order $n$ and minimum degree $delta(G)$.<br />The edge-connectivity $lambda(G)$ of $G$ is the minimum number<br />of edges whose removal renders $G$ disconnected. It is well-known that<br />$lambda(G) leq delta(G)$,<br />and if $lambda(G)=delta(G)$, then<br />$G$ is said to be maximally edge-connected. A classical result<br />by Chartrand gives the sufficient condition $delta(G) geq frac{n-1}{2}$<br />for a graph to be maximally edge-connected. We give lower bounds on<br />the edge-connectivity of graphs not containing $4$-cycles that imply<br />that for<br />graphs not containing a $4$-cycle Chartrand's condition can be relaxed<br />to $delta(G) geq sqrt{frac{n}{2}} +1$, and if the graph<br />also contains no $5$-cycle, or if it has girth at least six,<br />then this condition can be relaxed further,<br />by a factor of approximately $sqrt{2}$. We construct graphs<br />to show that for an infinite number of values of $n$<br />both sufficient conditions are best possible apart from<br />a small additive constant.
edge-connectivity
maximally edge-connected
graph
2019
12
01
141
150
http://comb-opt.azaruniv.ac.ir/article_13856_bcb7a6a4d152a475da2d7bdfa37a581e.pdf
Communications in Combinatorics and Optimization
Commun. Comb. Optim.
2538-2128
2538-2128
2019
4
2
Different-Distance Sets in a Graph
Jason T.
Hedetniemi
Stephen T.
Hedetniemi
Renu C.
Renu C. Laskar
Henry Martyn
Mulder
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$.<br />The lower and upper different-distance number of a graph are the order of a smallest, respectively largest, maximal different-distance set.<br />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.
Different-Distance Sets
Cartesian products
graph
2019
12
01
151
171
http://comb-opt.azaruniv.ac.ir/article_13863_aa060ff2474ed162917d785d51209d3c.pdf
Communications in Combinatorics and Optimization
Commun. Comb. Optim.
2538-2128
2538-2128
2019
4
2
Directed domination in oriented hypergraphs
Yair
Caro
Adriana
Hansberg
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:<br />[c (ln n)^{frac{1}{r-1}} le ora{Gamma}_{r-1}(H(n,r)) le C ln n,]<br />where $r$ is a positive integer and $c= c(r) > 0$ and $C = C(r) > 0$ are constants depending on $r$.
domination
directed domination
hypergraph
2019
12
01
173
183
http://comb-opt.azaruniv.ac.ir/article_13862_c7627d5b92f3a70d4057950f050d2d68.pdf
Communications in Combinatorics and Optimization
Commun. Comb. Optim.
2538-2128
2538-2128
2019
4
2
On trees with equal Roman domination and outer-independent Roman domination numbers
Seyed Mahmoud
Sheikholeslami
Sakineh
Nazari-Moghaddam
A Roman dominating function (RDF) on a graph $G$ is a function $f : V (G) to {0, 1, 2}$<br />satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one<br />vertex $v$ for which $f(v) = 2$. A Roman dominating function $f$ is called an outer-independent<br />Roman dominating function (OIRDF) on $G$ if the set ${vin Vmid f(v)=0}$ is independent.<br />The (outer-independent) Roman domination number $gamma_{R}(G)$ ($gamma_{oiR}(G)$) is the minimum weight<br />of an RDF (OIRDF) on $G$. Clearly for any graph $G$, $gamma_{R}(G)le gamma_{oiR}(G)$. In this paper,<br />we provide a constructive characterization of trees $T$ with $gamma_{R}(T)=gamma_{oiR}(T)$.
Roman domination
outer-independent Roman domination
tree
2019
12
01
185
199
http://comb-opt.azaruniv.ac.ir/article_13865_778d0f97a1447e3fa6dcc653002a9d16.pdf
Communications in Combinatorics and Optimization
Commun. Comb. Optim.
2538-2128
2538-2128
2019
4
2
On Hop Roman Domination in Trees
Nader
Jafari Rad
Abolfazl
Poureidi
Let $G=(V,E)$ be a graph. A subset $Ssubset V$ is a hop dominating set<br />if every vertex outside $S$ is at distance two from a vertex of<br />$S$. A hop dominating set $S$ which induces a connected subgraph<br /> is called a connected hop dominating set of $G$. The<br />connected hop domination number of $G$, $ gamma_{ch}(G)$, is the minimum cardinality of a connected hop<br />dominating set of $G$. A hop<br />Roman dominating function (HRDF) of a graph $G$ is a function $<br />f: V(G)longrightarrow {0, 1, 2} $ having the property that<br />for every vertex $ v in V $ with $ f(v) = 0 $ there is a<br />vertex $ u $ with $ f(u)=2 $ and $ d(u,v)=2 $.<br />The weight of<br />an HRDF $ f $ is the sum $f(V) = sum_{vin V} f(v) $. The<br />minimum weight of an HRDF on $ G $ is called the hop Roman<br />domination number of $ G $ and is denoted by $ gamma_{hR}(G)<br />$. We give an algorithm<br />that decides whether $gamma_{hR}(T)=2gamma_{ch}(T)$ for a given<br />tree $T$.<br />{bf Keywords:} hop dominating set, connected hop dominating set, hop Roman dominating<br />function.
hop dominating set
connected hop dominating set
hop Roman dominating function
2019
12
01
201
208
http://comb-opt.azaruniv.ac.ir/article_13874_62d388aaf42e0893e140772d7fa34403.pdf