eng
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
2018-06-01
3
1
1
24
10.22049/cco.2017.25806.1041
13654
Roman domination excellent graphs: trees
Vladimir Samodivkin
vl.samodivkin@gmail.com
1
University of Architecture, Civil Еngineering and Geodesy;
Department of Mathematics
A Roman dominating function (RDF) on a graph $G = (V, E)$ <br />is a labeling $f : V rightarrow {0, 1, 2}$ such<br />that every vertex with label $0$ has a neighbor with label $2$. <br />The weight of $f$ is the value $f(V) = Sigma_{vin V} f(v)$<br />The Roman domination number, $gamma_R(G)$, of $G$ is the<br />minimum weight of an RDF on $G$.<br />An RDF of minimum weight is called a $gamma_R$-function.<br />A graph G is said to be $gamma_R$-excellent if for each vertex $x in V$<br />there is a $gamma_R$-function $h_x$ on $G$ with $h_x(x) not = 0$. <br />We present a constructive characterization of $gamma_R$-excellent trees using labelings. <br />A graph $G$ is said to be in class $UVR$ if $gamma(G-v) = gamma (G)$ for each $v in V$, <br />where $gamma(G)$ is the domination number of $G$. <br /> We show that each tree in $UVR$ is $gamma_R$-excellent.
http://comb-opt.azaruniv.ac.ir/article_13654_ec8df599ae3874367c247f6fb520698c.pdf
Roman domination number
excellent graphs
trees
eng
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
2018-06-01
3
1
25
35
10.22049/cco.2017.26018.1067
13655
Product version of reciprocal degree distance of composite graphs
K Pattabiraman
pramank@gmail.com
1
Annamalai University
A {it topological index} of a graph is a real number related to the graph; it does not depend on labeling or pictorial representation of a graph. In this paper, we present the upper bounds for the product version of reciprocal degree distance of the tensor product, join and strong product of two graphs in terms of other graph invariants including the Harary index and Zagreb indices.
http://comb-opt.azaruniv.ac.ir/article_13655_225b463f2a3ca5e41aee2b3b437d11c2.pdf
Degree distance
reciprocal degree distance
composite graph
eng
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
2018-06-01
3
1
37
50
10.22049/cco.2018.25719.1021
13683
Total $k$-Rainbow domination numbers in graphs
Hossein Abdollahzadeh Ahangar
ha.ahangar@yahoo.com
1
Jafar Amjadi
j-amjadi@azaruniv.ac.ir
2
Nader Jafari Rad
n.jafarirad@gmail.com
3
Vladimir D. Samodivkin
vlsam_fte@uacg.bg
4
Babol Noshirvani University of Technology
Azarbaijan Shahid Madani University
Shahrood University of Technology
University of Architecture, Civil Engineering and Geodesy
Let $kgeq 1$ be an integer, and let $G$ be a graph. A {it<br />$k$-rainbow dominating function} (or a {it $k$-RDF}) of $G$ is a<br />function $f$ from the vertex set $V(G)$ to the family of all subsets<br />of ${1,2,ldots ,k}$ such that for every $vin V(G)$ with<br />$f(v)=emptyset $, the condition $bigcup_{uin<br />N_{G}(v)}f(u)={1,2,ldots,k}$ is fulfilled, where $N_{G}(v)$ is<br />the open neighborhood of $v$. The {it weight} of a $k$-RDF $f$ of<br />$G$ is the value $omega (f)=sum _{vin V(G)}|f(v)|$. A $k$-rainbow<br />dominating function $f$ in a graph with no isolated vertex is called<br />a {em total $k$-rainbow dominating function} if the subgraph of $G$<br />induced by the set ${v in V(G) mid f (v) not = {color{blue}emptyset}}$ has no isolated vertices. The {em total $k$-rainbow domination number} of $G$, denoted by<br />$gamma_{trk}(G)$, is the minimum weight of a total $k$-rainbow<br />dominating function on $G$. The total $1$-rainbow domination is the<br />same as the total domination. In this paper we initiate the<br />study of total $k$-rainbow domination number and we investigate its<br />basic properties. In particular, we present some sharp bounds on the<br />total $k$-rainbow domination number and we determine {color{blue}the} total<br />$k$-rainbow domination number of some classes of graphs.
http://comb-opt.azaruniv.ac.ir/article_13683_b5784dd717acd4308580ca847ce38c2b.pdf
$k$-rainbow dominating function
$k$-rainbow domination number
total $k$-rainbow dominating function
total $k$-rainbow domination number
eng
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
2018-06-01
3
1
51
70
10.22049/cco.2018.25801.1038
13693
An infeasible interior-point method for the $P*$-matrix linear complementarity problem based on a trigonometric kernel function with full-Newton step
Behrouz Kheirfam
b.kheirfam@azaruniv.edu
1
Masoumeh Haghighi
b.kheirfam@yahoo.com
2
Azarbaijan Shahid Madani University
Azarbaijan Shahid Madani University
An infeasible interior-point algorithm for solving the<br />$P_*$-matrix linear complementarity problem based on a kernel<br />function with trigonometric barrier term is analyzed. Each (main)<br />iteration of the algorithm consists of a feasibility step and<br />several centrality steps, whose feasibility step is induced by a<br />trigonometric kernel function. The complexity result coincides with<br />the best result for infeasible interior-point methods for<br />$P_*$-matrix linear complementarity problem.
http://comb-opt.azaruniv.ac.ir/article_13693_2409f47f2535c47bbf7f6f1c4e57f291.pdf
Linear complementarity problem
Full-Newton step
Infeasible interiorpoint method
Kernel function
Polynomial complexity
eng
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
2018-06-01
3
1
71
77
10.22049/cco.2018.26125.1078
13744
Double Roman domination and domatic numbers of graphs
Lutz Volkmann
volkm@math2.rwth-aachen.de
1
RWTH Aachen University
A double Roman dominating function on a graph $G$ with vertex set $V(G)$ is defined in cite{bhh} as a function<br />$f:V(G)rightarrow{0,1,2,3}$ having the property that if $f(v)=0$, then the vertex $v$ must have at least two<br />neighbors assigned 2 under $f$ or one neighbor $w$ with $f(w)=3$, and if $f(v)=1$, then the vertex $v$ must have<br />at least one neighbor $u$ with $f(u)ge 2$. The weight of a double Roman dominating function $f$ is the sum<br />$sum_{vin V(G)}f(v)$, and the minimum weight of a double Roman dominating function on $G$ is the double Roman<br />domination number $gamma_{dR}(G)$ of $G$.<br /><br />A set ${f_1,f_2,ldots,f_d}$ of distinct double Roman dominating functions on $G$ with the property that<br />$sum_{i=1}^df_i(v)le 3$ for each $vin V(G)$ is called in cite{v} a double Roman dominating family (of functions)<br />on $G$. The maximum number of functions in a double Roman dominating family on $G$ is the double Roman domatic number<br />of $G$.<br /><br />In this note we continue the study the double Roman domination and domatic numbers. In particular, we present<br />a sharp lower bound on $gamma_{dR}(G)$, and we determine the double Roman domination and domatic numbers of some<br />classes of graphs.
http://comb-opt.azaruniv.ac.ir/article_13744_0b21f0f7d95e9ab99c3422cf6f3acc77.pdf
domination
Double Roman domination number
Double Roman domatic number
eng
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
2018-06-01
3
1
79
91
10.22049/cco.2018.25964.1062
13747
Mixed Roman domination and 2-independence in trees
Nasrin Dehgardi
ndehgardi@gmail.com
1
Sirjan University of Technology, Sirjan 78137, Iran
Let $G=(V, E)$ be a simple graph with vertex set $V$ and edge set $E$. A {em mixed Roman dominating function} (MRDF) of $G$ is a function $f:Vcup Erightarrow {0,1,2}$ satisfying the condition that every element $xin Vcup E$ for which $f(x)=0$ is adjacent<br />or incident to at least one element $yin Vcup E$ for which $f(y)=2$. The weight of an<br />MRDF $f$ is $sum _{xin Vcup E} f(x)$. The mixed Roman domination number $gamma^*_R(G)$ of $G$ is<br />the minimum weight among all mixed Roman dominating functions of $G$. A subset $S$ of $V$ is a 2-independent set of $G$ if every vertex of $S$ has at most one neighbor in $S$. The minimum cardinality of a 2-independent set of $G$ is the 2-independence number $beta_2(G)$. These two parameters are incomparable in general, however, we show that if $T$ is a tree, then $frac{4}{3}beta_2(T)ge gamma^*_R(T)$ and we characterize all trees attaining the equality.
http://comb-opt.azaruniv.ac.ir/article_13747_2ec084aafd9f82151a96717d372ecd5b.pdf
Mixed Roman dominating function
Mixed Roman domination number
2-independent set
2-independence number