Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Restrained double Italian domination in graphs1111429710.22049/cco.2021.27334.1236ENLutzVolkmannRWTH Aachen University0000-0003-3496-277XJournal Article20210616Let $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.http://comb-opt.azaruniv.ac.ir/article_14297_121bc675d7489ec214bf8345ae93be3e.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Some new bounds on the modified first Zagreb index13211428110.22049/cco.2021.27159.1205ENIgorMilovanovićFaculty of Electronic Engineering, University of Nis, Nis, SerbiaEminaMilovanovićFaculty of Electronic EngineeringMarjanMatejićFaculty of Electronic EngineeringAkbarAliUniversity of Hail, Saudi Arabia0000-0001-8160-4196Journal Article20210226Let $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.http://comb-opt.azaruniv.ac.ir/article_14281_b184e449936b5b45754b4dff89027329.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Vertex-edge Roman domination in graphs: complexity and algorithms23371428010.22049/cco.2021.27163.1206ENManjayKumarDepartment of Computer Science and Engineering, National Institute of Technology, Warangal, IndiaVenkata Subba ReddyPDepartment of Computer Science and Engineering, National Institute of Technology, Warangal, IndiaJournal Article20210304For 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.http://comb-opt.azaruniv.ac.ir/article_14280_43d998ca89041cf76a7055446c9b2987.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Signed total Italian k-domatic number of a graph39521429210.22049/cco.2021.27165.1207ENLutzVolkmannRWTH Aachen University0000-0003-3496-277XJournal Article20210304Let $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.http://comb-opt.azaruniv.ac.ir/article_14292_79c85f689c24074952889963f65b0434.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301The stress of a graph53651428210.22049/cco.2021.27320.1231ENRakshaPoojaryDepartment of Data Science, PSPH, Manipal Academy of Higher Education, Manipal0000-0002-6553-8026Arathi BhatKDepartment of Mathematics, MIT, Manipal Academy of Higher Education, Manipal0000-0002-1526-5760SubramanianArumugamDirector (n-CARDMATH)
Kalasalingam University
Anand Nagar, Krishnankoil-626 126
Tamil Nadu, IndiaManjunatha PrasadKaranthaCentre for Advanced Research in Applied Mathematics and Statistics, Manipal Academy of Higher Education, ManipalJournal Article20210623Stress 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$.http://comb-opt.azaruniv.ac.ir/article_14282_09edb34f88f77b9f57f5d03d3f269826.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301On the distance spectra of product of signed graphs67761430010.22049/cco.2021.27304.1227ENShijinT.V.Department of Mathematics, Central University of Kerala, Kasaragod, India.0000-0002-9850-4674SooryaP.Department of Mathematics, Central University of Kerala, Kasaragod, India.Shahul HameedK.Department of Mathematics, K M M Government Women's College, Kannur, India.GerminaK. A.Department of Mathematics, Central University of Kerala, Kasaragod, India0000-0002-2643-3416Journal Article20210610In 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.http://comb-opt.azaruniv.ac.ir/article_14300_e7243fd35ad59ba27b4b65556f3996cc.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Some families of $alpha$-labeled subgraphs of the integral grid771011430510.22049/cco.2021.26989.1175ENChristianBarrientosDepartment of Mathematics
Valencia College
Orlando, FL 32832
United States0000-0003-2838-8687SarahMinionDepartment of Mathematics
Full Sail University
Orlando, FL 32792
United States0000-0002-8523-3369Journal Article20201031In 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.http://comb-opt.azaruniv.ac.ir/article_14305_0bd702cdba73b058600a24b871f835ca.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301On Randić spectrum of zero divisor graphs of commutative ring $mathbb{Z}_{n} $1031131430610.22049/cco.2021.27202.1212ENBilalRatherUniversity of Kashmir0000-0003-1381-0291ShariefuddinPirzadaDepartment of Mathematics, HazratbalImranBhatCentral University of KashmirTariqChishtiUniversity of KashmirJournal Article20210404For 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.http://comb-opt.azaruniv.ac.ir/article_14306_be0f6e47290f9d638ea0cdbfb812c923.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Covering total double Roman domination in graphs1151251432210.22049/cco.2021.27443.1265ENAtiehTeymourzadehDepartment of Mathematics, University of Mazandaran, Babolsar, Iran0000000150172570Doost AliMojdehDeparttment of Mathematics, University of Mazandaran0000-0001-9373-3390Journal Article20211004For 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.http://comb-opt.azaruniv.ac.ir/article_14322_323e2149f7da57cd59b0062abf209a20.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Efficient algorithms for independent Roman domination on some classes of graphs1271401432310.22049/cco.2021.27305.1228ENAbolfazlPoureidiShahrood University of TechnologyJournal Article20210611Let $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.http://comb-opt.azaruniv.ac.ir/article_14323_4bd9faf4ec151ad46dfc07a93bed4b9a.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301On the Zagreb indices of graphs with given Roman domination number1411521432410.22049/cco.2021.27439.1263ENAyu Ameliatul ShahilahAhmad JamriMENGGABANG TELIPOT
KUALA NERUSRoslanHasniUniversiti Malaysia Terengganu(UMT), MalaysiaSharifah KartiniSaid HusainUniversiti Putra Malaysia(UPM)Journal Article20210902Let $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.http://comb-opt.azaruniv.ac.ir/article_14324_9c5f1f9cdee97c3e03b866d32fa67a9e.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Bounds for fuzzy Zagreb Estrada index1531601432610.22049/cco.2021.27333.1235ENMaheshKaleNMIMS Deemed tobe University, Mumbai.0000-0003-2340-8562MiniraniNairNMIMS Deemed to UniversityJournal Article20210715Let $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.http://comb-opt.azaruniv.ac.ir/article_14326_d1f07895087ac5deb1ac9e367ca5a05f.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Unicyclic graphs with maximum Randić indices1611721432710.22049/cco.2021.27230.1216ENRoslanHasniUMT, MalaysiaNor HafizahMd HusinUniversiti Pendidikan Sultan IdrisZhibinDuSchool of Mathematics and Statistics, Zhaoqing University,
Zhaoqing 526061, ChinaJournal Article20210427The 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.http://comb-opt.azaruniv.ac.ir/article_14327_6555b5e7ba897c85af34e06ed66c2deb.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301On perfectness of annihilating-ideal graph of $mathbb{Z}_n$1731811432810.22049/cco.2021.27382.1252ENManideepaSahaPresidency University, KolkataSucharitaBiswasPresidency University, KolkataAngsumanDasDepartment of Mathematics, Presidency University, KolkataJournal Article20210831The 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.http://comb-opt.azaruniv.ac.ir/article_14328_df3f829c2e7dfbee3bdc028abc687ae5.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Remarks on the restrained Italian domination number in graphs1831911432910.22049/cco.2021.27471.1269ENLutzVolkmannRWTH Aachen University0000-0003-3496-277XJournal Article20211021Let $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.http://comb-opt.azaruniv.ac.ir/article_14329_1ab676fb95dc17392b17649fcfc8bc0a.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Sombor index of some graph transformations1932051434010.22049/cco.2021.27484.1272ENHarishchandra S.RamaneDepartment of Mathematics, Karnatak University, Dharwad0000-0003-3122-1669IvanGutmanUniversity of Kragujevac0000-0001-9681-1550KavitaBhajantriDepartment of Mathematics, Karnatak University, DharwadDeepa V.KitturmathDepartment of Mathematics, Karnatak University, DharwadJournal Article20211030The 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. http://comb-opt.azaruniv.ac.ir/article_14340_7ace5e93139b6507fbe4366cc8178fdd.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Signed bicyclic graphs with minimal index2072411434810.22049/cco.2022.27346.1241ENMaurizioBrunettiDipartimento di Matematica e Applicazioni R. Caccioppoli. Universita' di Napoli Federico II0000-0002-2742-1919AdrianaCiampellaDipartimento di Matematica e Applicazioni R. Caccioppoli. Universita' di Napoli Federico IIJournal Article20210724The 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.http://comb-opt.azaruniv.ac.ir/article_14348_9f0156787274798785c37d2073e8e83d.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Improved bounds for Kirchhoff index of graphs2432511434910.22049/cco.2022.27492.1275ENŞ. BurcuBozkurt AltındağNoMarjanMatejićFaculty of Electronic Engineering, University of Niš, Niš, SerbiaIgorMilovanovićFaculty of Electronic Engineering, University of Niš, Niš, SerbiaEminaMilovanovićFaculty of Electronic Engineering, University of Niš, Niš, SerbiaJournal Article20211101Let $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.http://comb-opt.azaruniv.ac.ir/article_14349_70ba214ed83cef21373f8882434e7125.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301Further study on "an extended shortest path problem A data envelopment analysis approach"2532591435210.22049/cco.2022.27510.1280ENJavadTayyebiBirjand university of technology0000-0002-7559-3870AlirezaAmirteymooriFull professor in Applied Mathematics & Operations Research, Islamic Azad University of Rasht, Iran.Journal Article20211110Amirteimoori 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.http://comb-opt.azaruniv.ac.ir/article_14352_daae7c08673222d8d10445fb190c76f1.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21288120230301A new upper bound on the independent $2$-rainbow domination number in trees2612701435510.22049/cco.2022.27641.1305ENNaderJafari RadShahed UniversityElhamGholamiIslamic Azad UniversityATehranian‎Islamic Azad UniversityHamidRasouliIslamic Azad University,Journal Article20211118A $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.http://comb-opt.azaruniv.ac.ir/article_14355_4f1fe4a7a66211a655541d57e894afed.pdf