Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
1
2018
06
01
Roman domination excellent graphs: trees
1
24
EN
Vladimir
D.
Samodivkin
University of Architecture, Civil Еngineering and Geodesy;
Department of Mathematics
vl.samodivkin@gmail.com
10.22049/cco.2017.25806.1041
A Roman dominating function (RDF) on a graph $G = (V, E)$ is a labeling $f : V rightarrow {0, 1, 2}$ suchthat every vertex with label $0$ has a neighbor with label $2$. The weight of $f$ is the value $f(V) = Sigma_{vin V} f(v)$The Roman domination number, $gamma_R(G)$, of $G$ is theminimum weight of an RDF on $G$.An RDF of minimum weight is called a $gamma_R$-function.A graph G is said to be $gamma_R$-excellent if for each vertex $x in V$there is a $gamma_R$-function $h_x$ on $G$ with $h_x(x) not = 0$. We present a constructive characterization of $gamma_R$-excellent trees using labelings. A graph $G$ is said to be in class $UVR$ if $gamma(G-v) = gamma (G)$ for each $v in V$, where $gamma(G)$ is the domination number of $G$. We show that each tree in $UVR$ is $gamma_R$-excellent.
Roman domination number,excellent graphs,trees
http://comb-opt.azaruniv.ac.ir/article_13654.html
http://comb-opt.azaruniv.ac.ir/article_13654_ec8df599ae3874367c247f6fb520698c.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
1
2018
06
01
Product version of reciprocal degree distance of composite graphs
25
35
EN
K
Pattabiraman
Annamalai University
pramank@gmail.com
10.22049/cco.2017.26018.1067
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.
Degree distance,reciprocal degree distance,composite graph
http://comb-opt.azaruniv.ac.ir/article_13655.html
http://comb-opt.azaruniv.ac.ir/article_13655_225b463f2a3ca5e41aee2b3b437d11c2.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
1
2018
06
01
Total $k$-Rainbow domination numbers in graphs
37
50
EN
Hossein
Abdollahzadeh Ahangar
Babol Noshirvani University of Technology
ha.ahangar@yahoo.com
Jafar
Amjadi
Azarbaijan Shahid Madani University
j-amjadi@azaruniv.edu
Nader
Jafari Rad
Shahrood University of Technology
n.jafarirad@gmail.com
Vladimir
D. Samodivkin
University of Architecture, Civil Engineering and Geodesy
vlsam_fte@uacg.bg
10.22049/cco.2018.25719.1021
Let $kgeq 1$ be an integer, and let $G$ be a graph. A {it$k$-rainbow dominating function} (or a {it $k$-RDF}) of $G$ is afunction $f$ from the vertex set $V(G)$ to the family of all subsetsof ${1,2,ldots ,k}$ such that for every $vin V(G)$ with$f(v)=emptyset $, the condition $bigcup_{uinN_{G}(v)}f(u)={1,2,ldots,k}$ is fulfilled, where $N_{G}(v)$ isthe open neighborhood of $v$. The {it weight} of a $k$-RDF $f$ of$G$ is the value $omega (f)=sum _{vin V(G)}|f(v)|$. A $k$-rainbowdominating function $f$ in a graph with no isolated vertex is calleda {em total $k$-rainbow dominating function} if the subgraph of $G$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$gamma_{trk}(G)$, is the minimum weight of a total $k$-rainbowdominating function on $G$. The total $1$-rainbow domination is thesame as the total domination. In this paper we initiate thestudy of total $k$-rainbow domination number and we investigate itsbasic properties. In particular, we present some sharp bounds on thetotal $k$-rainbow domination number and we determine {color{blue}the} total$k$-rainbow domination number of some classes of graphs.
$k$-rainbow dominating function,$k$-rainbow domination number,total $k$-rainbow dominating function,total $k$-rainbow domination number
http://comb-opt.azaruniv.ac.ir/article_13683.html
http://comb-opt.azaruniv.ac.ir/article_13683_b5784dd717acd4308580ca847ce38c2b.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
1
2018
06
01
An infeasible interior-point method for the $P*$-matrix linear complementarity problem based on a trigonometric kernel function with full-Newton step
51
70
EN
Behrouz
Kheirfam
Azarbaijan Shahid Madani University
b.kheirfam@azaruniv.edu
Masoumeh
Haghighi
Azarbaijan Shahid Madani University
b.kheirfam@yahoo.com
10.22049/cco.2018.25801.1038
An infeasible interior-point algorithm for solving the$P_*$-matrix linear complementarity problem based on a kernelfunction with trigonometric barrier term is analyzed. Each (main)iteration of the algorithm consists of a feasibility step andseveral centrality steps, whose feasibility step is induced by atrigonometric kernel function. The complexity result coincides withthe best result for infeasible interior-point methods for$P_*$-matrix linear complementarity problem.
Linear complementarity problem,Full-Newton step,Infeasible interiorpoint method,Kernel function,Polynomial complexity
http://comb-opt.azaruniv.ac.ir/article_13693.html
http://comb-opt.azaruniv.ac.ir/article_13693_2409f47f2535c47bbf7f6f1c4e57f291.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
1
2018
06
01
Double Roman domination and domatic numbers of graphs
71
77
EN
Lutz
Volkmann
RWTH Aachen University
volkm@math2.rwth-aachen.de
10.22049/cco.2018.26125.1078
A double Roman dominating function on a graph $G$ with vertex set $V(G)$ is defined in cite{bhh} as a function$f:V(G)rightarrow{0,1,2,3}$ having the property that if $f(v)=0$, then the vertex $v$ must have at least twoneighbors assigned 2 under $f$ or one neighbor $w$ with $f(w)=3$, and if $f(v)=1$, then the vertex $v$ must haveat least one neighbor $u$ with $f(u)ge 2$. The weight of a double Roman dominating function $f$ is the sum$sum_{vin V(G)}f(v)$, and the minimum weight of a double Roman dominating function on $G$ is the double Romandomination number $gamma_{dR}(G)$ of $G$.A set ${f_1,f_2,ldots,f_d}$ of distinct double Roman dominating functions on $G$ with the property that$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)on $G$. The maximum number of functions in a double Roman dominating family on $G$ is the double Roman domatic numberof $G$.In this note we continue the study the double Roman domination and domatic numbers. In particular, we presenta sharp lower bound on $gamma_{dR}(G)$, and we determine the double Roman domination and domatic numbers of someclasses of graphs.
Domination,Double Roman domination number,Double Roman domatic number
http://comb-opt.azaruniv.ac.ir/article_13744.html
http://comb-opt.azaruniv.ac.ir/article_13744_0b21f0f7d95e9ab99c3422cf6f3acc77.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
1
2018
06
01
Mixed Roman domination and 2-independence in trees
79
91
EN
Nasrin
Dehgardi
Sirjan University of Technology, Sirjan 78137, Iran
ndehgardi@gmail.com
10.22049/cco.2018.25964.1062
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 adjacentor incident to at least one element $yin Vcup E$ for which $f(y)=2$. The weight of anMRDF $f$ is $sum _{xin Vcup E} f(x)$. The mixed Roman domination number $gamma^*_R(G)$ of $G$ isthe 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.
Mixed Roman dominating function,Mixed Roman domination number,2-independent set,2-independence number
http://comb-opt.azaruniv.ac.ir/article_13747.html
http://comb-opt.azaruniv.ac.ir/article_13747_2ec084aafd9f82151a96717d372ecd5b.pdf