Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201A survey on the Intersection graphs of ideals of rings1211671424210.22049/cco.2021.26990.1176ENIvyChakrabartyIndependent Researcher0000-0003-3402-2032Joseph VargheseKureetharaChrist University0000-0001-5030-3948Journal Article20201031Let L(R) denote the set of all non-trivial left ideals of a ring R. The intersection graph of ideals of a ring R is an undirected simple graph denoted by G(R) whose vertices are in a one-to-one correspondence with L(R) and two distinct vertices are joined by an edge if and only if the corresponding left ideals of R have a non-zero intersection. The ideal structure of a ring reflects many ring theoretical properties. Thus much research has been conducted last few years to explore the properties of G(R). This is a survey of the developments in the study on the intersection graphs of ideals of rings since its introduction in 2009.http://comb-opt.azaruniv.ac.ir/article_14242_abf02f0de0796011d510761f1abc8cb7.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201On the total liar's domination of graphs1691751424310.22049/cco.2021.27219.1213ENNarjesSeyediDepartment of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, IranHamid RezaMaimaniShahid Rajaee Teacher Training UniversityAbolfazlTehranianDepartment of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, IranJournal Article20210415For a graph $G$, a set $L$ of vertices is called a total liar's domination if $|N_G(u)cap L|geq 2$ for any $uin V(G)$ and $|(N_G(u)cup N_G(v))cap L|geq 3$ for any distinct vertices $u,vin V(G)$. The total liar’s domination number is the cardinality of a minimum total liar’s<br />dominating set of $G$ and is denoted by $gamma_{TLR}(G)$. In this paper we study the total liar's domination numbers of join and products of graphs.http://comb-opt.azaruniv.ac.ir/article_14243_725863c96ed5c74301788ff79bb49bd3.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Complexity of the paired domination subdivision problem1771821424710.22049/cco.2021.27010.1180ENJafarAmjadiAzarbaijan Shahid Madani University0000-0001-9340-4773MustaphaChellaliUniversity of BlidaJournal Article20201118The paired domination subdivision number of a graph $G$ is the minimum number of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to increase the paired domination number of $G$. In this note, we show that the problem of computing the paired-domination subdivision number is NP-hard for bipartite graphs.http://comb-opt.azaruniv.ac.ir/article_14247_2b7da1c38b27ede26b28f0e041917bfc.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Algorithmic aspects of total Roman ${2}$-domination in graphs1831921426410.22049/cco.2021.27063.1189ENChakradharPNational Institute of Technology, WarangalVenkata Subba ReddyPNational Institute of Technology WarangalJournal Article20201229For a simple, undirected, connected graph $G$, a function $h : V rightarrow lbrace 0, 1, 2 rbrace$ is called a total Roman ${2}$-dominating function (TR2DF) if for every vertex $v$ in $V$ with weight $0$, either there exists a vertex $u$ in $N_G(v)$ with weight $2$, or at least two vertices $x, y$ in $N_G(v)$ each with weight $1$, and the subgraph induced by the vertices with weight more than zero has no isolated vertices. The weight of TR2DF $h$ is $sum_{p in V} h(p)$. The problem of determining TR2DF of minimum weight is called minimum total Roman {2}-domination problem (MTR2DP). We show that MTR2DP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a $2 (ln(Delta - 0.5) + 1.5)$-approximation algorithm for the MTR2DP and show that the same cannot have $(1 - delta) ln |V|$ ratio approximation algorithm for any $delta > 0$ unless $P = NP$. Next, we show that MTR2DP is APX-hard for graphs with $ Delta=4$. Finally, we show that the domination and TR2DF problems are not equivalent in computational complexity aspects.http://comb-opt.azaruniv.ac.ir/article_14264_93fdd90572f39e706ad1feba0e1d4260.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Eccentric completion of a graph1932011426510.22049/cco.2021.27079.1192ENManakkulam RohithRajaCHRIST (Deemed to be University), BangaloreTabitha AgnesMangamCHRIST (Deemed to be University),
BangaloreSudevNaduvathCHRIST (Deemed to be University),
Bangalore0000-0001-9692-4053Journal Article20210107The eccentric graph $G_e$ of a graph $G$ is a derived graph with the vertex set same as that of $G$ and two vertices in $G_e$ are adjacent if one of them is the eccentric vertex of the other. In this paper, the concepts of iterated eccentric graphs and eccentric completion of a graph are introduced and discussed.http://comb-opt.azaruniv.ac.ir/article_14265_08b4e4113d407f5f25883c3eccc49371.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Inverse problem for the Forgotten and the hyper Zagreb indices of trees2032091426610.22049/cco.2021.27034.1182ENJoseph VargheseKureetharaChrist University0000-0001-5030-3948AnjushaAsokDepartment of Mathematics, Christ University, Bangalore, India0000-0002-8255-9179Ismail NaciCangulDepartment of Mathematics
Uludag University,
Gorukle 16059 Bursa-Turkey0000 0002 0700 5774Journal Article20201129Let $G=(E(G),V(G))$ be a (molecular) graph with vertex set $V(G)$ and edge set $E(G)$. The forgotten Zagreb index and the hyper Zagreb index of G are defined by $F(G) = sum_{u in V(G)} d(u)^{3}$ and $HM(G) = sum_{uv in E(G)}(d(u)+d(v))^{2}$ where $d(u)$ and d(v) are the degrees of the vertices $u$ and $v$ in $G$, respectively. A recent problem called the inverse problem deals with the numerical realizations of topological indices. We see that there exist trees for all even positive integers with $F(G)>88$ and with $HM(G)>158$. Along with the result, we show that there exist no trees with $F(G) < 90$ and $HM(G) < 160$ with some exceptional even positive integers and hence characterize the forgotten Zagreb index and the hyper Zagreb index for trees.http://comb-opt.azaruniv.ac.ir/article_14266_96c5e70ed539dcd220803b9fb53ba7d2.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Extreme outer connected monophonic graphs2112261426810.22049/cco.2021.27042.1184ENGanesamoorthyK.Department of Mathematics, Coimbatore Institute of Technology
(Government Aided Autonomous Institution)
Coimbatore - 641 014, IndiaLakshmi PriyaSDepartment of Mathematics, Coimbatore Institute of Technology, CoimbatoreJournal Article20201210For a connected graph $G$ of order at least two, a set $S$ of vertices in a graph $G$ is said to be an textit{outer connected monophonic set} if $S$ is a monophonic set of $G$ and either $S=V$ or the subgraph induced by $V-S$ is connected. The minimum cardinality of an outer connected monophonic set of $G$ is the textit{outer connected monophonic number} of $G$ and is denoted by $m_{oc}(G)$. The number of extreme vertices in $G$ is its textit{extreme order} $ex(G)$. A graph $G$ is said to be an textit{extreme outer connected monophonic graph} if $m_{oc}(G)$ = $ex(G)$. Extreme outer connected monophonic graphs of order $p$ with outer connected monophonic number $p$ and extreme outer connected monophonic graphs of order $p$ with outer connected monophonic number $p-1$ are characterized. It is shown that for every pair $a, b$ of integers with $0 leq a leq b$ and $b geq 2$, there exists a connected graph $G$ with $ex(G) = a$ and $m_{oc}(G) = b$. Also, it is shown that for positive integers $r,d$ and $k geq 2$ with $r < d$, there exists an extreme outer connected monophonic graph $G$ with monophonic radius $r$, monophonic diameter $d$ and outer connected monophonic number $k$.http://comb-opt.azaruniv.ac.ir/article_14268_9a46437c0806e08d6d1d2388dd680b82.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Entire Wiener index of graphs2272451427110.22049/cco.2021.27234.1217ENIsmail NaciCANGULUludag University
Faculty of Arts and Science
Department of Mathematics
Gorukle, 16059
Bursa/Turkey0000 0002 0700 5774AnwarSalehDepartment of Mathematics, Faculty of Science, University of Jeddah, Jeddah, Saudi ArabiaAkramAlqesmahDepartment of Mathematics, University of Aden, YemenHanaaAlashwaliDepartment of Mathematics, Faculty of Science, University of Jeddah, Jeddah, Saudi ArabiaJournal Article20210428Topological indices are graph invariants computed usually by means of the distances or degrees of vertices of a graph. In chemical graph theory, a molecule can be modeled by a graph by replacing atoms by the vertices and bonds by the edges of this graph. Topological graph indices have been successfully used in determining the structural properties and in predicting certain physicochemical properties of chemical compounds. Wiener index is the oldest topological index which can be used for analyzing intrinsic properties of a molecular structure in chemistry. The Wiener index of a graph $G$ is equal to the sum of distances between all pairs of vertices of $G$. Recently, the entire versions of several indices have been introduced and studied due to their applications. Here we introduce the entire Wiener index of a graph. Exact values of this index for trees and some graph families are obtained, some properties and bounds for the entire Wiener index are established. Exact values of this new index for subdivision and $k$-subdivision graphs and some graph operations are obtained.http://comb-opt.azaruniv.ac.ir/article_14271_f1d0fdb137e0f5f8a1fa03a9ac4e93af.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Algorithmic aspects of certified domination in graphs2472551426910.22049/cco.2021.27302.1226ENPavan KumarJakkepalliIcfaiTech (Faculty of Science &amp;amp;amp; Technology)
ICFAI Foundation for Higher Education, Hyderabad, India0000-0001-6936-2358SubramanianArumugamDirector (n-CARDMATH)
Kalasalingam University
Anand Nagar, Krishnankoil-626 126
Tamil Nadu, IndiaHimanshuKhandelwalDepartment of Computer Science and Engineering, National Institute of Technology Warangal, Telangana, IndiaVenkata Subba ReddyP.National Institute of Technology WarangalJournal Article20210607A dominating set $ D $ of a graph $ G=(V,E) $ is called a certified dominating set of $ G $ if $vert N(v) cap (V setminus D)vert$ is either 0 or at least 2 for all $ v in D$. The certified domination number $gamma_{cer}(G) $ is the minimum cardinality of a certified dominating set of $ G $. In this paper, we prove that the decision problem corresponding to $gamma_{cer}(G) $ is NP-complete for split graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs. We also prove that it is linear time solvable for chain graphs, threshold graphs and bounded tree-width graphs.http://comb-opt.azaruniv.ac.ir/article_14269_0dabbd07d38631d59ef285a2fe950400.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Regular graphs with large Italian domatic number2572711426710.22049/cco.2021.27092.1194ENJeremyLyleDepartment of Mathematics and Computer Science, Olivet Nazarene University, Bourbonnais, ILJournal Article20210119For a graph $G$, an Italian dominating function is a function $f: V(G) rightarrow {0,1,2}$ such that for each vertex $v in V(G)$ either $f(v) neq 0$, or $sum_{u in N(v)} f(u) geq 2$. If a family $mathcal{F} = {f_1, f_2, dots, f_t}$ of distinct Italian dominating functions satisfy $sum^t_{i = 1} f_i(v) leq 2$ for each vertex $v$, then this is called an Italian dominating family. In [L. Volkmann, The {R}oman {${2}$}-domatic number of graphs, Discrete Appl. Math. 258 (2019), 235--241], Volkmann defined the Italian domatic number of $G$, $d_{I}(G)$, as the maximum cardinality of any Italian dominating family. In this same paper, questions were raised about the Italian domatic number of regular graphs. In this paper, we show that two of the conjectures are false, and examine some exceptions to a Nordhaus-Gaddum type inequality.http://comb-opt.azaruniv.ac.ir/article_14267_881830df7952eed74910cdc28fcdf2d1.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201A note on Roman $k$-tuple domination number2732741427810.22049/cco.2021.27350.1242ENNoorA'lawiah Abd AzizUniversiti Sains MalaysiaNaderJafari RadShahed UniversityJournal Article20210725For an integer $kgeq 2$, a Roman $k$-tuple dominating function, (or just RkDF), in a graph $G$ is a function $f colon V(G) rightarrow {0, 1, 2}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least $k$ vertices $v$ for which $f(v) = 2$, and every vertex $u$ for which $f(u) neq 0$ is adjacent to at least $k-1$ vertices $v$ for which $f(v) = 2$. The Roman $k$-tuple domination number of $G$ is the minimum weight of an RkDF in $G$. In this note we settle two problems posed in [Roman $k$-tuple Domination in Graphs, Iranian J. Math. Sci. Inform. 15 (2020), 101--115].http://comb-opt.azaruniv.ac.ir/article_14278_13648d83af1162cb8b52ce5c5f22d3bc.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Terminal status of vertices and terminal status connectivity indices of graphs with its applications to properties of cycloalkanes2753001427910.22049/cco.2021.27254.1221ENHarishchandra S.RamaneDepartment of Mathematics, Karnatak University, Dharwad0000-0003-3122-1669KavitaBhajantriDepartment of Mathematics, Karnatak University, DharwadDeepa V.KitturmathDepartment of Mathematics, Karnatak University, DharwadJournal Article20210512In this article the terminal status of a vertex and terminal status connectivity indices of a connected graph have introduced. Explicit formulae for the terminal status of vertices and for terminal status connectivity indices of certain graphs are obtained. Also some bounds are given for these indices. Further these indices are used for predicting the physico-chemical properties of cycloalkanes and it is observed that the correlation of physico-chemical properties of cycloalkanes with newly introduced indices is better than the correlation with other indices.http://comb-opt.azaruniv.ac.ir/article_14279_1227870152d900fbe70bd86dbd6e30aa.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Enumeration of k-noncrossing trees and forests3013111435310.22049/cco.2022.26903.1162ENIsaac OwinoOkothDepartment of Pure and Applied Mathematics, School of Mathematics, Statistics and Actuarial Science, Maseno University, Maseno, Kenya0000-0003-4503-4733Journal Article20200809A $k$-noncrossing tree is a noncrossing tree where each node receives a label in ${1,2,ldots,k}$ such that the sum of labels along an ascent does not exceed $k+1,$ if we consider a path from a fixed vertex called the root. In this paper, we provide a proof for a formula that counts the number of $k$-noncrossing trees in which the root (labelled by $k$) has degree $d$. We also find a formula for the number of forests in which each component is a $k$-noncrossing tree whose root is labelled by $k$.http://comb-opt.azaruniv.ac.ir/article_14353_690e707a9886b43c3feb284d6b4c5f5a.pdf