University of IsfahanTransactions on Combinatorics2251-865715420251111Proof of a conjecture for the identifying codenumber of the subdivision of graphs2312342998310.22108/toc.2025.143773.2228ENKamranMirashehDepartment of Pure Mathematics Faculty of Mathematical Sciences, University of Guilan, P. O. Box 41335-19141, Rasht,
IranAhmadAbbasiDepartment of Pure Mathematics Faculty of Mathematical Sciences, University of Guilan, P. O. Box 41335-19141, Rasht,
IranEbrahimVatandoostDepartment of Basic Science, Imam Khomeini International University, P. O. Box 34148-96818, Qazvin, IranJournal Article20241225In this paper, it is proved that the identifying code number of the subdivision graph of $G$ is $n$ where $ |V(G)|=n. $<br />This result proves the conjecture posed in [S. Ahmadi, E. Vatandoost and A. Behtoie, Domination number and identifying code number of the subdivision graphs, <em>J. Algebr. Syst.</em>, <strong>13</strong> no. 2 (2025) pp. 1--11].https://toc.ui.ac.ir/article_29983_c2da4fc59466df6cd08574ffad74d6a7.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715420251120Circulant matrices of each rank over finite fields2352503004510.22108/toc.2025.138779.2097ENYangjiangWeiSchool of Mathematics and Statistics, Nanning Normal University, and Center for Applied Mathematics of Guangxi at
Nanning Normal University, Nanning, P. R. ChinaYi MingZouDepartment of Mathematical Sciences, University of Wisconsin, Milwaukee, USAJournal Article20230815We consider the enumeration of circulant matrices over a finite field with $q$ elements, and we provide formulas to compute the number of these circulant matrices for each rank. We also consider the computation of the orders of $q$ in multiplicative groups of integers modulo $n$ that are needed in the enumeration, and we give a reduction method to compute these orders. We then use these results to derive explicit formulas for the enumerations of infinite sequences of circulant matrices of some special types.https://toc.ui.ac.ir/article_30045_edde931952a67fae8d88621f2be8dee1.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715420251129Total and paired domination numbers of some wheel-related graphs2512723004610.22108/toc.2025.145488.2286ENPannawatEakawinrujeeThammasat Secondary School, Faculty of Learning Sciences and Education, Thammasat University, Pathum Thani
12120, Thailand0000-0003-1336-1019NantapathTrakultraiprukDepartment of Mathematics and Statistics, Faculty of Science and Technology, Thammasat University, Pathum Thani
12120, ThailandJournal Article20250531Let $G$ be a graph without isolated vertices. A total dominating set of $G$ is a set $D\subseteq V(G)$ such that every vertex of $G$ is adjacent to some vertex in $D$. A paired dominating set of $G$ is a total dominating set whose induced subgraph has a perfect matching. The total (paired) domination number of $G$ is the minimum cardinality of a total (paired) dominating set of $G$. In this paper, we determine the total and the paired domination numbers of some wheel-related graphs. We also give upper bounds on the total and the paired domination numbers of closed helm graphs and web graphs. Moreover, we determine the paired domination numbers of Jahangir graphs and correct some results on the total domination numbers presented by Mtarneh et al. (Malays. J. Math. Sci., 13(S) (2019) 113--121).https://toc.ui.ac.ir/article_30046_8038ac2fbfe3a857a62adfb3f38c4798.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715420251122The Hamiltonian $(s,t)$-path problem in odd-sized $H$-alphabet grid graphs2732943004710.22108/toc.2025.145023.2272ENMarziehGhanbarian-AlavijehDepartment of Computer Science, Shahed University, Tehran, IranFatemehKeshavarz-KohjerdiDepartment of Computer Science, Shahed University, Tehran, IranJournal Article20250424The Hamiltonian path problem is a well-known problem in graph theory with numerous applications in many fields such as routing, robotics, and parallel processing. In general, this problem is NP-complete for general grid graphs; however, efficient solutions can be found for specific classes of graphs. This paper investigates the Hamiltonian $(s,t)$-path problem in odd-sized $H$-alphabet grid graphs, a sub-class of solid grid graphs. We begin by establishing the conditions under which a Hamiltonian path between two given vertices s and t does not exist. For the cases where a Hamiltonian path exists, we propose an efficient linear-time algorithm to find a Hamiltonian path between the two given vertices.<br /> https://toc.ui.ac.ir/article_30047_ce95cd5db4f9d0a5dfb21f00d4e4f99b.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715420251120Failed zero forcing numbers of grassmann graphs2953043005710.22108/toc.2025.145774.2295ENFatemehAfzaliDepartment of Mathematics, Faculty of Science Shahid Rajaee, Teacher Training University, Tehran, IranAmir HosseinGhodratiDepartment of Mathematics, Faculty of Science Shahid Rajaee, Teacher Training University, Tehran, IranHamid RezaMaimaniDepartment of Mathematics, Faculty of Science, Shahid Rajaee Teacher Training University, Tehran, Iran.Journal Article20250629For a graph $G$ with vertices colored either black or white, consider the following rule to change the colors: the color of a vertex which is the only white neighbor of a black vertex, changes from white to black. A proper subset $S$ of the vertex set of $G$ is called a failed zero forcing set if, regardless of how many times this rule is applied to a graph with the initial black vertices $S$, at least one white vertex always remains. The maximum size of such a subset is called the failed zero forcing number of $G$ and is denoted by $F(G)$. In this paper, we look at the failed zero forcing numbers of Grassmann graphs $J_q(n, 2)$ and prove that $F(J_q(n, 2))={n \brack 2}_q - b'_2(q)$, for $n\geq 5$, where $b'_2(q)$ is the maximum number of points in the affine or projective plane of order $q$ such that there is no line that passes through exactly one of these points. Moreover, using maximum arcs in the projective planes, we show that if $q$ is a power of two, then $F(J_q(n, 2))={n \brack 2}_q - (q + 2)$.https://toc.ui.ac.ir/article_30057_3a6bb0a913a680628dae5ffe471c1949.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715420251204Colored points traveling salesman problem3053153010510.22108/toc.2025.140814.2153ENSaeedAsaeediDepartment of Computer Science, Faculty of Mathematical Sciences, University of Kashan, P.O.Box 87317-53153, Kashan,
I. R. IranJournal Article20240224The Colored Points Traveling Salesman Problem (Colored Points TSP) is introduced in this work as a novel variation of the traditional Euclidean Traveling Salesman Problem (TSP) in which the set of points is partitioned into multiple classes, each of which is represented by a distinct color (or label). The goal is to find a minimum cost cycle that visits all the colors so that each color appears only once. This problem finds diverse applications across various fields, including transportation, goods distribution, postal services, inspection, insurance, and banking. By reducing the traditional TSP to it, we can demonstrate that Colored Points TSP is NP-hard. Here, we offer a $\frac{2\pi r}{3}$-approximation algorithm for this problem when the points are placed on a unit grid, where $r$ denotes the radius of the points' smallest color-spanning circle. The algorithm has been implemented, executed on random datasets, and compared against the brute force method.https://toc.ui.ac.ir/article_30105_70cf2527e15f3dc5695d7b0d796568a1.pdfUniversity of IsfahanTransactions on Combinatorics2251-865715420261201Antimagic labelings on graphs with ascending subgraph decomposition3173332981310.22108/toc.2025.143242.2219ENSigitPancahayaniDoctoral Program in Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung,
IndonesiaRinoviaSimanjuntakCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung,
Bandung, Indonesia0000-0002-3224-2376SaladinUttunggadewaCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung,
Bandung, IndonesiaJournal Article20241031Let $t$ and $q$ be positive integers that satisfy $\binom{t+1}{2} \leq q< \binom{t+2}{2}$ and $G$ be a simple and finite graph of size $q$. $G$ is said to be an ascending subgraph decomposition (ASD) graph if $G$ can be decomposed into $t$ subgraphs $H_1, H_2,\ldots,H_t$ without isolated vertices such that $H_i$ is isomorphic to a proper subgraph of $H_{i+1}$, for $1 \leq i \leq t-1$.<br /> <br />In this paper, we introduce a new type of antimagic labeling based on the notion of ASD. Let $G$ be an ASD graph and $f:V(G)\cup E(G) \rightarrow \{1,2,\ldots,\lvert V(G)\rvert+\lvert E(G)\rvert\}$ a bijection. The weight of a subgraph $H_i$ $(1\leq i\leq t)$ is $w(H_i)=\sum_{v\in V(H_i)}f(v)+\sum_{e\in E(H_i)}f(e)$. If the weights of all $H_i$s $(1\leq i\leq t)$ form an arithmetic progression with the smallest weight $a$ and common difference $d$, then $f$ is called an $(a,d)$-ASD antimagic labeling and $G$ is an $(a,d)$-ASD antimagic graph.<br /> <br />We provide an upper bound for $d$ in an $(a,d)$-ASD antimagic graph. We define and utilize the $(t,\delta)$-ascending antibalanced multisets to label some product graphs, including disjoint union, vertex amalgamation, edge amalgamation, subgraph amalgamation, and extended chain of graphs.https://toc.ui.ac.ir/article_29813_0ecf599d969a776a35604a8322cfc501.pdf