@article {
author = {Henning, M.A. and Haynes, Teresa},
title = {Paired-Domination Game Played in Graphs},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {79-94},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26437.1110},
abstract = {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},
url = {http://comb-opt.azaruniv.ac.ir/article_13851.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13851_54f7f80cbf84f62b513594201751c9dc.pdf}
}
@article {
author = {Gonzalez Yero, Ismael and Cabrera Martinez, Abel},
title = {A characterization of trees with equal Roman 2-domination and Roman domination numbers},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {95-107},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26364.1103},
abstract = {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},
url = {http://comb-opt.azaruniv.ac.ir/article_13850.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13850_e789cd5a865ff841296b9739ea34aec1.pdf}
}
@article {
author = {Chellali, M and Haynes, Teresa W. and Hedetniemi, Stephen T.},
title = {k-Efficient partitions of graphs},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {109-122},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26446.1112},
abstract = {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},
url = {http://comb-opt.azaruniv.ac.ir/article_13852.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13852_478f6dfde08ed596744a7773348bc29a.pdf}
}
@article {
author = {Meng, Wei and Grueter, Steffen and Guo, Yubao and Kapolke, Manu and Meesker, Simon},
title = {t-Pancyclic Arcs in Tournaments},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {123-130},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26333.1097},
abstract = {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},
url = {http://comb-opt.azaruniv.ac.ir/article_13853.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13853_b838a366c1fd609997bcb3c6948d3b01.pdf}
}
@article {
author = {Bessy, Stephane and Rautenbach, Dieter},
title = {Girth, minimum degree, independence, and broadcast independence},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {131-139},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26346.1098},
abstract = {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.},
keywords = {broadcast independence,independence,packing},
url = {http://comb-opt.azaruniv.ac.ir/article_13855.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13855_71bcf08def5ae349eb3026397d2e7723.pdf}
}
@article {
author = {Dankelmann, Peter},
title = {On the edge-connectivity of C_4-free graphs},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {141-150},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26453.1113},
abstract = {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},
url = {http://comb-opt.azaruniv.ac.ir/article_13856.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13856_bcb7a6a4d152a475da2d7bdfa37a581e.pdf}
}
@article {
author = {Hedetniemi, Jason T. and Hedetniemi, Stephen T. and Renu C. Laskar, Renu C. and Mulder, Henry Martyn},
title = {Different-Distance Sets in a Graph},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {151-171},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26467.1115},
abstract = {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 = {Different-Distance Sets,Cartesian products,graph},
url = {http://comb-opt.azaruniv.ac.ir/article_13863.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13863_aa060ff2474ed162917d785d51209d3c.pdf}
}
@article {
author = {Caro, Yair and Hansberg, Adriana},
title = {Directed domination in oriented hypergraphs},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {173-183},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26466.1114},
abstract = {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},
url = {http://comb-opt.azaruniv.ac.ir/article_13862.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13862_c7627d5b92f3a70d4057950f050d2d68.pdf}
}
@article {
author = {Sheikholeslami, Seyed Mahmoud and Nazari-Moghaddam, Sakineh},
title = {On trees with equal Roman domination and outer-independent Roman domination numbers},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {185-199},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26319.1095},
abstract = {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},
url = {http://comb-opt.azaruniv.ac.ir/article_13865.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13865_778d0f97a1447e3fa6dcc653002a9d16.pdf}
}
@article {
author = {Jafari Rad, Nader and Poureidi, Abolfazl},
title = {On Hop Roman Domination in Trees},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {201-208},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26469.1116},
abstract = {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.},
keywords = {hop dominating set,connected hop dominating set,hop Roman dominating function},
url = {http://comb-opt.azaruniv.ac.ir/article_13874.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13874_62d388aaf42e0893e140772d7fa34403.pdf}
}