ORIGINAL_ARTICLE
Paired-Domination Game Played in Graphs
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$.
http://comb-opt.azaruniv.ac.ir/article_13851_54f7f80cbf84f62b513594201751c9dc.pdf
2019-12-01T11:23:20
2020-08-05T11:23:20
79
94
10.22049/cco.2019.26437.1110
Paired-domination game
Paired-domination number
Domination game
M.A.
Henning
mahenning@uj.ac.za
true
1
University of Johannesburg
University of Johannesburg
University of Johannesburg
LEAD_AUTHOR
Teresa
Haynes
haynes@etsu.edu
true
2
East Tennessee State University;
Department of Mathematics
East Tennessee State University;
Department of Mathematics
East Tennessee State University;
Department of Mathematics
AUTHOR
ORIGINAL_ARTICLE
A characterization of trees with equal Roman 2-domination and Roman domination numbers
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.
http://comb-opt.azaruniv.ac.ir/article_13850_e789cd5a865ff841296b9739ea34aec1.pdf
2019-12-01T11:23:20
2020-08-05T11:23:20
95
107
10.22049/cco.2019.26364.1103
Roman ${2}$-domination
$2$-rainbow domination
Roman domination
tree
Ismael
Gonzalez Yero
ismael.gonzalez@uca.es
true
1
University of Cadiz
University of Cadiz
University of Cadiz
LEAD_AUTHOR
Abel
Cabrera Martinez
abel.cabrera@urv.cat
true
2
Universitat Rovira i Virgili
Universitat Rovira i Virgili
Universitat Rovira i Virgili
AUTHOR
ORIGINAL_ARTICLE
k-Efficient partitions of graphs
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.
http://comb-opt.azaruniv.ac.ir/article_13852_478f6dfde08ed596744a7773348bc29a.pdf
2019-12-01T11:23:20
2020-08-05T11:23:20
109
122
10.22049/cco.2019.26446.1112
domination
Efficient Domination
Distance-$k$ domination
M
Chellali
m_chellali@yahoo.com
true
1
LAMDA-RO Laboratory,
Department of Mathematics,
University of Blida,
B.P. 270, Blida, Algeria
LAMDA-RO Laboratory,
Department of Mathematics,
University of Blida,
B.P. 270, Blida, Algeria
LAMDA-RO Laboratory,
Department of Mathematics,
University of Blida,
B.P. 270, Blida, Algeria
AUTHOR
Teresa W.
Haynes
haynes@etsu.edu
true
2
Department of Mathematics and Statistics,
East Tennessee State University,
Johnson City, TN 37614-0002 USA
Department of Mathematics and Statistics,
East Tennessee State University,
Johnson City, TN 37614-0002 USA
Department of Mathematics and Statistics,
East Tennessee State University,
Johnson City, TN 37614-0002 USA
LEAD_AUTHOR
Stephen T.
Hedetniemi
hedet@clemson.edu
true
3
Professor Emeritus, School of Computing,
Clemson University,
Clemson, SC 29634 USA
Professor Emeritus, School of Computing,
Clemson University,
Clemson, SC 29634 USA
Professor Emeritus, School of Computing,
Clemson University,
Clemson, SC 29634 USA
AUTHOR
ORIGINAL_ARTICLE
t-Pancyclic Arcs in Tournaments
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$.
http://comb-opt.azaruniv.ac.ir/article_13853_b838a366c1fd609997bcb3c6948d3b01.pdf
2019-12-01T11:23:20
2020-08-05T11:23:20
123
130
10.22049/cco.2019.26333.1097
tournament
pancyclicity
t-pancyclic arc
Wei
Meng
mengwei@sxu.edu.cn
true
1
School of Mathematical Sciences, Shanxi University, 030006 Taiyuan, China
School of Mathematical Sciences, Shanxi University, 030006 Taiyuan, China
School of Mathematical Sciences, Shanxi University, 030006 Taiyuan, China
LEAD_AUTHOR
Steffen
Grueter
grueter@mathc.rwth-aachen.de
true
2
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
AUTHOR
Yubao
Guo
guo@mathc.rwth-aachen.de
true
3
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
AUTHOR
Manu
Kapolke
manu.kapolke@rwth-aachen.de
true
4
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
AUTHOR
Simon
Meesker
simon.meesker@rwth-aachen.de
true
5
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany
AUTHOR
ORIGINAL_ARTICLE
Girth, minimum degree, independence, and broadcast independence
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.
http://comb-opt.azaruniv.ac.ir/article_13855_71bcf08def5ae349eb3026397d2e7723.pdf
2019-12-01T11:23:20
2020-08-05T11:23:20
131
139
10.22049/cco.2019.26346.1098
broadcast independence
independence
packing
Stephane
Bessy
stephane.bessy@lirmm.fr
true
1
LIRMM
LIRMM
LIRMM
AUTHOR
Dieter
Rautenbach
dieter.rautenbach@uni-ulm.de
true
2
89069 Ulm, Germay
89069 Ulm, Germay
89069 Ulm, Germay
LEAD_AUTHOR
ORIGINAL_ARTICLE
On the edge-connectivity of C_4-free graphs
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.
http://comb-opt.azaruniv.ac.ir/article_13856_bcb7a6a4d152a475da2d7bdfa37a581e.pdf
2019-12-01T11:23:20
2020-08-05T11:23:20
141
150
10.22049/cco.2019.26453.1113
edge-connectivity
maximally edge-connected
graph
Peter
Dankelmann
pdankelmann@uj.ac.za
true
1
University of Johannesburg
University of Johannesburg
University of Johannesburg
LEAD_AUTHOR
ORIGINAL_ARTICLE
Different-Distance Sets in a Graph
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.
http://comb-opt.azaruniv.ac.ir/article_13863_aa060ff2474ed162917d785d51209d3c.pdf
2019-12-01T11:23:20
2020-08-05T11:23:20
151
171
10.22049/cco.2019.26467.1115
Different-Distance Sets
Cartesian products
graph
Jason T.
Hedetniemi
j.hedetniemi@wingate.edu
true
1
Wingate University
Wingate University
Wingate University
LEAD_AUTHOR
Stephen T.
Hedetniemi
hedet@clemson.edu
true
2
Department of Mathematics,
University of Johannesburg,
Auckland Park, South Africa
Department of Mathematics,
University of Johannesburg,
Auckland Park, South Africa
Department of Mathematics,
University of Johannesburg,
Auckland Park, South Africa
AUTHOR
Renu C.
Renu C. Laskar
rclsk@clemson.edu
true
3
Clemson University
Clemson University
Clemson University
AUTHOR
Henry Martyn
Mulder
hmmulder@ese.eur.nl
true
4
Erasmus Universiteit
Erasmus Universiteit
Erasmus Universiteit
AUTHOR
ORIGINAL_ARTICLE
Directed domination in oriented hypergraphs
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$.
http://comb-opt.azaruniv.ac.ir/article_13862_c7627d5b92f3a70d4057950f050d2d68.pdf
2019-12-01T11:23:20
2020-08-05T11:23:20
173
183
10.22049/cco.2019.26466.1114
domination
directed domination
hypergraph
Yair
Caro
yacaro@kvgeva.org.il
true
1
University of Haifa-Oranim
University of Haifa-Oranim
University of Haifa-Oranim
AUTHOR
Adriana
Hansberg
ahansberg@im.unam.mx
true
2
76230 Queretaro, Mexico
76230 Queretaro, Mexico
76230 Queretaro, Mexico
LEAD_AUTHOR
ORIGINAL_ARTICLE
On trees with equal Roman domination and outer-independent Roman domination numbers
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)$.
http://comb-opt.azaruniv.ac.ir/article_13865_778d0f97a1447e3fa6dcc653002a9d16.pdf
2019-12-01T11:23:20
2020-08-05T11:23:20
185
199
10.22049/cco.2019.26319.1095
Roman domination
outer-independent Roman domination
tree
Seyed Mahmoud
Sheikholeslami
s.m.sheikholeslami@azaruniv.edu
true
1
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
LEAD_AUTHOR
Sakineh
Nazari-Moghaddam
s.nazari@azaruniv.ac.ir
true
2
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
AUTHOR
ORIGINAL_ARTICLE
On Hop Roman Domination in Trees
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.
http://comb-opt.azaruniv.ac.ir/article_13874_62d388aaf42e0893e140772d7fa34403.pdf
2019-12-01T11:23:20
2020-08-05T11:23:20
201
208
10.22049/cco.2019.26469.1116
hop dominating set
connected hop dominating set
hop Roman dominating function
Nader
Jafari Rad
n.jafarirad@gmail.com
true
1
Separtment of Mathemtics, Shahed University, Tehran, Iran
Separtment of Mathemtics, Shahed University, Tehran, Iran
Separtment of Mathemtics, Shahed University, Tehran, Iran
LEAD_AUTHOR
Abolfazl
Poureidi
a.poureidi@gmail.com
true
2
Department of Mathematics, Shahrood University of Technology, Shahrood, Iran
Department of Mathematics, Shahrood University of Technology, Shahrood, Iran
Department of Mathematics, Shahrood University of Technology, Shahrood, Iran
AUTHOR