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:V\rightarrow \{0,1,2\}$ be a function on $G$. The weight of $f$ is $\omega(f)=\sum_{v\in V}f(v)$ and let $V_i=\{v\in 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 $v\in V_0$, $\sum_{u\in 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 $v\in V_0$ there exists $u\in 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, Algeria0000-0001-5231-6195Teresa 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 $t\leq \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 $3\leq t\leq |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_{x\in V(G)}f(x)$ of an independent broadcast $f$ on $G$. It is known that $\alpha(G)\leq \alpha_b(G)\leq 4\alpha(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 2\alpha(G)$ provided that $g\geq 6$ and $\delta\geq 3$ or that $g\geq 4$ and $\delta\geq 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 2\left(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 University0000-0003-2298-4744SakinehNazari-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 $\{v\in V\mid 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 $S\subset 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_{v\in 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)=2\gamma_{ch}(T)$ for a given tree $T$.http://comb-opt.azaruniv.ac.ir/article_13874_62d388aaf42e0893e140772d7fa34403.pdf