Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21281120160601Sufficient conditions on the zeroth-order general Randic index for maximally edge-connected digraphs1131351410.22049/cco.2016.13514ENLutzVolkmannRWTH Aachen University0000-0003-3496-277XJournal Article20151120Let $D$ be a finite and simple digraph with vertex set $V(D)$. For a vertex $v\in V(D)$, the degree of $v$, denoted by $d(v)$, is defined as the minimum value of its out-degree $d^+(v)$ and its in-degree $d^-(v)$. Now let $D$ be a digraph with minimum degree $\delta\ge 1$ and edge-connectivity $\lambda$. If $\alpha$ is real number, then, analogously to graphs, we define the zeroth-order general Randi\'{c} index by $\sum_{x\in V(D)}(d(x))^{\alpha}$. A digraph is maximally edge-connected if $\lambda=\delta$. In this paper, we present sufficient conditions for digraphs to be maximally edge-connected in terms of the zeroth-order general Randi\'{c} index, the order and the minimum degree when $\alpha <0$, $0<\alpha <1$ or $1<\alpha\le 2$. Using the associated digraph of a graph, we show that our results include some corresponding known results on graphs. http://comb-opt.azaruniv.ac.ir/article_13514_2c29013911bbc87b1dc4be81c6823349.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21281120160601The minus k-domination numbers in graphs15281353410.22049/cco.2016.13534ENN.DehgardiSirjan University of Technology, Sirjan 78137, Iran0000-0001-8214-6000Journal Article20160311For any integer $k\ge 1$, a minus $k$-dominating function is a function $f : V \rightarrow \{-1,0, 1\}$ satisfying $\sum_{w\in N[v]} f(w)\ge k$ for every $v\in V(G)$, where $N(v) =\{u \in V(G)\mid uv\in E(G)\}$ and $N[v] =N(v)\cup \{v\}$. The minimum of the values of $\sum_{v\in V(G)}f(v)$, taken over all minus $k$-dominating functions $f$, is called the minus $k$-domination number and is denoted by $\gamma^-_{k}(G)$. In this paper, we introduce the study of minus $k$-domination in graphs and present several sharp lower bounds on the minus $k$-domination number for general graphs.http://comb-opt.azaruniv.ac.ir/article_13534_842d7e5cc29617870d3b17a192a370e4.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21281120160601New bounds on proximity and remoteness in graphs29411354310.22049/cco.2016.13543ENP.DankelmannUniversity of JohannesburgJournal Article20160627The average distance of a vertex $v$ of a connected graph $G$ is the arithmetic mean of the distances from $v$ to all other vertices of $G$. The proximity $\pi(G)$ and the remoteness $\rho(G)$ of $G$ are defined as the minimum and maximum, respectively, average distance of the vertices of $G$. In this paper we investigate the difference between proximity or remoteness and the classical distance parameters diameter and radius. Among other results we show that in a graph of order $n$ and minimum degree $\delta$ the difference between diameter and proximity and the difference between radius and proximity cannot exceed $\frac{9n}{4(\delta+1)}+c_1$ and $\frac{3n}{4(\delta+1)}+c_2$, respectively, for constants $c_1$ and $c_2$ which depend on $\delta$ but not on $n$. These bounds improve bounds by Aouchiche and Hansen \cite{AouHan2011} in terms of order alone by about a factor of $\frac{3}{\delta+1}$. We further give lower bounds on the remoteness in terms of diameter or radius. Finally we show that the average distance of a graph, i.e., the average of the distances between all pairs of vertices, cannot exceed twice the proximity.http://comb-opt.azaruniv.ac.ir/article_13543_99e338e777d53b2fb451bb25a4de0578.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21281120160601The convex domination subdivision number of a graph43561354410.22049/cco.2016.13544ENM.DettlaffGdańsk University of TechnologyS.KosariAzarbaijan Shahid Madani UniversityM.LemańskaGdańsk University of TechnologyS.M.SheikholeslamiAzarbaijan Shahid Madani University0000-0003-2298-4744Journal Article20160622Let $G=(V,E)$ be a simple graph. A set $D\subseteq V$ is a dominating set of $G$ if every vertex in $V\setminus D$ has at least one neighbor in $D$. The distance $d_G(u,v)$ between two vertices $u$ and $v$ is the length of a shortest $(u,v)$-path in $G$. An $(u,v)$-path of length $d_G(u,v)$ is called an $(u,v)$-geodesic. A set $X\subseteq V$ is convex in $G$ if vertices from all $(a, b)$-geodesics belong to $X$ for any two vertices $a,b\in X$. A set $X$ is a convex dominating set if it is convex and dominating set. The {\em convex domination number} $\gamma_{\rm con}(G)$ of a graph $G$ equals the minimum cardinality of a convex dominating set in $G$. {\em The convex domination subdivision number} sd$_{\gamma_{\rm con}}(G)$ is the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the convex domination number. In this paper we initiate the study of convex domination subdivision number and we establish upper bounds for it. http://comb-opt.azaruniv.ac.ir/article_13544_b044108d0b0eedf90a89cf1f47c4f8e0.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21281120160601More skew-equienergetic digraphs57731354510.22049/cco.2016.13545ENCh.AdigaUniversity of Mysore0000-0002-3235-794xRakshithB RUniversity of MysoreJournal Article20160217Two digraphs of same order are said to be skew-equienergetic if their skew energies are equal. One of the open problems proposed by Li and Lian was to construct non-cospectral skew-equienergetic digraphs on <em>n</em> vertices. Recently this problem was solved by Ramane et al. In this paper, we give some new methods to construct new skew-equienergetic digraphs.http://comb-opt.azaruniv.ac.ir/article_13545_0f42ad1856ecb7c77844ab63bd68ed35.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21281120160601Bounds on the restrained Roman domination number of a graph75821355610.22049/cco.2016.13556ENH.Abdollahzadeh AhangarBabol Noshirvani University of Technology0000-0002-0038-8047S.R.MirmehdipourBabol Noshirvani University of TechnologyJournal Article20160808A {\em Roman dominating function} on a graph $G$ is a function $f:V(G)\rightarrow \{0,1,2\}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) =2$. A {\em restrained Roman dominating} function $f$ is a Roman dominating function if the vertices with label 0 induce a subgraph with no isolated vertex. The weight of a restrained Roman dominating function is the value $\omega(f)=\sum_{u\in V(G)} f(u)$. The minimum weight of a restrained Roman dominating function of $G$ is called the { \em restrained Roman domination number} of $G$ and denoted by $\gamma_{rR}(G)$. In this paper we establish some sharp bounds for this parameter. http://comb-opt.azaruniv.ac.ir/article_13556_af7da9ddc41c8343edb4835aaab47c2c.pdf