Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284120190601Strong Alliances in Graphs1131378510.22049/cco.2018.25921.1056ENC.HegdeMangalore University0000-0001-5751-7316B.SooryanarayanaDr. Ambedkar Institute of TechnologyJournal Article20170409For any simple connected graph $G=(V,E)$, a defensive alliance is a subset $S$ of $V$ satisfying the condition that every vertex $vin S$ has at most one more neighbour in $V-S$ than it has in $S$. The minimum cardinality of any defensive alliance in $G$ is called the alliance number of $G$, denoted $a(G)$. In this paper, we introduce a new type of alliance number called $k$-strong alliance number and its varieties. The bounds for 1-strong alliance number in terms of different graphical parameters are determined and the characterizations of graphs with 1-strong alliance number 1, 2, and $n$ are obtained.http://comb-opt.azaruniv.ac.ir/article_13785_db97a57dfa7d3980c88f4ce8245a31b6.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284120190601New skew equienergetic oriented graphs15241378610.22049/cco.2018.26286.1093ENXiangxiangLiuDepartment of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an, Shaanxi 710072,
People's Republic
of ChinaLigongWangDepartment of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi&#039;an, Shaanxi 710072, People&#039;s Republic of China.CunxiangDuanDepartment of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an, Shaanxi 710072,
People's Republic
of ChinaJournal Article20180703Let $S(G^{\sigma})$ be the skew-adjacency matrix of the oriented graph $G^{\sigma}$, which is obtained from a simple undirected graph $G$ by assigning an orientation $\sigma$ to each of its edges. The skew energy of an oriented graph $G^{\sigma}$ is defined as the sum of absolute values of all eigenvalues of $S(G^{\sigma})$. Two oriented graphs are said to be skew equienergetic if their skew energies are equal. In this paper, we determine the skew spectra of some new oriented graphs. As applications, we give some new methods to construct new non-cospectral skew equienergetic oriented graphs.http://comb-opt.azaruniv.ac.ir/article_13786_f2e382fc36d6b753b4c6c9d7e3b92229.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284120190601Eternal m-security subdivision numbers in graphs25331380310.22049/cco.2018.25948.1058ENMaryamAtapourDepartment of Mathematics
Faculty of basic sciences
University of Bonab
Bonab, Iran, Po. Box: 5551761167Journal Article20170529An eternal $m$-secure set of a graph $G = (V,E)$ is a set $S_0\subseteq V$ that can defend against any sequence of single-vertex attacks by means of multiple-guard shifts along the edges of $G$. A suitable placement of the guards is called an eternal $m$-secure set. The eternal $m$-security number $\sigma_m(G)$ is the minimum cardinality among all eternal $m$-secure sets in $G$. An edge $uv\in E(G)$ is subdivided if we delete the edge $uv$ from $G$ and add a new vertex $x$ and two edges $ux$ and $vx$. The eternal $m$-security subdivision number ${\rm sd}_{\sigma_m}(G)$ of a graph $G$ is the minimum cardinality of a set of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to increase the eternal $m$-security number of $G$. In this paper, we study the eternal $m$-security subdivision number in trees. In particular, we show that the eternal $m$-security subdivision number of trees is at most 2 and we characterize all trees attaining this bound. http://comb-opt.azaruniv.ac.ir/article_13803_3fd4e7d1ecc4a8bed4b5eb43305015eb.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284120190601On the inverse maximum perfect matching problem under the bottleneck-type Hamming distance35461380410.22049/cco.2018.26231.1087ENJavadTayyebiBirjand university of technology0000-0002-7559-3870Journal Article20180518Given an undirected network $G(V,A,c)$ and a perfect matching $M$ of $G$, the inverse maximum perfect matching problem consists of modifying minimally the elements of c so that M becomes a maximum perfect matching with respect to the modified vector. In this article, we consider the inverse problem when the modifications are measured by the weighted bottleneck-type Hamming distance. We propose an algorithm based on the binary search technique for solving the problem. Our proposed algorithm has a better time complexity than the one presented in [13]. We also study the inverse assignment problem as a special case of the inverse maximum perfect matching problem in which the network is bipartite and present an efficient algorithm for solving the problem. Finally, we compare the algorithm with those presented in the literature.http://comb-opt.azaruniv.ac.ir/article_13804_dbb06f4741821880df74fe3c9cca70f8.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284120190601The Roman domination and domatic numbers of a digraph47591384110.22049/cco.2019.26356.1101ENZhihongXieCollege of Science, East China University of Technology, Nanchang, P. R. ChinaGuoliangHaoCollege of Science, East China University of Technology, Nanchang, P. R. ChinaShouliuWeiDepartment of Mathematics, Minjiang University, Fuzhou, ChinaJournal Article20181022A Roman dominating function (RDF) on a digraph $D$ is a function $f: V(D)\rightarrow {0,1,2}$ satisfying the condition that every vertex $v$ with $f(v)=0$ has an in-neighbor $u$ with $f(u)=2$. The weight of an RDF $f$ is the value $\sum_{v\in V(D)}f(v)$. The Roman domination number of a digraph $D$ is the minimum weight of an RDF on $D$. A set $\{f_1,f_2,\dots,f_d\}$ of Roman dominating functions on $D$ with the property that $\sum_{i=1}^df_i(v)\le2$ for each $vin V(D)$, is called a Roman dominating family (of functions) on $D$. The maximum number of functions in a Roman dominating family on $D$ is the Roman domatic number of $D$, denoted by $d_{R}(D)$. In this paper we continue the investigation of the Roman domination number, and we initiate the study of the Roman domatic number in digraphs. We present some bounds for $d_{R}(D)$. In addition, we determine the Roman domatic number of some digraphs.http://comb-opt.azaruniv.ac.ir/article_13841_9bb2c1e1cb7db1916a327f1866d037b2.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284120190601The Italian domatic number of a digraph61701384510.22049/cco.2019.26360.1102ENLutzVolkmannRWTH Aachen University0000-0003-3496-277XJournal Article20181026An Italian dominating function on a digraph $D$ with vertex set $V(D)$ is defined as a function $f\colon V(D)\to \{0, 1, 2\}$ such that every vertex $v\in V(D)$ with $f(v)=0$ has at least two in-neighbors assigned 1 under $f$ or one in-neighbor $w$ with $f(w)=2$. A set $\{f_1,f_2,\ldots,f_d\}$ of distinct Italian dominating functions on $D$ with the property that $\sum_{i=1}^d f_i(v)\le 2$ for each $v\in V(D)$, is called an Italian dominating family (of functions) on $D$. The maximum number of functions in an Italian dominating family on $D$ is the Italian domatic number of $D$, denoted by $d_{I}(D)$. In this paper we initiate the study of the Italian domatic number in digraphs, and we present some sharp bounds for $d_{I}(D)$. In addition, we determine the Italian domatic number of some digraphs.http://comb-opt.azaruniv.ac.ir/article_13845_b207051edc37d9a82ecd605da8ed79b4.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284120190601On independent domination numbers of grid and toroidal grid directed graphs71771384610.22049/cco.2019.26282.1090ENRamyShaheenٍSyrianJournal Article20180622A subset $S$ of vertex set $V(D)$ is an indpendent dominating set of $D$ if $S$ is both an independent and a dominating set of $D$. The indpendent domination number, $i(D)$ is the cardinality of the smallest independent dominating set of $D$. In this paper we calculate the independent domination number of the cartesian product of two directed paths $P_m$ and $P_n$ for arbitraries $m$ and $n$. Also, we calculate the independent domination number of the Cartesian product of two directed cycles $C_m$ and $C_n$ for $m, n \equiv 0\pmod 3$, and $n \equiv 0\pmod m$. There are many values of $m$ and $n$ such that $C_m \Box C_n$ does not have an independent dominating set.http://comb-opt.azaruniv.ac.ir/article_13846_0948ec1c34ebfc23d9e6b9f6dc3f735d.pdf