Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21281120160630Sufficient conditions on the zeroth-order general Randic index for maximally edge-connected digraphs1131351410.22049/cco.2016.13514ENL.VolkmannRWTH Aachen University0000-0003-3496-277XJournal Article20151120Let <em>D </em>be a digraph with vertex set <em>V(D)</em> .For vertex <em>v</em> <em>V(D)</em>, the degree of <em>v</em>, denoted by <em>d(v)</em>, is defined as the minimum value if its out-degree and its in-degree . Now let <em>D</em> be a digraph with minimum degree and edge-connectivity If is real number, then the zeroth-order general Randic index is defined by . A digraph is maximally edge-connected if . In this paper we present sufficient conditions for digraphs to be maximally edge-connected in terms of the zeroth-order general Randic index, the order and the minimum degree when Using the associated digraph of a graph, we show that our results include some corresponding known results on graphs.Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21281120160601The minus k-domination numbers in graphs15281353410.22049/cco.2016.13534ENN.DehgardiSirjan University of Technology, Sirjan 78137, IranJournal Article20160311For any integer , a minus <em>k</em>-dominating function is afunction f : V (G) {-1,0, 1} satisfying w) for every vertex v, where <em>N(v) ={u </em> <em>V(G) | uv </em> <em> E(G)}</em> and N[v] =N(v)cup {v}. The minimum of the values of v), taken over all minus<em>k</em>-dominating functions <em>f</em>, is called the minus <em>k-</em>dominationnumber and is denoted by $gamma_k^-(G)$ . In this paper, we introduce the study of minus <em>k</em>-domination in graphs and we present several sharp lower bounds on the minus <em>k</em>-domination number for general graphs.Azarbaijan 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$<br />is the arithmetic mean of the distances from $v$ to all<br />other vertices of $G$. The proximity $pi(G)$ and the remoteness $rho(G)$<br />of $G$ are defined as the minimum and maximum average<br />distance of the vertices of $G$. <br />In this paper we investigate the difference between proximity or remoteness and the classical distance<br />parameters diameter and radius. <br />Among other results we show that in a graph of order<br />$n$ and minimum degree $delta$ the difference between<br />diameter and proximity and the difference between<br />radius and proximity cannot exceed <br />$frac{9n}{4(delta+1)}+c_1$ and <br />$frac{3n}{4(delta+1)}+c_2$, respectively, for <br />constants $c_1$ and $c_2$ which depend on $delta$<br />but not on $n$. These bounds improve bounds by<br />Aouchiche and Hansen cite{AouHan2011} in terms of<br />order alone by about a factor of $frac{3}{delta+1}$. <br />We further give lower bounds on the remoteness in<br />terms of diameter or radius. Finally we show that<br />the average distance of a graph, i.e., the average of<br />the distances between all pairs of vertices, cannot<br />exceed twice the proximity.Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21281120160808The 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 UniversityJournal Article20160622Let $G=(V,E)$ be a simple graph. A set $Dsubseteq V$ is a<br />dominating set of $G$ if every vertex in $Vsetminus D$ has at<br />least one neighbor in $D$. The distance $d_G(u,v)$ between two<br />vertices $u$ and $v$ is the length of a shortest $(u,v)$-path in<br />$G$. An $(u,v)$-path of length $d_G(u,v)$ is called an<br />$(u,v)$-geodesic. A set $Xsubseteq V$ is convex in $G$ if<br />vertices from all $(a, b)$-geodesics belong to $X$ for any two<br />vertices $a,bin X$. A set $X$ is a convex dominating set if it is<br />convex and dominating set. The {em convex domination number}<br />$gamma_{rm con}(G)$ of a graph $G$ equals the minimum<br />cardinality of a convex dominating set in $G$. {em The convex<br />domination subdivision number} sd$_{gamma_{rm con}}(G)$ is the<br />minimum number of edges that must be subdivided (each edge in $G$<br />can be subdivided at most once) in order to increase the convex<br />domination number. In this paper we initiate the study of convex<br />domination subdivision number and we establish upper bounds for<br />it.Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21281120160810More skew-equienergetic digraphs57731354510.22049/cco.2016.13545ENCh.AdigaUniversity of MysoreRakshithB 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.Azarbaijan 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<br />$f:V(G)rightarrow {0,1,2}$ satisfying the condition that every<br />vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex<br />$v$ for which $f(v) =2$. {color{blue}A {em restrained Roman dominating}<br />function} $f$ is a {color{blue} Roman dominating function if the vertices with label 0 induce<br />a subgraph with no isolated vertex.} The weight of a restrained Roman dominating function is<br />the value $omega(f)=sum_{uin V(G)} f(u)$. The minimum weight of a<br />restrained Roman dominating function of $G$ is called the { em<br />restrained Roman domination number} of $G$ and denoted by $gamma_{rR}(G)$.<br />In this paper we establish some sharp bounds for this parameter.