Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901Reconfiguring Minimum Independent Dominating Sets in Graphs3894111468210.22049/cco.2023.28965.1797ENRichard CBrewsterDepartment of Mathematics and Statistics, Thompson Rivers University, 805 TRU Way,
Kamloops, B.C., Canada0000-0002-3932-9570Christina MMynhardtDepartment of Mathematics and Statistics, University of Victoria, PO BOX 1700 STN CSC, Victoria, B.C. Canada0000-0001-6981-676XLaura ETeshimaDepartment of Mathematics and Statistics, University of Victoria, PO BOX 1700 STN CSC, Victoria, B.C. CanadaJournal Article20230901The independent domination number $i(G)$ of a graph $G$ is the minimum cardinality of a maximal independent set of $G$, also called an $i(G)$-set. The $i$-graph of $G$, denoted $\mathscr{I}(G)$, is the graph whose vertices correspond to the $i(G)$-sets, and where two $i(G)$-sets are adjacent if and only if they differ by two adjacent vertices. We show that not all graphs are $i$-graph realizable, that is, given a target graph $H$, there does not necessarily exist a seed graph $G$ such that $H \cong \mathscr{I}(G)$. Examples of such graphs include $K_{4}-e$ and $K_{2,3}$. We build a series of tools to show that known $i$-graphs can be used to construct new $i$-graphs and apply these results to build other classes of $i$-graphs, such as block graphs, hypercubes, forests, cacti, and unicyclic graphs.http://comb-opt.azaruniv.ac.ir/article_14682_00b259f42904b5f195c552f0b64e33f8.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901Graphoidally Independent Infinite Cactus4134231447310.22049/cco.2022.27745.1338ENDeeptiJainDepartment of Mathematics, Sri Venkateswara College, University of Delhi, Delhi, IndiaPurnimaGuptaAdjunct Professor (Prof of Eminence), Department of Mathematics, Ramanujan College,
University of Delhi, Delhi, IndiaJournal Article20220331A graphoidal cover of a graph $G$ (not necessarily finite) is a collection $\psi$ of paths (not necessarily finite, not necessarily open) satisfying the following axioms: (GC-1) Every vertex of $G$ is an internal vertex of at most one path in $\psi$, and (GC-2) every edge of $G$ is in exactly one path in $\psi$. The pair $(G, \psi)$ is called a graphoidally covered graph and the paths in $\psi$ are called the $\psi$-edges of $G$. In a graphoidally covered graph $(G, \psi)$, two distinct vertices $u$ and $v$ are $\psi$-adjacent if they are the ends of an open $\psi$-edge. A graphoidally covered graph $(G, \psi)$ in which no two distinct vertices are $\psi$-adjacent is called $\psi$-independent and the graphoidal cover $\psi$ is called a totally disconnecting graphoidal cover of $G$. Further, a graph possessing a totally disconnecting graphoidal cover is called a graphoidally independent graph. The aim of this paper is to establish complete characterization of graphoidally independent infinite cactus.http://comb-opt.azaruniv.ac.ir/article_14473_5e7ec1a2240a429fa913452fe0df7e76.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901PI Index of Bicyclic Graphs4254361451410.22049/cco.2023.27817.1360ENManjuSCDepartment of Mathematics, School of Physical Sciences, Kochi,
Amrita Vishwa Vidyapeetham, IndiaSomasundaramKDepartment of Mathematics, Amrita School of Physical Sciences, Coimbatore, Amrita Vishwa Vidyapeetham, India0000-0003-2226-1845Journal Article20220517The PI index of a graph $G$ is given by $PI(G)=\sum_{e\in E(G)}(\left|V(G)\right|-N_G(e))$, where $N_G(e)$ is the number of equidistant vertices for the edge $e$. Various topological indices of bicyclic graphs have already been calculated. In this paper, we obtained the exact value of the PI index of bicyclic graphs. We also explore the extremal graphs among all bicyclic graphs with respect to the PI index. Furthermore, we calculate the PI index of a cactus graph and determine the extremal values of the PI index among cactus graphs.http://comb-opt.azaruniv.ac.ir/article_14514_16693d8f0f62ff339f2efb5cc772d1df.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901Coalition of cubic graphs of order at most $10$4374501454210.22049/cco.2023.28328.1507ENSaeidAlikhaniDepartment of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran0000-0002-1801-203XHamidrezaGolmohammadiNovosibirsk State University, Pirogova str. 2, Novosibirsk, 630090, RussiaSobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, RussiaElena V.KonstantinovaNovosibirsk State University, Pirogova str. 2, Novosibirsk, 630090, RussiaSobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, RussiaJournal Article20230217The coalition in a graph $G$ consists of two disjoint sets of vertices $V_{1}$ and $V_{2}$, neither of which is a dominating set but whose union $V_{1}\cup V_{2}$, is a dominating set. A coalition partition in a graph $G$ is a vertex partition $\pi$ = $\{V_1, V_2,\dots, V_k \}$ such that every set $V_i \in \pi$ is not a dominating set but forms a coalition with another set $V_j\in \pi$ which is not a dominating set. The coalition number $C(G)$ equals the maximum $k$ of a coalition partition of $G$. In this paper, we compute the coalition numbers of all cubic graphs of order at most $10$.http://comb-opt.azaruniv.ac.ir/article_14542_103d8d93afd44cc6d45e68bdcf8227d1.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901On the rna number of generalized Petersen graphs4514661451810.22049/cco.2023.27973.1408ENDeepakSehrawatDepartment of Mathematics, Indian Institute of Technology Guwahati, Guwahati, IndiaBikashBhattacharjyaDepartment of Mathematics, Indian Institute of Technology Guwahati, Guwahati, IndiaJournal Article20220822A signed graph $(G,\sigma)$ is called a parity signed graph if there exists a bijective mapping $f \colon V(G) \rightarrow \{1,\ldots,|V(G)|\}$ such that for each edge $uv$ in $G$, $f(u)$ and $f(v)$ have same parity if $\sigma(uv)=+1$, and opposite parity if $\sigma(uv)=-1$. The \emph{rna} number $\sigma^{-}(G)$ of $G$ is the least number of negative edges among all possible parity signed graphs over $G$. Equivalently, $\sigma^{-}(G)$ is the least size of an edge-cut of $G$ that has nearly equal sides.<br /><br />In this paper, we show that for the generalized Petersen graph $P_{n,k}$, $\sigma^{-}(P_{n,k})$ lies between $3$ and $n$. Moreover, we determine the exact value of $\sigma^{-}(P_{n,k})$ for $k\in \{1,2\}$. The \emph{rna} numbers of some famous generalized Petersen graphs, namely, Petersen graph, D\" urer graph, M\" obius-Kantor graph, Dodecahedron, Desargues graph and Nauru graph are also computed. Recently, Acharya, Kureethara and Zaslavsky characterized the structure of those graphs whose \emph{rna} number is $1$. We use this characterization to show that the smallest order of a $(4n+1)$-regular graph having \emph{rna} number $1$ is $8n+6$. We also prove the smallest order of $(4n-1)$-regular graphs having \emph{rna} number $1$ is bounded above by $12n-2$. In particular, we show that the smallest order of a cubic graph having \emph{rna} number $1$ is 10.http://comb-opt.azaruniv.ac.ir/article_14518_8fdf483020c02cbc615f57ea5434589e.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901Optimal Coverage of Borders Using Unmanned Aerial Vehicles4674841452810.22049/cco.2023.27951.1403ENMuhammadEtezadiFaculty of Sciences, Emam Ali University, Tehran, IranSiamakAshrafiDepartment of Mathematics, Maragheh Branch, Islamic Azad University Of Maragheh, IranMostafaGhasemiFaculty of Sciences, Imam Ali University, Tehran, IranJournal Article20220803Unmanned Aerial Vehicles (UAVs) play a very important role in military and civilian activities. In this paper, the aim is to cover the borders of Iran using UAVs. For this purpose, two zero-one programming models are presented. In the first model, our goal is to cover the borders of Iran at the minimum total time (the required time to prepare UAVs to start flying and the flight time of the UAVs). In this model, by minimizing the total time of UAVs for covering the borders, the costs appropriate to the flight of UAVs (such as the fuel costs of UAVs) are also reduced. In the second model, which is mostly used in emergencies and when a military attack occurs on the country's borders, the aim is to minimize the maximum required time to counter attacks and cover the entire country's borders. The efficiency of both models is shown by numerical examples.http://comb-opt.azaruniv.ac.ir/article_14528_be44992cdfb1e68caca4514aa43f0fc3.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901New results on Orthogonal Component Graphs of Vector Spaces over $\mathbb{Z}_p$4854951453210.22049/cco.2023.28034.1422ENVrinda MaryMathewDepartment of Mathematics, CHRIST (Deemed to be University), Bangalore-560029, Karnataka,
India0000-0002-3310-6480SudevNaduvathDepartment of Mathematics, CHRIST (Deemed to be University), Bangalore-560029, Karnataka,
India0000-0001-9692-4053Thadathil JosephVargheseDepartment of Mathematics, CHRIST (Deemed to be University), Bangalore-560029, Karnataka,
IndiaJournal Article20221008A new concept known as the orthogonal component graph associated with a finite-dimensional vector space over a finite field has been recently added as another class of algebraic graphs. In these graphs, the vertices will be all the possible non-zero linear combinations of orthogonal basis vectors. Any two vertices will be adjacent if the corresponding vectors are orthogonal. In this paper, we discuss the various colorings and structural properties of orthogonal component graphs.http://comb-opt.azaruniv.ac.ir/article_14532_7d670efed4ef785fa079c4040f07fdcd.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901On the anti-forcing number of graph powers4975071454910.22049/cco.2023.27874.1378ENNedaSoltaniDepartment of Mathematical Sciences, Yazd University, 89195-741, Yazd, IranSaeidAlikhaniDepartment of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran0000-0002-1801-203XJournal Article20220609Let $G=(V,E)$ be a simple connected graph. A perfect matching (or Kekul\'e structure in chemical literature) of $G$ is a set of disjoint edges which covers all vertices of $G$. The anti-forcing number of $G$ is the smallest number of edges such that the remaining graph obtained by deleting these edges has a unique perfect matching and is denoted by $af(G)$. For every $m\in\mathbb{N}$, the $m$th power of $G$, denoted by $G^m$, is a graph with the same vertex set as $G$ such that two vertices are adjacent in $G^m$ if and only if their distance is at most $m$ in $G$. In this paper, we study the anti-forcing number of the powers of some graphs.http://comb-opt.azaruniv.ac.ir/article_14549_8063c1509ea34ba75de39f928295198a.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901On the vertex irregular reflexive labeling of generalized friendship graph and corona product of graphs5095261454510.22049/cco.2023.28046.1426ENKooi-KuanYoongSpecial Interest Group on Modelling and Data Analytics (SIGMDA), Faculty of Ocean
Engineering Technology and Informatics, Universiti Malaysia Terengganu, Terengganu, MalaysiaRoslanHasniSpecial Interest Group on Modelling and Data Analytics (SIGMDA), Faculty of Ocean
Engineering Technology and Informatics, Universiti Malaysia Terengganu, Terengganu, MalaysiaGee-ChoonLauUniversiti Teknologi MARA,
Faculty of Computer
and Mathematical Sciences,
85100 Segamat,
Johor, Malaysia0000-0002-9777-6571AliAhmadCollege of Computer Sciences and Information Technology, Jazan University, Jazan, Saudi ArabiaJournal Article20221017For a graph $G$, we define a total $k$-labeling $\varphi$ as a combination of an edge labeling $\varphi_e:E(G)\rightarrow \{1,\,2,\,\ldots,\,k_e\}$ and a vertex labeling $\varphi_v:V(G)\rightarrow \{0,\,2,\,\ldots,\,2k_v\}$, where $k=\,\mbox{max}\, \{k_e,2k_v\}$. The total $k$-labeling $\varphi$ is called a vertex irregular reflexive $k$-labeling of $G$ if any pair of vertices $u$, $u'$ have distinct vertex weights $wt_{\varphi}(u)\neq wt_{\varphi}(u')$, where $wt_{\varphi}(u)=\varphi(u)+\sum_{uu'\in E(G)} \varphi(uu')$ for any vertex $u\in V(G)$. The smallest value of $k$ for which such a labeling exists is called the reflexive vertex strength of $G$, denoted by $rvs{(G)}$. In this paper, we present a new lower bound for the reflexive vertex strength of any graph. We investigate the exact values of the reflexive vertex strength of generalized friendship graphs, corona product of two paths, and corona product of a cycle with isolated vertices by referring to the lower bound. This study discovers some interesting open problems that are worth further exploration.http://comb-opt.azaruniv.ac.ir/article_14545_827f4576ec34ec69917d00d963659911.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212893202409011-Edge contraction: Total vertex stress and confluence number5275381453510.22049/cco.2023.27338.1238ENShinyJosephMathematic Research Center, Mary Matha Arts and Science College, Mananthavady, Kerala,
IndiaJohanKokIndependant Mathematics Researcher, City of Tshwane, South Africa & Visiting Faculty at
CHRIST (Deemed to be a University), Bangalore, India0000-0003-0106-1676Journal Article20210719This paper introduces certain relations between $1$-edge contraction and the total vertex stress and the confluence number of a graph. A main result states that if a graph $G$ with $\zeta(G)=k\geq 2$ has an edge $v_iv_j$ and a $\zeta$-set $\mathcal{C}_G$ such that $v_i,v_j\in \mathcal{C}_G$ then, $\zeta(G/v_iv_j) = k-1$. In general, either $\mathcal{S}(G/e_i) \leq \mathcal{S}(G/e_j)$ or $\mathcal{S}(G/e_j) \leq \mathcal{S}(G/e_i)$ is true. This observation leads to an investigation into the question: for which edge(s) $e_i$ will $\mathcal{S}(G/e_i) = \max\{\mathcal{S}(G/e_j):e_j \in E(G)\}$ and for which edge(s) will $\mathcal{S}(G/e_j) = \min\{\mathcal{S}(G/e_\ell):e_\ell \in E(G)\}$?http://comb-opt.azaruniv.ac.ir/article_14535_7872a0fe9b978460e43157600b4820c7.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901Some new families of generalized $k$-Leonardo and Gaussian Leonardo Numbers5395531454410.22049/cco.2023.28236.1485ENKalikaPrasadDepartment of Mathematics, Central University of Jharkhand, India, 8352050000-0002-3653-5854RitanjaliMohantyDepartment of Mathematics, Central University of Jharkhand, India, 8352050000-0002-5885-5613MuneshKumariDepartment of Mathematics, Central University of Jharkhand, India, 8352050000-0002-6541-0284HrishikeshMahatoDepartment of Mathematics, Central University of Jharkhand, India, 8352050000-0002-3769-0653Journal Article20230109In this paper, we introduce a new family of the generalized $k$-Leonardo numbers and study their properties. We investigate the Gaussian Leonardo numbers and associated new families of these Gaussian forms. We obtain combinatorial identities like Binet formula, Cassini's identity, partial sum, etc. in the closed form. Moreover, we give various generating and exponential generating functions.http://comb-opt.azaruniv.ac.ir/article_14544_6844cc9ba641d31cafe5358297bc0096.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901Vector valued switching in signed graphs5555651457010.22049/cco.2023.28591.1624ENShahul KHameedDepartment of Mathematics, K M M Government Women’s College, Kannur - 670004, Kerala, IndiaAlbinMathewDepartment of Mathematics, Central University of Kerala, Kasaragod - 671316, Kerala, India0000-0002-2643-3416K AGerminaDepartment of Mathematics, Central University of Kerala, Kasaragod - 671316, Kerala, India0000-0002-2643-3416ThomasZaslavskyDepartment of Mathematics and Statistics, Binghamton University (SUNY), Binghamton, NY
13902-6000, USAJournal Article20230420A signed graph is a graph with edges marked positive and negative; it is unbalanced if some cycle has negative sign product. We introduce the concept of vector valued switching function in signed graphs, which extends the concept of switching to higher dimensions. Using this concept, we define balancing dimension and strong balancing dimension for a signed graph, which can be used for a new classification of degree of imbalance of unbalanced signed graphs. We provide bounds for the balancing and strong balancing dimensions, and calculate these dimensions for some classes of signed graphs.http://comb-opt.azaruniv.ac.ir/article_14570_a32562d8b382a20dbf15525d6d96d990.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901A study on structure of codes over $\mathbb Z_4+u\mathbb Z_4+v\mathbb Z_4 $5675781454810.22049/cco.2023.28011.1503ENGowdhamanKarthickDepartment of Mathematics, Presidency University, Bangalore, Karnataka, IndiaJournal Article20220919We study $(1+2u+2v)$-constacyclic code over a semi-local ring $S=\mathbb Z_4+u\mathbb Z_4+v\mathbb Z_4$ with the condition $u^2=3u,v^2=3v$, and $uv=vu=0$, we show that $(1+2u+2v)$-constacyclic code over $S$ is equivalent to quasi-cyclic code over $\mathbb{Z}_4$ by using two new Gray maps from $S$ to $\mathbb{Z}_4.$ Also, for odd length $n$ we have defined a generating set for constacyclic codes over $S.$ Finally, we obtained some examples which are new to the data base [Database of $\mathbb{Z}_4$ codes [online]}, http://$\mathbb{Z}_4$ Codes.info(Accessed March 2, 2020)].http://comb-opt.azaruniv.ac.ir/article_14548_e6fe5c8749c957f757c7ff47ae8f2470.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901The higher-order Sombor index5795941462310.22049/cco.2023.28658.1654ENMeilingYouCollege of Mathematics and Statistics, Hunan Normal University
Changsha, Hunan 410081, P. R. ChinaHanyuanDengCollege of Mathematics and Statistics, Hunan Normal University
Changsha, Hunan 410081, P. R. ChinaJournal Article20230517Based on the geometric background of Sombor index and motivating by the higher order connectivity index and the Sombor index, we introduce the pathcoordinate of a path in a graph and a degree-point in a higher dimensional coordinate system, and define the higher order Sombor index of a graph. We first consider mathematical properties of the higher order Sombor index, show that the higher order connectivity index of a starlike tree is completely determined by its branches and that starlike trees with a given maximum degree which have the same higher order Sombor indices are isomorphic. Then, we determine the extremal values of the second order Sombor index for all trees with n vertices and characterize the corresponding extremal trees. Finally, the chemical importance of the second order Sombor index is investigated and it is shown that the new index is useful in predicting physicochemical properties with high accuracy compared to some well-established.http://comb-opt.azaruniv.ac.ir/article_14623_f60f8a2ae984bcb21f7626feb8c776a2.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289320240901On the Roman Domination Polynomials5956051455810.22049/cco.2023.28145.1456ENSeyed HoseinMirhoseiniDepartment of Mathematics, Shahed University, Tehran, IranNaderJafari RadDepartment of Mathematics, Shahed University, Tehran, IranJournal Article20221207A Roman dominating function (RDF) on a graph $G$ is a function $ f:V(G)\to \{0,1,2\}$ satisfying the condition that every vertex $u$ with $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) = 2$. The weight of an RDF $f$ is the sum of the weights of the vertices under $f$. The Roman domination number, $\gamma_R(G)$ of $G$ is the minimum weight of an RDF in $G$. The Roman domination polynomial of a graph $G$ of order $n$ is the polynomial $RD(G,x)=\sum_{i=\gamma_R(G)}^{2n} d_R(G,i) x^{i}$, where $d_R(G,i)$ is the number of RDFs of $G$ with weight $i$. In this paper we prove properties of Roman domination polynomials and determine $RD(G,x)$ in several classes of graphs $G$ by new approaches. We also present bounds on the number of all Roman domination polynomials in a graph.http://comb-opt.azaruniv.ac.ir/article_14558_89b7c9b66325ade14daa91bf23f6ca9d.pdf