Communications in Combinatorics and Optimization
Volume:8 Issue: 1, Winter 2023

Let $G$ be a graph with vertex set $V(G)$. A double Italian dominating function (DIDF) is a function $f:V(G)longrightarrow {0,1,2,3}$ having the property that $f(N[u])geq 3$ for every vertex $uin V(G)$ with $f(u)in {0,1}$, where $N[u]$ is the closed neighborhood of $u$. If $f$ is a DIDF on $G$, then let $V_0={vin V(G): f(v)=0}$. A restrained double Italian dominating function (RDIDF) is a double Italian dominating function $f$ having the property that the subgraph induced by $V_0$ does not have an isolated vertex. The weight of an RDIDF $f$ is the sum $sum_{vin V(G)}f(v)$, and the minimum weight of an RDIDF on a graph $G$ is the restrained double Italian domination number. We present bounds and Nordhaus-Gaddum type results for the restrained double Italian domination number. In addition, we determine the restrained double Italian domination number for some families of graphs.

Let $G$ be a graph containing no isolated vertices. For the graph $G$, its modified first Zagreb index is defined as the sum of reciprocals of squares of vertex degrees of $G$. This article provides some new bounds on the modified first Zagreb index of $G$ in terms of some other well-known graph invariants of $G$. From the obtained bounds, several known results follow directly.

For a simple, undirected graph $G(V,E)$, a function $h : V(G) rightarrow lbrace 0, 1, 2rbrace$ such that each edge $ (u,v)$ of $G$ is either incident with a vertex with weight at least one or there exists a vertex $w$ such that either $(u,w) in E(G)$ or  $(v,w) in E(G)$ and $h(w) = 2$, is called a vertex-edge Roman dominating function (ve-RDF) of $G$. For a graph $G$, the smallest possible weight of a ve-RDF of $G$ which is denoted by $gamma_{veR}(G)$, is known as the textit{vertex-edge Roman domination number} of $G$. The problem of determining  $gamma_{veR}(G)$ of a graph $G$ is called minimum vertex-edge Roman domination problem (MVERDP). In this article, we show that the problem of deciding if $G$ has a ve-RDF of weight at most $l$ for star convex bipartite graphs, comb convex bipartite graphs, chordal graphs and planar graphs is NP-complete. On the positive side, we show that MVERDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, a 2-approximation algorithm for MVERDP is presented. It is also shown that vertex cover and vertex-edge Roman domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming  formulation for MVERDP is presented.

Let $kge 1$ be an integer, and let $G$ be a finite and simple graph with vertex set $V(G)$. A  signed total Italian $k$-dominating function on a graph $G$ is a function $f:V(G)longrightarrow {-1, 1, 2}$ such that $sum_{uin N(v)}f(u)ge k$ for every $vin V(G)$, where $N(v)$ is the neighborhood of $v$, and each vertex $u$ with $f(u)=-1$ is adjacent to a vertex $v$ with $f(v)=2$ or to two vertices $w$ and $z$ with $f(w)=f(z)=1$. A set ${f_1,f_2,ldots,f_d}$ of distinct signed total Italian $k$-dominating functions on $G$ with the property that $sum_{i=1}^df_i(v)le k$ for each $vin V(G)$, is called a signed total Italian $k$-dominating family (of functions) on $G$. The maximum number of functions in a signed total Italian $k$-dominating family on $G$ is the  signed total Italian k-domatic number of $G$, denoted by $d_{stI}^k(G)$. In this paper we initiate the study of signed total Italian k-domatic numbers in graphs, and we present sharp bounds for $d_{stI}^k(G)$. In addition, we determine the signed total Italian k-domatic number of some graphs.

Stress is an important centrality measure of graphs applicable to the study of social and biological networks. We study the stress of paths, cycles, fans and wheels. We determine the stress of a cut vertex of a graph $G$, when $G$ has at most two cut vertices. We have also identified the graphs with minimum stress and maximum stress in the family of all trees of order $n$ and in the family of all complete bipartite graphs of order $n$.

In this article, we study the distance matrix of the product of signed graphs such as the Cartesian product and the lexicographic product in terms of the signed distance matrices of the factor graphs. Also, we discuss the signed distance spectra of some special classes of product of signed graphs.

In this work we study the most restrictive variety of graceful labelings, that is, we study the existence of an $alpha$-labeling for some families of graphs that can be embedded in the integral grid. Among the categories of graphs considered here we have a subfamily of 2-link fences, a subfamily of column-convex polyominoes, and a subfamily of irregular cyclic-snakes. We prove that under some conditions, the a-labelings of these graphs can be transformed into harmonious labelings. We also present a closed formula for the number of 2-link fences examined here.

For a finite commutative ring $ mathbb{Z}_{n} $ with identity $ 1neq 0 $, the zero divisor graph $ Gamma(mathbb{Z}_{n}) $ is a simple connected graph having vertex set as the set of non-zero zero divisors, where two vertices $ x $ and $ y $ are adjacent if and only if $ xy=0 $. We find the Randi'c spectrum of the zero divisor graphs $ Gamma(mathbb{Z}_{n}) $, for various values of $ n$ and characterize $ n $ for which $ Gamma(mathbb{Z}_{n}) $ is Randi'c integral.

For a graph $G$ with no isolated vertex, a covering total double Roman dominating function ($CTDRD$ function) $f$ of $G$ is a total double Roman dominating function ($TDRD$ function) of $G$ for which the set ${vin V(G)| f(v)ne 0}$ is a vertex cover set. The covering total double Roman domination number $gamma_{ctdR}(G)$ equals the minimum weight of an $CTDRD$ function on $G$. An $CTDRD$ function on $G$ with weight $gamma_{ctdR} (G)$ is called a $gamma_{ctdR} (G)$-function. In this paper, the graphs $G$ with small $gamma_{ctdR} (G)$ are characterised. We show that the decision problem associated with $CTDRD$ is $NP$-complete even when restricted to planer graphs with maximum degree at most four. We then show that for every graph $G$ without isolated vertices, $gamma_{oitR}(G)<gamma_{ctdR}(G)< 2gamma_{oitR}(G)$ and for every tree $T$, $2beta(T)+1leq gamma_{ctdR}(T)leq4beta(T)$, where $gamma_{oitR}(G)$ and $beta(T)$ are the outer independent total Roman domination number of $G$, and the minimum vertex cover number of $T$ respectively. Moreover we investigate the $gamma_{ctdR}$ of corona of two graphs.

Let $G=(V,E)$ be a given graph of order $n $. A function $f : V to {0,1, 2}$ is an independent Roman dominating function (IRDF) on $G$ if for every vertex $vin V$ with $f(v)=0$ there is a vertex $u$ adjacent to $v$ with $f(u)=2$ and ${vin V:f(v)> 0}$ is an independent set. The weight of an IRDF $f$ on $G $ is the value $f(V)=sum_{vin V}f(v)$. The minimum weight of an IRDF among all IRDFs on $G$ is called the independent Roman domination number of~$G$. In this paper, we give algorithms for computing the independent Roman domination number of $G$ in $O(|V|)$ time when $G=(V,E)$ is a tree, unicyclic graph or proper interval graph.

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. The two Zagreb indices $M_1=sum_{vin V(G)} d^2_G(v)$ and $M_2=sum_{uvin E(G)} d_G(u)d_G(v)$ are vertex degree based graph invariants that have been introduced in the 1970s and extensively studied ever since. {In this paper, we first give a lower bound on the first Zagreb index of trees with given Roman domination number and we characterize all extremal trees. Then we present upper bound for Zagreb indices of unicyclic and bicyclic graphs with given Roman domination number.

Let $G(V,sigma ,mu )$ be a fuzzy graph of order $n$, where $sigma(u)$ is the vertex membership, $mu(u,v)$ is membership value of an edge and $mu (u)$ is the strength of vertex. The first fuzzy Zagreb index is the sum $sigma ({{u}_{i}})mu ({{u}_{i}})+sigma ({{u}_{j}})mu ({{u}_{j}})$ where ${{{u}_{i}}{{u}_{j}}in {{mu }}}$ and the corresponding fuzzy Zagreb matrix is the square matrix of order $n$ whose $(i,j)^{th}$ entry whenever $ineq j$, is $sigma ({{u}_{i}})mu ({{u}_{i}})+sigma ({{u}_{j}})mu ({{u}_{j}})$ and zero otherwise. In this paper, we introduce the Zagreb Estrada index of fuzzy graphs and establish some bounds for it.

The Randi'c index $R(G)$ of a graph $G$ is the sum of the weights $(d_u d_v)^{-frac{1}{2}}$ of all edges $uv$ in $G$, where $d_u$ denotes the degree of vertex $u$. Du and Zhou [On Randi'c indices of trees, unicyclic graphs, and bicyclic graphs, Int. J. Quantum Chem. 111 (2011), 2760--2770] determined the $n$-vertex unicyclic graphs with the third for $nge 5$, the fourth for $nge 7$ and the fifth for $nge 8$ maximum Randi'c indices. Recently, Li et al. [The Randi{' c} indices of trees, unicyclic graphs and bicyclic graphs, Ars Combin. 127 (2016), 409--419] obtained the $n$-vertex unicyclic graphs with the sixth and the seventh for $nge 9$ and the eighth for $nge 10$ maximum Randi'c indices. In this paper, we characterize the $n$-vertex unicyclic graphs with the ninth, the tenth, the eleventh, the twelfth and the thirteenth maximum Randi'c values.

The annihilating-ideal graph of a commutative ring $R$ with unity is defined as the graph $AG(R)$ whose vertex set is the set of all non-zero ideals with non-zero annihilators and two distinct vertices $I$ and $J$ are adjacent if and only if $IJ = 0$. Nikandish et.al. proved that $AG(mathbb{Z}_n)$ is weakly perfect. In this short paper, we characterize $n$ for which $AG(mathbb{Z}_n)$ is perfect.

Let $G$ be a graph with vertex set $V(G)$. An Italian dominating function (IDF) is a function $f:V(G)longrightarrow {0,1,2}$ having the property that that $f(N(u))geq 2$ for every vertex $uin V(G)$ with $f(u)=0$, where $N(u)$ is the neighborhood of $u$. If $f$ is an IDF on $G$, then let $V_0={vin V(G): f(v)=0}$. A restrained Italian dominating function (RIDF) is an Italian dominating function $f$ having the property that the subgraph induced by $V_0$ does not have an isolated vertex. The weight of an RIDF $f$ is the sum $sum_{vin V(G)}f(v)$, and the minimum weight of an RIDF on a graph $G$ is the restrained Italian domination number. We present sharp bounds for the restrained Italian domination number, and we determine the restrained Italian domination number for some families of graphs.

* The formulas are not displyed corrrectly.

The Sombor index of the graph $G$ is a recently introduced degree based topological index. It is defined as $SO = sum_{uv in E(G)} sqrt{d(u)^2+d(v)^2}$, where $d(u)$ is the degree of the vertex u and $E(G)$ is the edge set of $G$.  In this paper we calculate $SO$ of some graph transformations.

The index $lambda_1(Gamma)$ of a signed graph $Gamma=(G,sigma)$ is just the largest eigenvalue of its adjacency matrix. For any $n geqslant 4$ we identify the signed graphs achieving the minimum index in the class of signed bicyclic graphs with $n$ vertices. Apart from the $n=4$ case, such graphs are obtained by considering a starlike tree with four branches of suitable length (i.e. four distinct paths joined at their end vertex $u$) with two additional negative independent edges pairwise joining the four vertices adjacent to $u$. As a by-product, all signed bicyclic graphs containing  a theta-graph and whose index is less than $2$ are detected.

Let $G$ be a simple connected graph with n vertices. The Kirchhoff index of $G$ is defined as $Kf (G) = nsum_{i=1}^{n-1}1/μ_i$, where $mu_1ge mu_2ge dotsge mu_{n-1}>mu_n=0$ are the Laplacian eigenvalues of $G$. Some bounds on $Kf (G)$ in terms of graph parameters such as the number of vertices, the number of edges, first Zagreb index, forgotten topological index, etc., are presented. These bounds improve some previously known bounds in the literature.

Amirteimoori proposed an approach based on data envelopment analysis (DEA) for  multi-objective path problems on networks whose arcs contain multiple positive and negative attributes [A. Amirteimoori, An extended shortest path problem: A data envelopment analysis approach, Applied Mathematics Letters 25 (2012) 1839-1843]. The approach is to define a relative efficiency for each arcs using DEA models, and then to solve a longest path problem for obtaining a path with maximum efficiency. In this note, we focus on two drawbacks of the approach and illustrate them using examples. Then, we propose remedies to eliminate them.

A $2$-rainbow dominating function on a graph $G$ is a function $g$ that assigns to each vertex a set of colors chosen from the subsets of ${1, 2}$ so that for each vertex with $g(v) =emptyset$ we have $bigcup_{uin N(v)} g(u) = {1, 2}$. The weight of a $2$-rainbow dominating function $g$ is the value $w(g) = sum_{vin V(G)} |f(v)|$. A $2$-rainbow dominating function $g$ is an independent $2$-rainbow dominating function if no pair of vertices assigned nonempty sets are adjacent. The $2$-rainbow domination number $gamma_{r2}(G)$ (respectively, the independent $2$-rainbow domination number $i_{r2}(G)$) is the minimum weight of a $2$-rainbow dominating function (respectively, independent $2$-rainbow dominating function) on $G$. We prove that for any tree $T$ of order $ngeq 3$, with $ell$ leaves and $s$ support vertices, $i_{r2}(T)leq (14n+ell+s)/20$, thus improving the bound given in [Independent 2-rainbow domination in trees, Asian-Eur. J. Math. 8 (2015) 1550035] under certain conditions.