University of IsfahanTransactions on Combinatorics2251-865711220220601Peripheral Hosoya polynomial of composite graphs63762602510.22108/toc.2021.127151.1813ENAnteneh AlemuAliDepartment of Mathematics, Mangalore University, Mangalore-574199, India0000-0002-7010-0483Kishori P.NarayankarDepartment of Mathematics, Mangalore University, Mangalore-574199, IndiaJournal Article20210123Peripheral Hosoya polynomial of a graph $G$ is defined as,<br /> \begin{align*}<br /> &PH(G,\lambda)=\sum_{k\geq 1}d_P(G,k)\lambda^k,\\<br /> \text{where $d_P(G,k)$ is the number} &\text{ of pairs of peripheral vertices at distance $k$ in $G$.}<br /> \end{align*}<br />Peripheral Hosoya polynomial of composite graphs viz., $G_1\times G_2$ the Cartesian product, $G_1+G_2$ the join, $G_1[G_2]$ the composition, $G_1\circ G_2$ the corona and $G_1\{G_2\}$ the cluster of arbitrary connected graphs $G_1$ and $G_2$ are computed and their peripheral Wiener indices are stated as immediate consequences.https://toc.ui.ac.ir/article_26025_3ff14793f03f06efb256958566913365.pdfUniversity of IsfahanTransactions on Combinatorics2251-865711220220601On the reliability of modified bubble-sort graphs77832591310.22108/toc.2021.127002.1807ENMohsenGhasemiDepartment of Mathematics, Urmia University, P. O. Box 57135 Urmia, IranJournal Article20210114The modified bubble-sort graph $MB_n$ $(n \geq 2)$ has been known as a topology structure of interconnection networks. In this paper, we propose simple method for arc-transitivity of $MB_n$ $(n \geq 2)$. Also by using this result we investigate some reliability measures, including super-connectivity, cyclic edge connectivity, etc., in the modified bubble-sort graphs.https://toc.ui.ac.ir/article_25913_cd8ac7dacfc867cdeff04427be754713.pdfUniversity of IsfahanTransactions on Combinatorics2251-865711220220601Optimal maximal graphs85972601510.22108/toc.2021.128956.1860ENChristianBarrientosDepartment of Mathematics, Valencia College, Orlando, FL 32832, U. S. A.0000-0003-2838-8687MagedYoussefDepartment of Mathematics & Statistics, College of Sciences, Imam Mohammad Ibn Saud Islamic University, Riyadh 11623,
Saudi Arabia0000-0002-0365-1891Journal Article20210601An optimal labeling of a graph with $n$ vertices and $m$ edges is an injective assignment of the first $n$ nonnegative integers to the vertices, that induces, for each edge, a weight given by the sum of the labels of its end-vertices with the property that the set of all induced weights consists of the first $m$ positive integers. We explore the connection of this labeling with other well-known functions such as super edge-magic and $\alpha$-labelings. A graph with $n$ vertices is maximal when the number of edges is $2n-3$; all the results included in this work are about maximal graphs. We determine the number of optimally labeled graphs using the adjacency matrix. Several techniques to construct maximal graphs that admit an optimal labeling are introduced as well as a family of outerplanar graphs that can be labeled in this form.https://toc.ui.ac.ir/article_26015_ba32b11bb5551d77c32c9fbb7f9e1672.pdfUniversity of IsfahanTransactions on Combinatorics2251-865711220220601Independent roman $\{3\}$-domination991102606610.22108/toc.2021.127953.1840ENP.ChakradharDepartment of Computer Science and Engineering, SR University, Warangal - 506 371, India0000-0001-6589-8358P.Venkata Subba ReddyDepartment of Computer Science and Engineering, National Institute of Technology, Warangal - 506 004, IndiaJournal Article20210331Let $G$ be a simple, undirected graph. In this paper, we initiate the study of independent Roman $\{3\}$-domination. A function $g : V(G) \rightarrow \lbrace 0, 1, 2, 3 \rbrace$ having the property that $\sum_{v \in N_G(u)}^{} g(v) \geq 3$, if $g(u) = 0$, and $\sum_{v \in N_G(u)}^{} g(v) \geq 2$, if $g(u) = 1$ for any vertex $u \in V(G)$, where $N_G(u)$ is the set of vertices adjacent to $u$ in $G$, and no two vertices assigned positive values are adjacent is called an \textit{ independent Roman $\{3\}$-dominating function} (IR3DF) of $G$. The weight of an IR3DF $g$ is the sum $g(V) = \sum_{v \in V}g(v)$. Given a graph $G$ and a positive integer $k$, the independent Roman $\{3\}$-domination problem (IR3DP) is to check whether $G$ has an IR3DF of weight at most $k$. We investigate the complexity of IR3DP in bipartite and chordal graphs. The minimum independent Roman $\lbrace 3 \rbrace$-domination problem (MIR3DP) is to find an IR3DF of minimum weight in the input graph. We show that MIR3DP is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs. We also show that the domination problem and IR3DP are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MIR3DP.https://toc.ui.ac.ir/article_26066_8685d9cd7d13606daa8d949bab0fa40a.pdfUniversity of IsfahanTransactions on Combinatorics2251-865711220220601Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of finite rings1111222605310.22108/toc.2021.126721.1802ENDenpongPongpipatDepartment of Mathematics, Faculty of Science, Khon Kaen UniversityNuttawootNupoDepartment of Mathematics, Faculty of Science, Khon Kaen UniversityJournal Article20201230The unitary Cayley graph $\Gamma_n$ of a finite ring $\mathbb{Z}_n$ is the graph with vertex set $\mathbb{Z}_n$ and two vertices $x$ and $y$ are adjacent if and only if $x-y$ is a unit in $\mathbb{Z}_n$. A family $\mathcal{F}$ of mutually edge disjoint trees in $\Gamma_n$ is called a tree cover of $\Gamma_n$ if for each edge $e\in E(\Gamma_n)$, there exists a tree $T\in\mathcal{F}$ in which $e\in E(T)$. The minimum cardinality among tree covers of $\Gamma_n$ is called a tree covering number and denoted by $\tau(\Gamma_n)$. In this paper, we prove that, for a positive integer $ n\geq 3 $, the tree covering number of $ \Gamma_n $ is $ \displaystyle\frac{\varphi(n)}{2}+1 $ and the tree covering number of $ \overline{\Gamma}_n $ is at most $ n-p $ where $ p $ is the least prime divisor of $n$. Furthermore, we introduce the Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of rings $\mathbb{Z}_n$.https://toc.ui.ac.ir/article_26053_1faba403cd1999945cf2ce36fbe484ef.pdf