Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201Paired-Domination Game Played in Graphs79941385110.22049/cco.2019.26437.1110ENM.A.HenningUniversity of JohannesburgTeresa W.HaynesEast Tennessee State University;
Department of MathematicsJournal Article20190227In this paper, we continue the study of the domination game in graphs introduced by Bre{v{s}}ar, Klav{v{z}}ar, and Rall [SIAM J. Discrete Math. 24 (2010) 979--991]. 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 $gamma_{pr}(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 $gamma_{pr}(G) le frac{4}{5}n$, and this bound is tight. Further we show that if $G$ is $(C_4,C_5)$-free, then $gamma_{pr}(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 $gamma_{pr}(G) le frac{3}{4}n$.http://comb-opt.azaruniv.ac.ir/article_13851_54f7f80cbf84f62b513594201751c9dc.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201A characterization of trees with equal Roman {2}-domination and Roman domination numbers951071385010.22049/cco.2019.26364.1103ENIsmaelGonzalez YeroUniversity of Cadiz0000-0002-1619-1572AbelCabrera MartinezUniversitat Rovira i VirgiliJournal Article20181001Given 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 /><br />1) 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 /><br />2) 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 /><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.http://comb-opt.azaruniv.ac.ir/article_13850_e789cd5a865ff841296b9739ea34aec1.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201k-Efficient partitions of graphs1091221385210.22049/cco.2019.26446.1112ENMChellaliLAMDA-RO Laboratory,
Department of Mathematics,
University of Blida,
B.P. 270, Blida, AlgeriaTeresa W.HaynesDepartment of Mathematics and Statistics,
East Tennessee State University,
Johnson City, TN 37614-0002 USAStephen T.HedetniemiProfessor Emeritus, School of Computing,
Clemson University,
Clemson, SC 29634 USAJournal Article20181010A set $S = {u_1,u_2, ldots, u_t}$ of vertices of $G$ is an efficient dominating set if every vertex of $G$ is dominated exactly once by the vertices 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 set of $G$ and that each $U_i$ contains the vertex $u_i$ and all the vertices at distance~1 from it in $G$. In this paper, we generalize the concept of efficient domination by considering $k$-efficient domination partitions of the vertex set of $G$, where each element of the partition is a set consisting 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$-efficient domination number for general graphs, and for $k in {1,2}$, we give exact values for some graph families. Complexity results are also obtained. http://comb-opt.azaruniv.ac.ir/article_13852_478f6dfde08ed596744a7773348bc29a.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201t-Pancyclic Arcs in Tournaments1231301385310.22049/cco.2019.26333.1097ENWeiMengSchool of Mathematical Sciences, Shanxi University, 030006 Taiyuan, ChinaSteffenGrueterLehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, GermanyYubaoGuoLehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, GermanyManuKapolkeLehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, GermanySimonMeeskerLehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, GermanyJournal Article20180901Let $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 ( J. Combin. Inform. System Sci., 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 all tournaments which satisfy $h^t(T)= t$. We also present all tournaments which fulfill $p^t(T)= t$. http://comb-opt.azaruniv.ac.ir/article_13853_b838a366c1fd609997bcb3c6948d3b01.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201Girth, minimum degree, independence, and broadcast independence1311391385510.22049/cco.2019.26346.1098ENStephaneBessyLIRMMDieterRautenbach89069 Ulm, GermayJournal Article20180925An 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 $sum_{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 degree of 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.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201On the edge-connectivity of C_4-free graphs1411501385610.22049/cco.2019.26453.1113ENPeterDankelmannUniversity of JohannesburgJournal Article20180801Let $G$ be a connected graph of order $n$ and minimum degree $delta(G)$. The edge-connectivity $lambda(G)$ of $G$ is the minimum number of 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 result by Chartrand gives the sufficient condition $delta(G) geq frac{n-1}{2}$ for a graph to be maximally edge-connected. We give lower bounds on the edge-connectivity of graphs not containing $4$-cycles that imply that for graphs not containing a $4$-cycle Chartrand's condition can be relaxed to $delta(G) geq sqrt{frac{n}{2}} +1$, and if the graph also 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 graphs to show that for an infinite number of values of $n$ both sufficient conditions are best possible apart from a small additive constant.http://comb-opt.azaruniv.ac.ir/article_13856_bcb7a6a4d152a475da2d7bdfa37a581e.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201Different-Distance Sets in a Graph1511711386310.22049/cco.2019.26467.1115ENJason T.HedetniemiWingate UniversityStephen T.HedetniemiDepartment of Mathematics,
University of Johannesburg,
Auckland Park, South AfricaRenu C.Renu C. LaskarClemson UniversityHenry MartynMulderErasmus Universiteit0000-0002-4776-4046Journal Article20180915A 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-istance 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.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201Directed domination in oriented hypergraphs1731831386210.22049/cco.2019.26466.1114ENYairCaroUniversity of Haifa-OranimAdrianaHansberg76230 Queretaro, MexicoJournal Article20181202ErdÖs [On Schutte 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 $overrightarrow{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 overrightarrow{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$.http://comb-opt.azaruniv.ac.ir/article_13862_c7627d5b92f3a70d4057950f050d2d68.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201On trees with equal Roman domination and outer-independent Roman domination numbers1851991386510.22049/cco.2019.26319.1095ENSeyed MahmoudSheikholeslamiAzarbaijan Shahid Madani UniversitySakinehNazari-MoghaddamAzarbaijan Shahid Madani UniversityJournal Article20180802A 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 one vertex $v$ for which $f(v) = 2$. A Roman dominating function $f$ is called an outer-independent Roman 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 weight of 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.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201On Hop Roman Domination in Trees2012081387410.22049/cco.2019.26469.1116ENNaderJafari RadSepartment of Mathemtics, Shahed University, Tehran, IranAbolfazlPoureidiDepartment of Mathematics, Shahrood University of Technology, Shahrood, IranJournal Article20190407Let $G=(V,E)$ be a graph. A subset $Ssubset V$ is a hop dominating set if 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$. The connected hop domination number of $G$, $ gamma_{ch}(G)$, is the minimum cardinality of a connected hop dominating set of $G$. A hop Roman dominating function (HRDF) of a graph $G$ is a function $<br />f: V(G)longrightarrow {0, 1, 2} $ having the property that for every vertex $ v in V $ with $ f(v) = 0 $ there is a vertex $ u $ with $ f(u)=2 $ and $ d(u,v)=2 $. The weight of an HRDF $ f $ is the sum $f(V) = sum_{vin V} f(v) $. The minimum weight of an HRDF on $ G $ is called the hop Roman domination number of $ G $ and is denoted by $ gamma_{hR}(G)<br />$. We give an algorithm that decides whether $gamma_{hR}(T)=2gamma_{ch}(T)$ for a given tree $T$.http://comb-opt.azaruniv.ac.ir/article_13874_62d388aaf42e0893e140772d7fa34403.pdf