ORIGINAL_ARTICLE
Strong Alliances in Graphs
For 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.pdf
2019-06-01T11:23:20
2020-08-05T11:23:20
1
13
10.22049/cco.2018.25921.1056
Alliances
Defensive alliances
Secure sets
Strong alliances
C.
Hegde
chandrugh@gmail.com
true
1
Mangalore University
Mangalore University
Mangalore University
LEAD_AUTHOR
B.
Sooryanarayana
dr_bsnrao@dr-ait.org
true
2
Dr. Ambedkar Institute of Technology
Dr. Ambedkar Institute of Technology
Dr. Ambedkar Institute of Technology
AUTHOR
ORIGINAL_ARTICLE
New skew equienergetic oriented graphs
Let $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 iftheir skew energies are equal. In this paper, we determine the skew spectra of some new oriented graphs. As applications, we give somenew methods to construct new non-cospectral skew equienergetic oriented graphs.
http://comb-opt.azaruniv.ac.ir/article_13786_f2e382fc36d6b753b4c6c9d7e3b92229.pdf
2019-06-01T11:23:20
2020-08-05T11:23:20
15
24
10.22049/cco.2018.26286.1093
Oriented graph
Skew energy
Skew equienergetic
Xiangxiang
Liu
xxliumath@163.com
true
1
Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an, Shaanxi 710072,
People's Republic
of China
Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an, Shaanxi 710072,
People's Republic
of China
Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an, Shaanxi 710072,
People's Republic
of China
AUTHOR
Ligong
Wang
lgwangmath@163.com
true
2
Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi&#039;an, Shaanxi 710072, People&#039;s Republic of China.
Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi&#039;an, Shaanxi 710072, People&#039;s Republic of China.
Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi&#039;an, Shaanxi 710072, People&#039;s Republic of China.
LEAD_AUTHOR
Cunxiang
Duan
cxduanmath@163.com
true
3
Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an, Shaanxi 710072,
People's Republic
of China
Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an, Shaanxi 710072,
People's Republic
of China
Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an, Shaanxi 710072,
People's Republic
of China
AUTHOR
ORIGINAL_ARTICLE
Eternal m-security subdivision numbers in graphs
An eternal $m$-secure set of a graph $G = (V,E)$ is aset $S_0subseteq V$ that can defend against any sequence ofsingle-vertex attacks by means of multiple-guard shifts along theedges of $G$. A suitable placement of the guards is called aneternal $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 $uvin E(G)$ is subdivided if wedelete the edge $uv$ from $G$ and add a new vertex $x$ and twoedges $ux$ and $vx$. The eternal $m$-security subdivision number${rm sd}_{sigma_m}(G)$ of a graph $G$ is the minimum cardinalityof 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 showthat the eternal $m$-security subdivision number of trees is atmost 2 and we characterize all trees attaining this bound.
http://comb-opt.azaruniv.ac.ir/article_13803_3fd4e7d1ecc4a8bed4b5eb43305015eb.pdf
2019-06-01T11:23:20
2020-08-05T11:23:20
25
33
10.22049/cco.2018.25948.1058
eternal $m$-secure set
eternal -security number
eternal m-security subdivision number
Maryam
Atapour
m.atapour@bonabu.ac.ir
true
1
Department of Mathematics
Faculty of basic sciences
University of Bonab
Bonab, Iran, Po. Box: 5551761167
Department of Mathematics
Faculty of basic sciences
University of Bonab
Bonab, Iran, Po. Box: 5551761167
Department of Mathematics
Faculty of basic sciences
University of Bonab
Bonab, Iran, Po. Box: 5551761167
LEAD_AUTHOR
ORIGINAL_ARTICLE
On the inverse maximum perfect matching problem under the bottleneck-type Hamming distance
Given 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 cite{Liu}. 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.pdf
2019-06-01T11:23:20
2020-08-05T11:23:20
35
46
10.22049/cco.2018.26231.1087
Inverse problem
Hamming distance
perfect matching
binary search
Javad
Tayyebi
javadtayyebi@birjand.ac.ir
true
1
Birjand university of technology
Birjand university of technology
Birjand university of technology
LEAD_AUTHOR
ORIGINAL_ARTICLE
The Roman domination and domatic numbers of a digraph
A 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_{vin 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.pdf
2019-06-01T11:23:20
2020-08-05T11:23:20
47
59
10.22049/cco.2019.26356.1101
Roman dominating function
Roman domination number
Roman domatic number
digraph
Zhihong
Xie
xiezh168@163.com
true
1
College of Science, East China University of Technology, Nanchang, P. R. China
College of Science, East China University of Technology, Nanchang, P. R. China
College of Science, East China University of Technology, Nanchang, P. R. China
AUTHOR
Guoliang
Hao
guoliang-hao@163.com
true
2
College of Science, East China University of Technology, Nanchang, P. R. China
College of Science, East China University of Technology, Nanchang, P. R. China
College of Science, East China University of Technology, Nanchang, P. R. China
LEAD_AUTHOR
Shouliu
Wei
wslwillow@126.com
true
3
Department of Mathematics, Minjiang University, Fuzhou, China
Department of Mathematics, Minjiang University, Fuzhou, China
Department of Mathematics, Minjiang University, Fuzhou, China
AUTHOR
ORIGINAL_ARTICLE
The Italian domatic number of a digraph
An {em Italian dominating function} on a digraph $D$ with vertex set $V(D)$ is defined as a function$fcolon V(D)to {0, 1, 2}$ such that every vertex $vin V(D)$ with $f(v)=0$ has at least two in-neighborsassigned 1 under $f$ or one in-neighbor $w$ with $f(w)=2$. A set ${f_1,f_2,ldots,f_d}$ of distinctItalian dominating functions on $D$ with the property that $sum_{i=1}^d f_i(v)le 2$ for each $vin V(D)$,is called an {em Italian dominating family} (of functions) on $D$. The maximum number of functions in anItalian dominating family on $D$ is the {em 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 sharpbounds for $d_{I}(D)$. In addition, we determine the Italian domatic number of some digraphs.
http://comb-opt.azaruniv.ac.ir/article_13845_b207051edc37d9a82ecd605da8ed79b4.pdf
2019-06-01T11:23:20
2020-08-05T11:23:20
61
70
10.22049/cco.2019.26360.1102
Digraphs
Italian dominating function
Italian domination number
Italian domatic number
Lutz
Volkmann
volkm@math2.rwth-aachen.de
true
1
RWTH Aachen University
RWTH Aachen University
RWTH Aachen University
LEAD_AUTHOR
ORIGINAL_ARTICLE
On independent domination numbers of grid and toroidal grid directed graphs
A subset $S$ of vertex set $V(D)$ is an {\em indpendent dominating set} of $D$ if $S$ is both an independent and a dominating set of $D$. The {\em 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 { \em cartesian product} of two {\em directed paths} $P_m$ and $P_n$ for arbitraries $m$ and $n$. Also, we calculate the independent domination number of the { \em cartesian product} of two {\em directed cycles} $C_m$ and $C_n$ for $m, n \equiv 0 ({\rm mod}\ 3)$, and $n \equiv 0 ({\rm mod}\ 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
2019-06-01T11:23:20
2020-08-05T11:23:20
71
77
10.22049/cco.2019.26282.1090
directed path
directed cycle
Cartesian product
independent domination number
Ramy
Shaheen
shaheenramy2010@hotmail.com
true
1
ٍSyrian
ٍSyrian
ٍSyrian
LEAD_AUTHOR