Paired-Domination Game Played in Graphs
M.A.
Henning
University of Johannesburg
author
Teresa
Haynes
East Tennessee State University;
Department of Mathematics
author
text
article
2019
eng
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$.
Communications in Combinatorics and Optimization
Azarbaijan Shahid Madani University
2538-2128
4
v.
2
no.
2019
79
94
http://comb-opt.azaruniv.ac.ir/article_13851_54f7f80cbf84f62b513594201751c9dc.pdf
dx.doi.org/10.22049/cco.2019.26437.1110
A characterization of trees with equal Roman 2-domination and Roman domination numbers
Ismael
Gonzalez Yero
University of Cadiz
author
Abel
Cabrera Martinez
Universitat Rovira i Virgili
author
text
article
2019
eng
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.
Communications in Combinatorics and Optimization
Azarbaijan Shahid Madani University
2538-2128
4
v.
2
no.
2019
95
107
http://comb-opt.azaruniv.ac.ir/article_13850_e789cd5a865ff841296b9739ea34aec1.pdf
dx.doi.org/10.22049/cco.2019.26364.1103
k-Efficient partitions of graphs
M
Chellali
LAMDA-RO Laboratory,
Department of Mathematics,
University of Blida,
B.P. 270, Blida, Algeria
author
Teresa W.
Haynes
Department of Mathematics and Statistics,
East Tennessee State University,
Johnson City, TN 37614-0002 USA
author
Stephen T.
Hedetniemi
Professor Emeritus, School of Computing,
Clemson University,
Clemson, SC 29634 USA
author
text
article
2019
eng
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.
Communications in Combinatorics and Optimization
Azarbaijan Shahid Madani University
2538-2128
4
v.
2
no.
2019
109
122
http://comb-opt.azaruniv.ac.ir/article_13852_478f6dfde08ed596744a7773348bc29a.pdf
dx.doi.org/10.22049/cco.2019.26446.1112
t-Pancyclic Arcs in Tournaments
Wei
Meng
School of Mathematical Sciences, Shanxi University, 030006 Taiyuan, China
author
Steffen
Grueter
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
author
Yubao
Guo
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
author
Manu
Kapolke
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
author
Simon
Meesker
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
author
text
article
2019
eng
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$.
Communications in Combinatorics and Optimization
Azarbaijan Shahid Madani University
2538-2128
4
v.
2
no.
2019
123
130
http://comb-opt.azaruniv.ac.ir/article_13853_b838a366c1fd609997bcb3c6948d3b01.pdf
dx.doi.org/10.22049/cco.2019.26333.1097
Girth, minimum degree, independence, and broadcast independence
Stephane
Bessy
LIRMM
author
Dieter
Rautenbach
89069 Ulm, Germay
author
text
article
2019
eng
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.
Communications in Combinatorics and Optimization
Azarbaijan Shahid Madani University
2538-2128
4
v.
2
no.
2019
131
139
http://comb-opt.azaruniv.ac.ir/article_13855_71bcf08def5ae349eb3026397d2e7723.pdf
dx.doi.org/10.22049/cco.2019.26346.1098
On the edge-connectivity of C_4-free graphs
Peter
Dankelmann
University of Johannesburg
author
text
article
2019
eng
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.
Communications in Combinatorics and Optimization
Azarbaijan Shahid Madani University
2538-2128
4
v.
2
no.
2019
141
150
http://comb-opt.azaruniv.ac.ir/article_13856_bcb7a6a4d152a475da2d7bdfa37a581e.pdf
dx.doi.org/10.22049/cco.2019.26453.1113
Different-Distance Sets in a Graph
Jason T.
Hedetniemi
Wingate University
author
Stephen T.
Hedetniemi
Department of Mathematics,
University of Johannesburg,
Auckland Park, South Africa
author
Renu C.
Renu C. Laskar
Clemson University
author
Henry Martyn
Mulder
Erasmus Universiteit
author
text
article
2019
eng
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.
Communications in Combinatorics and Optimization
Azarbaijan Shahid Madani University
2538-2128
4
v.
2
no.
2019
151
171
http://comb-opt.azaruniv.ac.ir/article_13863_aa060ff2474ed162917d785d51209d3c.pdf
dx.doi.org/10.22049/cco.2019.26467.1115
Directed domination in oriented hypergraphs
Yair
Caro
University of Haifa-Oranim
author
Adriana
Hansberg
76230 Queretaro, Mexico
author
text
article
2019
eng
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$.
Communications in Combinatorics and Optimization
Azarbaijan Shahid Madani University
2538-2128
4
v.
2
no.
2019
173
183
http://comb-opt.azaruniv.ac.ir/article_13862_c7627d5b92f3a70d4057950f050d2d68.pdf
dx.doi.org/10.22049/cco.2019.26466.1114
On trees with equal Roman domination and outer-independent Roman domination numbers
Seyed Mahmoud
Sheikholeslami
Azarbaijan Shahid Madani University
author
Sakineh
Nazari-Moghaddam
Azarbaijan Shahid Madani University
author
text
article
2019
eng
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)$.
Communications in Combinatorics and Optimization
Azarbaijan Shahid Madani University
2538-2128
4
v.
2
no.
2019
185
199
http://comb-opt.azaruniv.ac.ir/article_13865_778d0f97a1447e3fa6dcc653002a9d16.pdf
dx.doi.org/10.22049/cco.2019.26319.1095
On Hop Roman Domination in Trees
Nader
Jafari Rad
Separtment of Mathemtics, Shahed University, Tehran, Iran
author
Abolfazl
Poureidi
Department of Mathematics, Shahrood University of Technology, Shahrood, Iran
author
text
article
2019
eng
Let $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.
Communications in Combinatorics and Optimization
Azarbaijan Shahid Madani University
2538-2128
4
v.
2
no.
2019
201
208
http://comb-opt.azaruniv.ac.ir/article_13874_62d388aaf42e0893e140772d7fa34403.pdf
dx.doi.org/10.22049/cco.2019.26469.1116