Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21283120180601Roman domination excellent graphs: trees1241365410.22049/cco.2017.25806.1041ENVladimir D.SamodivkinUniversity of Architecture, Civil Еngineering and Geodesy;
Department of Mathematics0000-0001-7934-5789Journal Article20161002A Roman dominating function (RDF) on a graph $G = (V, E)$ is a labeling $f : V \rightarrow \{0, 1, 2\}$ such that every vertex with label $0$ has a neighbor with label $2$. The weight of $f$ is the value $f(V) = \Sigma_{v\in V} f(v)$ The Roman domination number, $\gamma_R(G)$, of $G$ is the minimum 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) \neq 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.Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21283120180601Product version of reciprocal degree distance of composite graphs25351365510.22049/cco.2017.26018.1067ENKPattabiramanAnnamalai UniversityJournal Article20170907A 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.Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21283120180601Total $k$-Rainbow domination numbers in graphs37501368310.22049/cco.2018.25719.1021ENHosseinAbdollahzadeh AhangarBabol Noshirvani University of Technology0000-0002-0038-8047JafarAmjadiAzarbaijan Shahid Madani University0000-0001-9340-4773NaderJafari RadShahrood University of TechnologyVladimirD. SamodivkinUniversity of Architecture, Civil Engineering and GeodesyJournal Article20170914Let $k\geq 1$ be an integer, and let $G$ be a graph. A $k$-rainbow dominating function (or a {$k$-RDF) of $G$ is a function $f$ from the vertex set $V(G)$ to the family of all subsets of $\{1,2,\ldots ,k\}$ such that for every $v\in V(G)$ with $f(v)=\emptyset $, the condition $\bigcup_{u\in N_{G}(v)}f(u)=\{1,2,\ldots,k\}$ is fulfilled, where $N_{G}(v)$ is the open neighborhood of $v$. The weight of a $k$-RDF $f$ of $G$ is the value $\omega (f)=\sum _{v\in V(G)}|f(v)|$. A $k$-rainbow dominating function $f$ in a graph with no isolated vertex is called a total $k$-rainbow dominating function if the subgraph of $G$ induced by the set $\{v\in V(G) \mid f (v) \neq \emptyset\}$ has no isolated vertices. The total $k$-rainbow domination number of $G$, denoted by $\gamma_{trk}(G)$, is the minimum weight of a total $k$-rainbow dominating function on $G$. The total $1$-rainbow domination is the same as the total domination. In this paper we initiate the study of total $k$-rainbow domination number and we investigate its basic properties. In particular, we present some sharp bounds on the total $k$-rainbow domination number and we determine the total $k$-rainbow domination number of some classes of graphs. Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21283120180601An infeasible interior-point method for the $P*$-matrix linear complementarity problem based on a trigonometric kernel function with full-Newton step51701369310.22049/cco.2018.25801.1038ENBehrouzKheirfamAzarbaijan Shahid Madani Universityorcid.org/0000-0001-7928-2618MasoumehHaghighiAzarbaijan Shahid Madani Universityorcid.org/0000-0001-7928-2618Journal Article20160926An infeasible interior-point algorithm for solving the $P_*$-matrix linear complementarity problem based on a kernel function with trigonometric barrier term is analyzed. Each (main) iteration of the algorithm consists of a feasibility step and several centrality steps, whose feasibility step is induced by a trigonometric kernel function. The complexity result coincides with the best result for infeasible interior-point methods for $P_*$-matrix linear complementarity problem.Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21283120180601Double Roman domination and domatic numbers of graphs71771374410.22049/cco.2018.26125.1078ENLutzVolkmannRWTH Aachen University0000-0003-3496-277XJournal Article20171117A double Roman dominating function on a graph $G$ with vertex set $V(G)$ is defined in cite{bhh} as a function $f:V(G)\to \{0,1,2,3\}$ having the property that if $f(v)=0$, then the vertex $v$ must have at least two neighbors assigned 2 under $f$ or one neighbor $w$ with $f(w)=3$, and if $f(v)=1$, then the vertex $v$ must have at least one neighbor $u$ with $f(u)\ge 2$. The weight of a double Roman dominating function $f$ is the sum $\sum_{v\in V(G)}f(v)$, and the minimum weight of a double Roman dominating function on $G$ is the double Roman domination number $\gamma_{dR}(G)$ of $G$.<br /><br />A set $\{f_1,f_2, \dots,f_d\}$ of distinct double Roman dominating functions on $G$ with the property that $\sum_{i=1}^df_i(v)\le 3$ for each $v\in V(G)$ is called 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 number of $G$.<br /><br />In this note we continue the study the double Roman domination and domatic numbers. In particular, we present a sharp lower bound on $\gamma_{dR}(G)$, and we determine the double Roman domination and domatic numbers of some classes of graphs.Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21283120180601Mixed Roman domination and 2-independence in trees79911374710.22049/cco.2018.25964.1062ENNasrinDehgardiSirjan University of Technology, Sirjan 78137, Iran0000-0001-8214-6000Journal Article20170620Let $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:V\cup E\rightarrow \{0,1,2\}$ satisfying the condition that every element $xin V\cup E$ for which $f(x)=0$ is adjacent or incident to at least one element $y\in V\cup E$ for which $f(y)=2$. The weight of an MRDF $f$ is $\sum_{x\in V\cup E} f(x)$. The mixed Roman domination number $\gamma^*_R(G)$ of $G$ is 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.