University of IsfahanTransactions on Combinatorics2251-865715220250421Total Roman domination on Kneser graphs69762943310.22108/toc.2025.140647.2148ENAbolfazlBahmaniDepartment of Mathematics, University of Zanjan, Zanjan, Iran0000-0003-1531-8735MojganEmamiDepartment of Mathematics, University of Zanjan, Zanjan, IranJournal Article20240206A Roman dominating function (RDF) on a graph $G$ is a function $f : V (G) \longrightarrow \{0, 1, 2\}$ such that any vertex $v$ with $ f(v) = 0$ is adjacent to at least one vertex $w$ with $f(w) = 2$. In addition, if the subgraph of $G$ induced by the set of all vertices for which $f \ne 0$ has no isolated vertices then $f$ is called a total Roman dominating function (TRDF). If $f$ is an RDF (TRDF) then the least value of $\sum_{u\in V} f(u)$ is called Roman domination number (total Roman domination number) of $G$ and is denoted by $\gamma_{_R}(G)$ ( $\gamma_{_{tR}}(G)$). Let $G=G(n, k, 0)$ be a Kneser graph, where $n,k$ are positive integers. In this paper we present some bounds for $\gamma_{_{tR}}(G(n, k, 0))$ for $k^2 < n < k^2+k$. In particular we show that $\gamma_{_{tR}}(G(k^2+k-1, k, 0))=2(k+2)$ and for $n\geqslant 2k+1$, $\gamma_{_{R}}(G(n, k, 0)) \geq max \{ \gamma_{_{R}}(G(n-1, k -1, 0)), \gamma_{_{R}}(G(n, k -1, 0))\}$.https://toc.ui.ac.ir/article_29433_eda40b217eca81661131de4de3aadfae.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715220250511On minimal trees with respect to hyper-Zagreb indices77902949910.22108/toc.2025.140617.2146ENNasrinDehgardiDepartment of Mathematics and Computer Science, Sirjan University of Technology, Sirjan, IranHamidehAramDepartment of Mathematics, Khoy.C., Islamic Azad University, Khoy, IranMahdiehAzariDepartment of Mathematics, Kaz.C., Islamic Azad University, Kazerun, Iran0000-0002-0919-0598Journal Article20240204Zagreb indices are among the foremost topological indices in mathematical chemistry. These indices are crucial for investigating the total $\pi$-electron energy of alternant hydrocarbons and are utilized to study various aspects of molecular properties, including complexity, chirality, ZE-isomerism, and hetero-systems. In this paper, we focus on two well-known modifications of these indices: the first and second hyper-Zagreb indices. For a finite simple graph $\Gamma$, these indices are expressed as $$HM_1(\Gamma)=\sum_{\vartheta \omega\in E(\Gamma)}(d_{\Gamma}(\vartheta ) +d_{\Gamma}(\omega))^{2} \ \ {\rm and} \ \ HM_2(\Gamma)=\sum_{\vartheta \omega\in E(\Gamma)}(d_{\Gamma}(\vartheta) d_{\Gamma}( \omega))^{2},$$ where $E(\Gamma)$ denotes the edge set of $\Gamma$ and $d_{\Gamma}(\vartheta)$ indicates the degree of the vertex $\vartheta$ in $\Gamma$. In this paper, we introduce graph transformations on trees and connected graphs that minimize the first and second hyper-Zagreb indices. Accordingly, we determine the minimum values of these indices within the class of all trees with a given number of vertices and a specified maximum vertex degree. Additionally, we characterize the corresponding minimal trees. Our results will be extended to all connected graphs with a given order and maximum vertex degree.https://toc.ui.ac.ir/article_29499_57537069f1ae6f51859d5ff09fd07f06.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715220250726Metric dimension and Zagreb indices of essential ideal graph of a finite commutative ring911102953010.22108/toc.2025.141755.2182ENP.JamsheenaPG and Research Department of Mathematics, Farook College, P.O. Farook College, Kozhikode, Kerala, India- 673632A. V.ChithraDepartment of Mathematics, National Institute of Technology Calicut, Kozhikode, 673601, Kerala, IndiaJournal Article20240607Let $R$ be a commutative ring with unity. The essential ideal graph $\mathcal{E}_{R}$ of $R$ is a graph whose set of vertex consists of all nonzero proper ideals of <em>R</em>. Two vertices $\hat{I}$ and $\hat{J}$ are adjacent if and only if $\hat{I}+ \hat{J}$ is an essential ideal. In this paper, we characterize the graph $\mathcal{E}_{R}$ as having a finite metric dimension. Furthermore, we identify that the essential ideal graph and the annihilating ideal graph of the ring $\mathbb{Z}_{n}$ are isomorphic whenever $n$ is a product of distinct primes. In addition, we estimate the metric dimension of the essential ideal graph of the ring $\mathbb{Z}_{n}$. Moreover, we determine the topological indices, namely the first and second Zagreb indices, of $\mathcal{E}_{\mathbb Z_n}$.https://toc.ui.ac.ir/article_29530_4f5eb7a78757bef9c2029880f1824158.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715220250713The Laplacian and distance matrix of a signed tree1111242955710.22108/toc.2025.137241.2061ENHongZixuanMOE-LCSM, CHP-LCOCS, School of Mathematics and Statistics, Hunan Normal University Changsah, ChinaHouYaopingMOE-LCSM, CHP-LCOCS, School of Mathematics and Statistics, Hunan Normal University Changsah, ChinaXiongZhuanMOE-LCSM, CHP-LCOCS, School of Mathematics and Statistics, Hunan Normal University Changsah, ChinaJournal Article20230402Let $N$ and $\widetilde{D}$ be net Laplacian and net distance matrices of a signed tree, respectively. The inverse (resp. group inverse) of $\widetilde{D}$ is obtained if it is nonsingular (resp. singular), which extend the inverse formula obtained by Graham and Lov\'{a}sz for distance matrix of a unsigned tree. The interlacing inequality connecting the eigenvalues of $\widetilde{D}$ and $N$ of a signed tree is also obtained.https://toc.ui.ac.ir/article_29557_ca7e8817fdb5cc2b08d7204894cd19bd.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715220251013The relation between distance Laplacian spectral radius and integer $k$-matching number in graphs1251362955810.22108/toc.2025.143292.2221ENYanhongZhangDepartment of Mathematics and Statistics, Qinghai Normal University, Xining, ChinaLeiZhangDepartment of Mathematics and Statistics, Qinghai Normal University, Xining, China0000-0001-5187-7898HaizhenRenDepartment of Mathematics and Statistics, Qinghai Normal University, Xining, China0000-0001-5609-5924Journal Article20241105Let $G$ be a graph with order $n$. Aouchiche and Hansen first proposed the distance Laplacian matrix of $G$, defined as $\mathcal{L}(G)=diag(Tr)-\mathcal{D}(G)$, where $\mathcal{D}(G)$ is the distance matrix and $diag(Tr)=diag(Tr(v_1), Tr(v_2),\ldots,Tr(v_n))$ is the diagonal matrix of the vertex transmissions of $G$, and the largest eigenvalue of $\mathcal{L}(G)$ is called the distance Laplacian spectral radius of $G$, written as $\rho_{\mathcal{L}}(G)$. By using the equitable quotient matrix of $\mathcal{L}(G)$, Tutte Theorem and Tutte-Berge Formula of integer $k$-matching, we establish the lower bound for the distance Laplacian spectral radius of $G$ among all $n$-vertex graphs with given integer $k$-matching number and characterized the corresponding extremal graph. This generalizes the results of Wang et al. [Lower bounds of distance Laplacian spectral radii of $n$-vertex graphs in terms of matching number, <em>Linear Algebra Appl.</em>, <strong>506</strong> (2016) 579--587.] and Liu et al. [Lower bounds of distance Laplacian spectral radii of $n$-vertex graphs in terms of fractional matching number, <em>J. Oper. Res. Soc. China.</em>, (2023) 1--8.].https://toc.ui.ac.ir/article_29558_3baa38bda30792f662013d4310a8e902.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715220251111Approximation algorithms for the freeze tag problem inside polygons1371452957010.22108/toc.2025.143753.2229ENFatemehRajabi-AlniDepartment of Computer Engineering, Iran University of Science and Technology, Tehran, IranBehrouzMinaei-BidgoliDepartment of Computer Engineering, Iran University of Science and Technology, Tehran, IranAlirezaBagheriComputer Engineering Department, Amirkabir University of Technology (Tehran Polytechnic), Tehran, IranJournal Article20241225The <em>freeze tag problem </em>(FTP) aims to awaken a swarm of robots with one or more initially awake robots as soon as possible. Each awake robot must touch a sleeping robot to wake it up. Once a robot is awakened, it can assist in awakening other sleeping robots. We study this problem inside a polygonal domain and present approximation algorithms for it.https://toc.ui.ac.ir/article_29570_6014e408996b5a3157c75e1941c3e649.pdf