Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2290 https://internationalpubls.com Complexity of Types of Trapezoidal Graphs Iqbal M. Batiha1,2,*, Belal Batiha3, Iqbal H. Jebril1, Hamzah O. Al-Khawaldeh4, Basma Mohamed5 1Department of Mathematics, Al Zaytoonah University of Jordan, Amman 11733, Jordan 2Nonlinear Dynamics Research Center (NDRC), Ajman University, Ajman 346, United Arab Emirates 3Department of Mathematics, Faculty of Science and Information Technology, Jadara University, Irbid, Jordan 4Department of Mathematics, Al Al-Bayt University, Mafraq, Jordan 5Giza Higher Institute for Managerial Sciences, Tomah, Eygpt Article History: Received: 12-01-2025 Revised: 15-02-2025 Accepted: 01-03-2025 Abstract: The number of spanning trees in graphs (networks) is a fundamental invariant that plays a crucial role in measuring the reliability and connectivity of a network. It is particularly significant in various applications, including network design, circuit analysis, and structural stability assessments. In this paper, we derive explicit and simplified formulas for computing the complexity of specific classes of graphs, particularly trapezoidal graphs, using advanced techniques from linear algebra and matrix analysis. By leveraging Kirchhoff's matrix tree theorem and eigenvalue-based formulations, we establish efficient methods for determining the number of spanning trees. Additionally, we explore computational approaches such as Chio’s condensation and Dodgson’s method to enhance the accuracy and efficiency of determinant calculations related to graph Laplacians. The results obtained provide a deeper insight into the structural properties of trapezoidal graphs and their spanning tree enumeration, offering potential applications in combinatorial optimization, network topology analysis, and applied mathematics. Keywords: Edge contraction, spanning trees, trapezoidal graphs. 1. Introduction We provide some fundamental definitions and lemmas in this work. We work with undirected graphs G = (V, E) that are simple and finite, where the vertex set is V and the edge set is E. A tree that has the same set of vertices as graph G is said to be a spanning tree in graph G. The number of spanning trees in G, commonly known as the graph's complexity and represented by τ(G), is a quantity that has been extensively explored and found in many different applications. The three most common application domains are measuring the number of Eulerian circuits in a graph [1], identifying specific chemical isomers [2], and network dependability [3-5]. For G = (V, E), the number of spanning trees may be found using the standard result of Kirchhoff [6]. The Kirchhoff matrix H is defined as the n × n characteristic matrix H = D −A, where D is the diagonal matrix of the degrees of G and A is its adjacency matrix. H = [𝑎𝑖𝑗] is defined as follows: When i = j, then (i) 𝑎𝑖𝑗= −1, 𝑣𝑖 and 𝑣𝑗 are nearby, and (ii) 𝑎𝑖𝑗 equals the degree of vertex 𝑎𝑖𝑗; otherwise, (iii) 𝑎𝑖𝑗= 0. Every co-factor of H is equivalent to τ(G). There are several ways to compute τ(G). let 𝜇1 ≥ 𝜇2 ≥. . . ≥ 𝜇𝑝 indicate the eigenvalues of H matrix of a p point graph. Then, it can be demonstrated with ease that 𝜇𝑝 = 0. Then it is easily shown that 0. Furthermore, Kelmans and Chelnokov [7] shown that, 𝜏(𝐺) = 1/𝑝∏ 𝜇𝑘 𝑝−1 𝑘=1 . The formula for the number of spanning trees in a d- Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2291 https://internationalpubls.com regular graph G can be expressed as 𝜏(𝐺) = 1/𝑝∏ (𝑑 − 𝜇𝑘 𝑝−1 𝑘=1 ) where 𝜆0 = 𝑑, 𝜆1, 𝜆2, . . . , 𝜆𝑝−1 are the eigenvalues of the corresponding adjacency matrix of the graph. On the other hand, for a small number of unique graph families, there are straightforward formulas that greatly simplify the computation and determination of the number of related spanning trees, particularly for high numbers. One of the first such result is due to Cayley [8] who showed that complete graph on n vertices, 𝐾𝑛 has 𝑛𝑛−2 spanning trees that he showed 𝜏(𝐾𝑛) = 𝑛 𝑛−2, 𝑛 ≥ 2 and 𝜏(𝐾𝑝,𝑞) = 𝑝 𝑞−1𝑞𝑝−1𝑝, 𝑞 ≥ 1 where 𝐾𝑝,𝑞 is the complete bipartite graph with bipartite sets containing p and q vertices, respectively. It is well known, as in e.g., [9,10]. For Sierpiński graphs and data center networks, Zhang et al. [11] computed the spanning tree entropy. Linear-time techniques for calculating the quantity and mean size of connected sets in a planar 3-tree were introduced by Luo et al. [12]. Sotirov et al. [13] constructed a series of QMSTP relaxations of increasing complexity and quality by utilizing an expanded formulation for the minimal spanning tree problem. Mohamed et al. [14] obtained basic formulae for the number of spanning trees of specific types of cyclic snake graphs by applying matrix analysis and linear algebra techniques. Daoud [15] computed the number of spanning trees of the Cartesian and Composition products of certain families’ graphs. In this paper, we use matrix analysis and linear algebra techniques to obtain simple expressions of the complexity of specific graphs, including trapezoidal graph types. 1.1 Chio’s Condensation Is technique to calculate an n × n determinant using (n − 1) × (n − 1) determinants; see to [16], [17]: 𝐴 = | 𝑎11 𝑎12 ⋯ 𝑎1𝑛 𝑎21 𝑎22 ⋯ 𝑎2𝑛 ⋮ ⋮ ⋱ ⋮ 𝑎𝑛1 𝑎𝑛2 ⋯ 𝑎𝑛𝑛 | = | | | 𝑎11 𝑎12 𝑎21 𝑎22 | | 𝑎11 𝑎13 𝑎21 𝑎23 | ⋯ | 𝑎11 𝑎1𝑛 𝑎21 𝑎2𝑛 | | 𝑎11 𝑎12 𝑎31 𝑎32 | | 𝑎11 𝑎13 𝑎31 𝑎33 | ⋯ | 𝑎11 𝑎1𝑛 𝑎31 𝑎3𝑛 | ⋮ ⋮ ⋱ ⋮ | 𝑎11 𝑎12 𝑎𝑛1 𝑎𝑛2 | | 𝑎11 𝑎13 𝑎𝑛1 𝑎𝑛3 | ⋯ | 𝑎11 𝑎1𝑛 𝑎𝑛1 𝑎𝑛𝑛 | | | (1) 1.2 Dodgson’s Condensation Method By defining determinants of size (n − 1) × (n − 1) in terms of those of size (n − 2)×(n − 2), and so on, Dodgson's condensation method computes determinants of size n × n (see [18]). This method is based on Dodgson and Chio’s method, but the difference between them is that this new method is resolved by calculating 4 unique determinants of (n − 1) × (n − 1) Order, (which can be derived from determinants of n × n order, if we remove first row and first column or first row and last column or last row and first column or last row and last column, elements that belongs to only one of unique determinants we should call them unique elements), and one determinant of (n − 2) × (n − 2) order which is formed from n × n order determinant with elements 𝑎𝑖𝑗 with i, j = 1, n, on condition that the determinant of (n − 2) × (n − 2) = 0. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2292 https://internationalpubls.com Lemma 1.2.1 A basic graph G with n vertices has the following Laplacian matrix 𝐿𝑛𝑥𝑛 definition 𝑳 = 𝑫− 𝑨: where D is the graph's degree matrix and A is its adjacency matrix. Directed graphs can employ either the in degree or the out degree, depending on the application. The elements of 𝐿𝑖,𝑗 are given by: 𝐿𝑖,𝑗 = { deg( 𝑣𝑖) 𝑖𝑓 𝑖 = 𝑗 −1 𝑖𝑓 𝑖 ≠ 𝑗 𝑎𝑛𝑑 𝑣𝑖 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑖𝑠 𝑎𝑑𝑗𝑎𝑐𝑒𝑛𝑡 𝑡𝑜 𝑣𝑗 , where deg(𝑣𝑖) is degree of the vertex i. Definition 1.2.2 The intersection family of trapezoids, or trapezoid graphs, are those in which each trapezoid has two opposite sides that are parallel to each other. These graphs, which are precisely between co-comparability graphs (where the complement has a transitive orientation) and permutation graphs (where the trapezoids are lines), have drawn a lot of attention [19]. For further studies about some other applications that could employ some other graphs, the reader may refer to the references [20,21,22,23,24,25,26,27,28,29]. 2. Main Results Theorem 2.1. Let 𝑇(𝑃𝑛 𝑛−2) be a trapezoidal graph of 2n − 2 vertices with triangulations 𝜏(𝑇(𝑃𝑛 𝑛−2)) = 𝜏 ( ) such that 𝜏(𝑇(𝑃𝑛 𝑛−2)) = 100 × 8𝑘 , 𝑘 ≥ 1, where 𝑘 is the number of blocks. Proof. By applying Eq. (1), we can perform the proof by the following steps: - By mathematical induction, we prove the statement is true at m = 1, 𝜏(𝐺) is a 2×2-matrix with both rows the same: 𝜏(𝐺) = 1 520 [ 480 400 400 1200 ] = 800. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2293 https://internationalpubls.com - We prove that the statement is true at 𝑚 = 𝑘 + 1, that is straightforward induction using properties of determinants and Dodgson and Chio method and applying Eq. (2), we have: 𝜏(𝐺) = | | | 2 −1 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 −1 4 −1 ⋱ ⋯ ⋮ −1 ⋱ ⋱ ⋯ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋮ −1 0 ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 −1 0 0 ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋱ −1 −1 −1 −1 −1 ⋱ ⋱ 0 ⋱ 0 ⋱ ⋱ 0 0 ⋱ 0 ⋯ ⋱ ⋱ −1 ⋱ −1 ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋯ ⋯ 0 −1 −1 0 ⋯ 0 −1 4 | | | (2𝑘+5)×(2𝑘+5) Consequently, we can have 𝜏(𝐺) = 1 (65 + (𝑘 − 1) × 15) × 8𝑘 | 60 × 8𝑘 50 × 8𝑘 50 × 8𝑘 (150 + (𝑘 − 1) × 25) × 8𝑘 | = 100 × 8𝑘 , where k is the number of blocks. So, we have 𝜏(𝐺) = 1 | | | 4 −1 0 ⋯ 0 −1 −1 0 ⋯ −1 ⋱ ⋱ ⋱ ⋱ −1 −1 ⋮ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 ⋱ 0 ⋱ ⋱ −1 −1 −1 ⋱ ⋱ 0 ⋱ −1 ⋱ ⋱ −1 0 ⋱ ⋱ ⋱ −1 ⋱ ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋯ ⋱ 0 −1 ⋱ 0 −1 4 | | | (2𝑘+3)∗(2𝑘+3) | | | | | | | | | 2 −1 0 ⋯ ⋯ 0 −1 0 ⋯ 0 −1 4 ⋱ ⋱ ⋱ ⋯ −1 ⋱ ⋱ ⋯ 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ 0 ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋯ ⋱ ⋱ −1 ⋱ 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 ⋱ −1 ⋱ 0 0 ⋱ 0 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋯ 0 −1 0 −1 ⋱ ⋯ −1 4 | | | (2𝑘+4)∗(2𝑘+4) | | | −1 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 4 ⋱ ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋯ ⋮ −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 ⋱ 0 ⋱ ⋱ ⋱ −1 −1 −1 ⋱ ⋱ 0 ⋱ −1 ⋱ ⋱ 0 −1 0 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋯ −1 ⋱ −1 0 ⋯ −1 4 −1 | | | (2𝑘+4)∗(2𝑘+4) | | | −1 4 −1 0 ⋯ 0 −1 −1 0 ⋯ 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 0 0 0 ⋱ ⋱ −1 ⋱ 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 ⋱ −1 ⋱ 0 0 ⋱ 0 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ 0 −1 ⋱ ⋱ ⋱ 4 0 ⋯ ⋯ 0 −1 −1 0 ⋱ ⋱ −1 | | | (2𝑘+4)∗(2𝑘+4) | | | 4 −1 0 ⋯ 0 −1 −1 0 ⋯ 0 −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 ⋱ 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 ⋱ −1 ⋱ ⋱ 0 −1 0 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋯ 0 −1 −1 0 ⋯ 0 −1 4 | | | (2𝑘+4)∗(2𝑘+4) | | | | | | in which 1 𝑆 = 1 | | | 4 −1 0 ⋯ 0 −1 −1 0 ⋯ −1 ⋱ ⋱ ⋱ ⋱ −1 −1 ⋮ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 ⋱ 0 ⋱ ⋱ −1 −1 −1 ⋱ ⋱ 0 ⋱ −1 ⋱ ⋱ −1 0 ⋱ ⋱ ⋱ −1 ⋱ ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋯ ⋱ 0 −1 ⋱ 0 −1 4 | | | (𝑛−3)×(𝑛−3) Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2294 https://internationalpubls.com 𝐴 = | | | 2 −1 0 ⋯ ⋯ 0 −1 0 ⋯ 0 −1 4 ⋱ ⋱ ⋱ ⋯ −1 ⋱ ⋱ ⋯ 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ 0 ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋯ ⋱ ⋱ −1 ⋱ 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 ⋱ −1 ⋱ 0 0 ⋱ 0 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋯ 0 −1 0 −1 ⋱ ⋯ −1 4 | | | (𝑛−2)×(𝑛−2) , 𝐵 = | | | −1 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 4 ⋱ ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋯ ⋮ −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 ⋱ 0 ⋱ ⋱ ⋱ −1 −1 −1 ⋱ ⋱ 0 ⋱ −1 ⋱ ⋱ 0 −1 0 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋯ −1 ⋱ −1 0 ⋯ −1 4 −1 | | | (𝑛−2)×(𝑛−2) 𝐵𝑇 = | | | −1 4 −1 0 ⋯ 0 −1 −1 0 ⋯ 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 0 0 0 ⋱ ⋱ −1 ⋱ 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 ⋱ −1 ⋱ 0 0 ⋱ 0 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ 0 −1 ⋱ ⋱ ⋱ 4 0 ⋯ ⋯ 0 −1 −1 0 ⋱ ⋱ −1 | | | (𝑛−2)×(𝑛−2) and 𝐶 = | | | 4 −1 0 ⋯ 0 −1 −1 0 ⋯ 0 −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 ⋱ 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 ⋱ −1 ⋱ ⋱ 0 −1 0 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋯ 0 −1 −1 0 ⋯ 0 −1 4 | | | (𝑛−2)×(𝑛−2) Theorem 2.2. Let 𝑇(𝑃𝑛 𝑛−2) be a trapezoidal graph of (2𝑛 − 2) vertices with triangulations Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2295 https://internationalpubls.com 𝜏(𝑇(𝑃𝑛 𝑛−2)) = 𝜏 ( ) such that 𝜏(𝑇(𝑃𝑛 𝑛−2)) = 100 × 12𝑘−1, 𝑘 ≥ 1 where 𝑘 is the number of blocks. Proof. By using Eq. (1), we can apply the proof by performing the following steps: - By mathematical induction, we prove this statement at 𝑚 = 1, i.e. 𝜏(𝐺) is a 2×2-matrix with both rows the same: 𝜏(𝐺) = 1 50 [ 60 50 50 125 ] = 100. - We prove the statement at 𝑚 = 𝑘 + 1, that is straightforward induction using properties of determinants and Dodgson and Chio method and applying Eq. (2), we have: 𝜏(𝐺) = | | | 2 −1 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 −1 4 ⋱ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ 5 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 5 −1 0 ⋯ ⋯ 0 −1 −1 0 ⋯ 0 −1 4 | | | (2𝑘+3)×(2𝑘+3) Consequently, we can have 𝜏(𝐺) = 1 (50 + (𝑘 − 1) × 15) × 12𝑘−1 | 60 × 12𝑘−1 50 × 12𝑘−1 50 × 12𝑘−1 (125 + (𝑘 − 1) × 25) × 12𝑘−1 |, or 𝜏(𝐺) = 100 × 12𝑘−1, where k is the number of blocks. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2296 https://internationalpubls.com 𝜏(𝐺) = 1 | | | 4 −1 0 ⋯ 0 −1 −1 0 ⋯ −1 5 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ 0 −1 ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋮ 0 ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ −1 −1 0 ⋯ 0 −1 5 | | | (2𝑘+1)∗(2𝑘+1) | | | | | | | | | 2 −1 0 ⋯ ⋯ 0 −1 0 ⋯ 0 −1 4 ⋱ ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋮ 0 ⋱ 5 ⋱ ⋱ ⋱ −1 ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ −1 0 0 ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋯ 0 −1 −1 −1 0 ⋯ −1 5 | | | (2𝑘+2)∗(2𝑘+2) | | | −1 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 4 ⋱ ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋱ ⋮ −1 5 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ ⋱ 0 −1 ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋯ −1 −1 −1 0 ⋯ −1 5 −1 | | | (2𝑘+2)∗(2𝑘+2) | | | −1 4 −1 0 ⋯ 0 −1 −1 0 ⋯ 0 ⋱ 5 ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ −1 0 ⋯ ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 5 0 ⋯ ⋯ 0 −1 −1 0 ⋯ 0 −1 | | | (2𝑘+2)∗(2𝑘+2) | | | 4 −1 0 ⋯ 0 −1 −1 0 ⋯ 0 −1 5 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ ⋱ 0 −1 ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 5 −1 0 ⋯ 0 −1 −1 0 ⋯ 0 −1 4 | | | (2𝑘+2)∗(2𝑘+2) | | | | | | for which 1 𝑆 = 1 | | | 4 −1 0 ⋯ 0 −1 −1 0 ⋯ −1 5 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ 0 −1 ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋮ 0 ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ −1 −1 0 ⋯ 0 −1 5 | | | (2𝑘+1)×(2𝑘+1) 𝐴 = | | | 2 −1 0 ⋯ ⋯ 0 −1 0 ⋯ 0 −1 4 ⋱ ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋮ 0 ⋱ 5 ⋱ ⋱ ⋱ −1 ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ −1 0 0 ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋯ 0 −1 −1 −1 0 ⋯ −1 5 | | | (2𝑘+2)×(2𝑘+2) 𝐵 = | | | −1 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 4 ⋱ ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋱ ⋮ −1 5 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ ⋱ 0 −1 ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋯ −1 −1 −1 0 ⋯ −1 5 −1 | | | , Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2297 https://internationalpubls.com 𝐵𝑇 = | | | −1 4 −1 0 ⋯ 0 −1 −1 0 ⋯ 0 ⋱ 5 ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ −1 0 ⋯ ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 5 0 ⋯ ⋯ 0 −1 −1 0 ⋯ 0 −1 | | | (2𝑘+2)∗(2𝑘+2) 𝐶 = | | | 4 −1 0 ⋯ 0 −1 −1 0 ⋯ 0 −1 5 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ 5 −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋱ ⋱ −1 4 0 ⋱ ⋱ −1 −1 −1 −1 ⋱ ⋱ 0 4 −1 ⋱ ⋱ 0 −1 ⋱ ⋱ ⋱ ⋱ −1 5 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 5 −1 0 ⋯ 0 −1 −1 0 ⋯ 0 −1 4 | | | (2𝑘+2)∗(2𝑘+2) Theorem 2.3. Let 𝑇(𝑃𝑛 𝑛−2) be a trapezoidal graph of 2n − 2 vertices with triangulations 𝜏(𝑇(𝑃𝑛 𝑛−2)) = 𝜏 ( ) such that 𝜏(𝑇(𝑃𝑛 𝑛−2)) = 9 × 23𝑘+2, k ≥ 1, where k is the number of blocks. Proof. By applying Eq. (1), we can perform the following steps: - By mathematical induction, we prove this statement at m = 1, i.e. 𝜏(𝐺) is a 2×2 matrix with both rows the same: 𝜏(𝑇(𝑃𝑛 𝑛−2)) = 1 216 [ 192 144 144 432 ] = 288. - We try to prove the statement at 𝑚 = 𝑘 + 1; that is straightforward induction using properties of determinants and Dodgson and Chio method and applying Eq. (2), we have: Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2298 https://internationalpubls.com 𝜏(𝑇(𝑃𝑛 𝑛−2)) = | | | 2 −1 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 −1 3 ⋱ ⋱ ⋯ ⋯ ⋱ ⋱ ⋱ ⋯ ⋮ 0 ⋱ 4 ⋱ ⋱ ⋯ −1 ⋱ ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋮ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ ⋱ −1 0 ⋮ ⋮ ⋱ −1 3 0 ⋱ ⋱ −1 0 −1 ⋱ −1 ⋱ ⋱ 0 3 −1 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋱ ⋱ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋯ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 4 −1 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 −1 3 | | | (2𝑘+5)×(2𝑘+5) Consequently, we can have 𝜏(𝑇(𝑃𝑛 𝑛−2)) = 1 (8𝑘 × (27 + 6 (𝑘 − 1))) | 3 × 8𝑘+1 18 × 8𝑘 18 × 8𝑘 8𝑘 × (54 + 9 (𝑘 − 1)) | = 9 × 23𝑘+2, where k is the number of blocks −𝜏(𝐺) = 1 𝑆 | 𝐴 𝐵 𝐵𝑇 𝐶 |. As a result, we get 𝜏(𝐺) = 1 | | | 3 −1 0 ⋯ ⋯ 0 −1 0 ⋯ −1 4 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ −1 3 0 ⋱ ⋱ −1 0 −1 ⋱ ⋱ 0 3 −1 ⋱ 0 −1 ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋯ −1 0 −1 0 0 −1 4 | | | (2𝑘+3)∗(2𝑘+3) | | | | | | | | | 2 −1 0 ⋯ ⋯ 0 −1 0 ⋯ 0 −1 3 ⋱ ⋱ ⋱ 0 ⋱ ⋱ ⋱ ⋮ 0 ⋱ 4 ⋱ ⋱ ⋱ −1 ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ 0 0 0 ⋱ ⋱ −1 3 0 ⋱ ⋱ −1 −1 ⋱ −1 ⋱ ⋱ 0 3 −1 ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋯ 0 −1 0 −1 0 0 −1 4 | | | (2𝑘+4)∗(2𝑘+4) | | | −1 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 3 ⋱ ⋱ ⋯ ⋯ ⋱ ⋱ ⋱ ⋱ ⋮ −1 4 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ −1 3 0 ⋱ ⋱ ⋱ 0 0 −1 ⋱ ⋱ 0 3 −1 ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋯ −1 0 −1 0 0 −1 4 −1 | | | (2𝑘+4)∗(2𝑘+4) | | | −1 3 −1 0 ⋯ ⋯ 0 −1 0 ⋯ 0 ⋱ 4 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ 0 0 0 ⋱ ⋱ −1 3 0 ⋱ ⋱ −1 −1 ⋱ −1 ⋱ ⋱ 0 3 −1 ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 4 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 −1 | | | (2𝑘+4)∗(2𝑘+4) | | | 3 −1 0 ⋯ ⋯ 0 −1 0 ⋯ 0 −1 4 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ −1 3 0 ⋱ ⋱ −1 0 0 −1 ⋱ ⋱ 0 3 −1 ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 4 −1 0 ⋯ 0 −1 0 ⋯ ⋯ 0 −1 3 | | | (2𝑘+4)∗(2𝑘+4) | | | | | | for which 1 𝑆 = 1 | | | 3 −1 0 ⋯ ⋯ 0 −1 0 ⋯ −1 4 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ −1 3 0 ⋱ ⋱ −1 0 −1 ⋱ ⋱ 0 3 −1 ⋱ 0 −1 ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋯ −1 0 −1 0 0 −1 4 | | | (2𝑚+3)×(2𝑚+3) , Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2299 https://internationalpubls.com A= | | | 2 −1 0 ⋯ ⋯ 0 −1 0 ⋯ 0 −1 3 ⋱ ⋱ ⋱ 0 ⋱ ⋱ ⋱ ⋮ 0 ⋱ 4 ⋱ ⋱ ⋱ −1 ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ 0 0 0 ⋱ ⋱ −1 3 0 ⋱ ⋱ −1 −1 ⋱ −1 ⋱ ⋱ 0 3 −1 ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 0 ⋯ 0 −1 0 −1 0 0 −1 4 | | | (2𝑚+4)×(2𝑚+4) , B= | | | −1 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 3 ⋱ ⋱ ⋯ ⋯ ⋱ ⋱ ⋱ ⋱ ⋮ −1 4 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ −1 3 0 ⋱ ⋱ ⋱ 0 0 −1 ⋱ ⋱ 0 3 −1 ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋯ −1 0 −1 0 0 −1 4 −1 | | | (2𝑚+4)∗(2𝑚+4) 𝐵𝑇 = | | | −1 3 −1 0 ⋯ ⋯ 0 −1 0 ⋯ 0 ⋱ 4 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ 0 0 0 ⋱ ⋱ −1 3 0 ⋱ ⋱ −1 −1 ⋱ −1 ⋱ ⋱ 0 3 −1 ⋱ 0 0 ⋱ ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 4 0 ⋯ ⋯ 0 −1 0 ⋯ ⋯ 0 −1 | | | (2𝑚+4)∗(2𝑚+4) , and C= | | | 3 −1 0 ⋯ ⋯ 0 −1 0 ⋯ 0 −1 4 ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ 4 −1 ⋱ ⋱ ⋱ ⋱ −1 ⋮ ⋱ ⋱ −1 3 0 ⋱ ⋱ −1 0 0 −1 ⋱ ⋱ 0 3 −1 ⋱ ⋱ ⋮ −1 ⋱ ⋱ ⋱ ⋱ −1 4 ⋱ ⋱ ⋮ 0 ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 0 ⋮ ⋱ ⋱ ⋱ −1 ⋱ ⋱ ⋱ 4 −1 0 ⋯ 0 −1 0 ⋯ ⋯ 0 −1 3 | | | (2𝑚+4)∗(2𝑚+4) Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2300 https://internationalpubls.com 3. Conclusion An essential invariant and significant indicator of a network's dependability is the number of spanning trees in graphs or networks. In this work, we used matrix analysis and linear algebra to construct elementary formulae for the complexity of several kinds of special graphs, including trapezoidal graph forms. The derived expressions provide a computationally efficient approach to evaluating the structural properties of these graphs. Furthermore, our results contribute to a deeper understanding of network resilience and optimization, which can be beneficial in various applications, such as communication networks, circuit design, and combinatorial optimization. References [1] C.J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, New York, 1980. [2] W. Myrvold, K.H. Cheung, L.B. Page, J.E. Perry, "Uniformly-most reliable networks do not always exist," Networks, vol. 21, pp. 417–419, 1991. [3] L. Peling, F. Boesch, C. Suffel, "On the characterization of graphs with maximum number of spanning trees," Discrete Mathematics, vol. 179, pp. 155–166, 1998. [4] T.J.N. Brown, R.B. Mallion, P. Pollak, A. Roth, "Some methods for counting the spanning trees in labeled molecular graphs, examined in relation to certain fullerenes," Discrete Mathematics, vol. 67, pp. 51–66, 1996. [5] W. Moon, "Enumerating labeled trees," in Graph Theory and Theoretical Physics, F. Harary, Ed. 1967, pp. 261–271. [6] G.G. Kirchhoff, "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird," Annalen der Physik und Chemie, vol. 72, pp. 497–508, 1847. [7] A.K. Kelmans, V.M. Chelnokov, "A certain polynomial of a graph and graphs with an extreme number of trees," Journal of Combinatorial Theory, Series B, vol. 16, pp. 197–214, 1974. [8] G.A. Cayley, "A theorem on trees," Quarterly Journal of Mathematics, vol. 23, pp. 276–378, 1889. [9] L. Clark, "On the enumeration of multipartite spanning trees of the complete graph," Bulletin of the ICA, vol. 38, pp. 50–60, 2003. [10] N.S. Qiao, B. Chen, "The number of spanning trees and chains of graphs," Journal of Applied Mathematics, vol. 9, pp. 10–16, 2007. [11] X. Zhang, G. Yang, C. He, R. Klasing, and Y. Mao, "The number of spanning trees for Sierpiński graphs and data center networks," Information and Computation, vol. 105194, 2024. [12] Z. Luo and K. Xu, "Computing the number and average size of connected sets in planar 3-trees," Graphs and Combinatorics, vol. 40, no. 3, pp. 1-18, 2024. [13] R. Sotirov and Z. Verchére, "The quadratic minimum spanning tree problem: lower bounds via extended formulations," Vietnam Journal of Mathematics, pp. 1-22, 2024. [14] B. Mohamed and M. Amin, "Complexity of some types of cyclic snake graphs," Mathematical Modelling, vol. 9, no. 1, pp. 14-22, 2024. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 9s (2025) 2301 https://internationalpubls.com [15] S. N. Daoud, "Number of spanning trees of Cartesian and composition products of graphs and Chebyshev polynomials," IEEE Access, vol. 7, pp. 71142-71157, 2019. [16] A. Salihu, H. Snopce, A. Luma, and J. Ajdari, "Optimization of Dodgson's condensation method for rectangular determinant calculations," Advanced Mathematical Models & Applications, vol. 7, no. 3, pp. 264-274, 2022. [17] R. B. Armistead, "MPI-based parallel solution of sparse linear systems using Chio's condensation algorithm and test data from power flow analysis," 2010. [18] A. Salihu, H. Snopçe, J. Ajdari, and A. Luma, "Generalization of Dodgson’s condensation method for calculating determinant of rectangular matrices," in 2022 International Conference on Electrical, Computer and Energy Technologies (ICECET), 2022, pp. 1-6. [19] G. B. Mertzios and D. G. Corneil, "Vertex splitting and the recognition of trapezoid graphs," Discrete Applied Mathematics, vol. 159, no. 11, pp. 1131-1147, 2011. [20] H. Al-Zoubi, H. Alzaareer, A. Zraiqat, T. Hamadneh, and W. Al-Mashaleh, "On ruled surfaces of coordinate finite type," WSEAS Transactions on Mathematics, vol. 21, pp. 765–769, 2022. [21] I. M. Batiha and B. Mohamed, "Binary rat swarm optimizer algorithm for computing independent domination metric dimension problem," Mathematical Models in Engineering, vol. 10, no. 3, pp. 119–132, 2024. [22] I. M. Batiha, B. Mohamed, and I. H. Jebril, "Secure metric dimension of new classes of graphs," Mathematical Models in Engineering, vol. 10, no. 3, pp. 161–167, 2024. [23] I. M. Batiha, M. Amin, B. Mohamed, and H. I. Jebril, "Connected metric dimension of the class of ladder graphs," Mathematical Models in Engineering, vol. 10, pp. 65–74, 2024. [24] I. M. Batiha, N. Anakira, A. Hashim, and B. Mohamed, "A special graph for the connected metric dimension of graphs," Mathematical Models in Engineering, vol. 10, pp. 1–8, 2024. [25] I. M. Batiha, N. Anakira, and B. Mohamed, "Algorithm for finding domination resolving number of a graph," Journal of Mechanics of Continua and Mathematical Sciences, vol. 19, pp. 18–23, 2024. [26] B. Mohamed, I. M. Batiha, M. Odeh, and M. El-Meligy, "Computing the independent domination metric dimension problem of specific graphs," Journal of Mechanics of Continua and Mathematical Sciences, vol. 19, pp. 256–264, 2024. [27] N. Vijaya, B. Rajan, and I. Venkat, "Crossing numbers of join of a graph on six vertices with a path and a cycle," International Journal of Advances in Soft Computing and its Applications, vol. 12, no. 3, pp. 45–58, 2020. [28] A. Kumar and S. Singh, "Fuzzy graph theory approach to network vulnerability assessment," International Journal of Advances in Soft Computing and its Applications, vol. 11, no. 2, pp. 123–134, 2019. [29] M. Rahman and T. K. Das, "Application of graph theory in social network analysis," International Journal of Advances in Soft Computing and its Applications, vol. 10, no. 1, pp. 89– 102, 2018.