On the Spectral Parameters of certain Interconnection Networks, Nanosheets and Benzenoid Systems

Introduction

Interconnection Networks are extremely important in designing computer networks that can be designed with minimum transmission delay, maximum fault tolerance, enhanced embeddability and more beneficial features. The spectral properties that are derived can be used to analyse various properties of these networks and can be exploited in various branches of computer science [10].

Chemical graphs play a significant role in predicting the mathematical tools that correlate a molecule’s chemical structure with its observed biological activity and physico-chemical property in a cost-effective manner [6]. To this end, certain spectral parameters of some variants of hypercube,benzenoid systems and nanosheets have been computed. It is observed that there exists a linear relationship between the dimensions of the graphs and their energy. Further, the results in this article substantiate the fact all the molecular graphs whose degree of the vertices do not exceed three, are all non-hyperenergetic. Thus, this article explains how the behaviour of adjacency matrices creates an impact in the chemical properties of a molecule. 

Preliminaries

This section deals with all the prerequisites that are essential for the understanding of this article.

Definition 1. [5] The sum of the absolute values of the eigenvalues of the adjacency matrix of a graph G is termed as the energy, E(G)of a graph G.

Definition 2. [4, 12] The largest and the smallest eigenvalues from the adjacency matrix of a graph G are referred to as the spectral radius or index and the least eigenvalue of Grespectively.

Definition 3. [7] The difference between the spectral radius and the least eigenvalue of G is called the spreadof Gand the difference between the spectral radius and the second largest eigenvalue is termed as separator of G.

Definition 4. [8] Ahyperenergeticgraph is one whose energy is greater than twice one less than the number of vertices.

Definition 5. [1] A graph in which all the vertices have their degree one of the two values {a, b} is said to be biregular.­­­­­­­­­

Definition 6.[3] Pericondensedbenzenoids constitute Carbon Nanotubes (CNTs), which are ordered in graphite-like, hexagonal pattern. The pericondensedbenzenoid graphs (r, l), r, l ≥ 1 are obtained by joining r hexagonal chains with l hexagons in each chain as seen in Figure 1.

Figure 1: The pericondensedbenzenoid graphs (r, l) Click here to View Figure

Definition 7. [3] Aconvex benzenoid systemhas the structureBS(n, p, q, r, s) for n ≥ 1, 0 ≤ p ≤ r ≤ n, 0 ≤ s ≤ q ≤ n and p + q = r + s. See Figure 2.

Figure 2: The convex benzenoid system Click here to View Figure

Definition 8. [3] The convex benzenoid system that reduces according to the component value n, that is, the parallelogram shaped benzenoid system (n, m) is depicted in Figure 3.

Figure 3: The parallelogram shaped benzenoid system (n, m) Click here to View Figure

Definition 9. [3] Type –IC₄C₈(S) Inanosheet T¹[p,q] is the 2-dimensional lattice of TUC₄ C₈ (S)[p,q]  nanotube, where p and q are defining parameters. See Figures 4 and 5.

Figure 4: TUC4 C8 (S)[p,q] nanotube Click here to View Figure

Figure 5: Type – I C4 C8 (S)  nanosheet Click here to View Figure

Definition 10. [3] Type – II C₄ C₈ (R) nanosheet T²[p,q] is the 2-dimensional lattice of TUC₄ C₈ (R)[p,q] nanotube, where p and q are defining parameters. See Figures 6 and 7.

Figure 6: TUC4 C8 (R)[p,q] nanotube Click here to View Figure

Figure 7: Type – II C4 C8 (R) nanosheet Click here to View Figure

Definition 11. [3] A H–naphtalenicnanosheet (n, m) is made by alternating hexagons C₆, squares C₄ and octagons C₈ . See Figure 8.

Figure 8: H-naphtalenicnanosheet (n, m) Click here to View Figure

Definition 12. [6] The benzenoid system which can be extended to any dimension and satisfies the condition that the limit of the ratio of the number of internal vertices to the total number of vertices is less than 1 as n → ∞ are called as homologous series of extruded benzenoid systems. Following are some classes of such graphs. See Figures 9 to 16.

Figure 9: Dn Click here to View Figure

Figure 10: En Click here to View Figure

Figure 11: Fn Click here to View Figure

Figure 12: Gn Click here to View Figure

Figure 13: In Click here to View Figure

Figure 14: Jn Click here to View Figure

Figure 15: Kn Click here to View Figure

Figure 16: Ln Click here to View Figure

Definition 13. [11] The enhanced hypercube Q_r,k, 0 ≤ k ≤ r– 1 is a graph with vertex setsame as that of Q_r and the edge set includes the edges of Q_r along with the edges between the vertices labelled with complementary indices. See figures 17 and 18.

Figure 17: Q3,2 Click here to View Figure

Figure 18: Q4,2 Click here to View Figure

Definition 14. [2] An augmented hypercube is one which the vertex set is same as that of the hypercube with the corresponding dimension. The edges are drawn between the vertices if the binary address denoting the vertices differ exactly by one bit. See figures 19 and 20.

Figure 19: AQ2 Click here to View Figure

Figure 20: AQ3 Click here to View Figure

Lemma 1. [9] The characteristic polynomial of Circum-coronene(1) of the class of chemical graphs Circum-coronene(n) is x⁶ – 6x⁴ + 9x² – 4.

Theorem 1. [8] If a graph G is a disconnected graphs with components G₁, G₂, …, G_k, then its characteristic polynomial φ(G) can be written as a product of the characteristic polynomials of all the components.

Theorem 2. [8] If uv is an edge of G, then the characteristic polynomial  of the graph G can be expressed as φ(G) = φ(G-uv) – φ(G – u – v) – 2 ∑_C∈C(uv) φ(G – C) where C(uv) is the set of cycles containing uv.

Theorem 3.[1] The largest eigenvalue of the adjacency matrix of a k-regular graph will be k.

Spectral Parameters of Enhanced Hypercube and Augmented Hypercube 

Theorem 4. The enhanced hypercube Q_r,k has the following spectral parameters:

Proof. The enhanced hypercubesQ_r,k is a variant of the hypercube with the vertex set same as that of the hypercube and the edge set has some additional edges called complementary edges. All these additional edges which increase the connectivity between the vertices, are incident with one vertex of the form, x₀ x₁ x₂ ⋯ x_k-2 x_k-1 x_k ⋯x_r-1 and another vertex of the form x₀ x₁ x₂ ⋯ x_k-2 x_k-1 x_k ⋯x_r-1,  where x_i = 0 or 1, 0 ≤ i ≤ r – 1. This (r + 1)-regular graph has 2^r vertices and (r + 1)2^r–1 edges. Using Theorem 3, (i) follows.

The adjacency matrix of the enhanced hypercube Q_r,k is a 2^r × 2^r matrix which can be viewed as A+B, where A is the adjacency matrix of the hypercube Q_r and B is the adjacency matrix of disjoint copies of some bipartite graphs. When r = 2, 3, it can be seen that the bipartite graphs are P₂, when r = 4, the bipartite graphs are C₄ and so on.

Hence, the matrix B can in turn be recognized as a sum of adjacency matrices of bipartite graphs. Thus, the adjacency matrix of Q_r,k can be realized as the sum of adjacency matrices of bipartite graphs, since Q_r is also bipartite. Now, each of these matrices in the sum can be represented in the form of

whose spectrum is symmetric with respect to 0.

Thus, solving the characteristic equation of each of these matrices to obtain their eigenvalues would yield the second largest eigenvalue of the adjacency matrix of Q_r,k. Note that all the adjacency matrices considered here are of the order 2^r × 2^r and only the edges are taken according to the corresponding subgraph. From these formulations, (ii) and (iii) follow.

Theorem 5. The augmented hypercubes have the following spectral parameters:

Proof. The augmented hypercubesAQ^r is a variant of the hypercube which has some extra edges apart from those of the hypercube. The vertices are labeled as r-bit binary strings and the extra edges are between any two distinct vertices if the corresponding elements in the binary string are the same or complement to each other. This resultant graph which is constructed in a recursive manner is 2r – 1 regular and possesses 2^r vertices and (2r – 1)2^r–1 edges. Thus, (ii) follows from Theorem 3.

It can be observed that the extra edges that are added form disjoint copies of bipartite graphs such as P₂, C₄ and so on. The eigenvalues of the bipartite graphs possess symmetry about zero and can thus be computed in a relatively smaller amount of time compared to other graphs. This ensures that the adjacency matrix of the augmented hypercubes can be realized as the sum of the adjacency matrices of bipartite graphs whose adjacency matrices are represented in the form of a block matrix as shown below:

Note that all the adjacency matrices considered here are of the order 2^r × 2^r and only the edges are taken according to the corresponding subgraph. Resolving the eigenvalues of the adjacency matrices, the theorem follows.

Spectral Parameters of Pericondensed Benzenoid Graph and Parallelogram Shaped Benzenoid System 

Theorem 6. The pericondensedbenzenoid graph (r, l) has the following spectral parameters:

Proof.Pericondensedbenzenoid graphs are obtained by attaching r hexagonal chains of l hexagons each. See Figure 1. This is a biregular graph which has vertices of degrees 2 and 3 only. One can observe that this is also a bipartite graph whose adjacency matrix can be represented as,

in which each partition of the set of vertices possess r(2l + 1) vertices equally.

To obtain the characteristic polynomial, the graph is viewed as r⌈l/2⌉ hexagons connected by a path of length 1 or 2. Then, using Lemma 1, the characteristic polynomial of each of these disjoint hexagons can be computed. By Theorem 1, the characteristic polynomial of the disconnected graph in which each of the components is a hexagon can be obtained. Further, considering each of the remaining 6r(l – ⌈l/2⌉ ) + r – l edges that constitute the connecting paths separately and applying Theorem 2, the characteristic polynomial of the pericondensedbenzenoid graphs can be achieved from which the theorem follows.

Theorem 7. The Parallelogram shaped benzenoid system (n, m) has the following spectral parameters:

Proof. The parallelogram shaped benzenoid graphs are a class of graphs which possess 2(mn + m + n) vertices. See Figure 3. When m and n are equal to 1, it can be seen that its spectrum is,

Hence, energy is equal to 8 in this case. It can be observed that with increase in one mvalue, the number of vertices increase by 2n + 2 and with increase in one n value, the vertices count rise by 2m + 2. In each case, the energy increases by 3n – 3 and 3m – 3 respectively. Thus, by using mathematical induction, the energy of this class of graph can be obtained as 3m (n + 1) +3n -1.

(ii) to (vi) can also be proved in a similar manner.

Spectral Parameters of Certain Nanosheets

In this section, the spectral parameters of three nanosheets, namely, Type-I C₄ C₈ (S) nanosheet, Type-II C₄ C₈ (R) nanosheet, H-naphtalenic nanosheet are obtained by analysing their adjacency matrices.

Theorem 8. The Type – I C₄ C₈ (S) nanosheet, T¹ [p,q] has the following spectral parameters:

Proof. The Type-I C₄ C₈ (S)  nanosheet T¹ [p,q] is a tessellation of C₈ connected by adjoining the cycle C₄. See Figure 5. The adjacency matrix of this class of graphs is a 8pq × 8pq matrix that can be represented as the sum of adjacency matrix of the disjoint components of C₈ and the adjacency matrix of the disjoint components of C₄. Both these adjacency matrices are of the form (⁰_B^{T  B}₀) since the components of C₈ and C₄ are bipartite. The characteristic polynomial of these components of C₈ and C₄ can be obtained as an outcome of Theorem 1. Note that the adjacency matrices considered here are of order 8pq × 8pq and only the edges are taken according to the corresponding subgraph. With these formulations, the characteristic polynomial for this class of graph can be easily obtained and hence the theorem follows.                                                                                                                                     □

Remark 1. E(T¹ [p,q]) = E(T¹ [q,p])

Theorem 9.The Type-II C₄ C₈ (R)  nanosheet, denoted by T² [p,q]  has the following spectral parameters:

Proof. The Type-II C₄ C₈ (R)  nanosheet is a trivalent decoration which consists of the cycles C₄  connected to one another by a single edge. See Figure 7. This forms a tessellation of C₄ and C₈ . The adjacency matrix for this class of graphs will be a 4(p + 1)(q + 1) × 4(p + 1)(q + 1) matrix which can be realised as the sum of adjacency matrices of disjoint components of C₄ and C₈. Now, the characteristic polynomial of the disjoint components of  C₄ and C₈ can be computed as an outcome of Theorem 1. From these formulations, one can easily obtain the characteristic polynomial for this class of graph and hence the theorem follows.

Remark 2.E(T² [p,q]) = E(T² [q,p])

Theorem 10. The H-naphtalenicnanosheet (n, m) has the following spectral parameters:

Proof. The class of H-naphtalenicnanosheet is a class of graphs which constitutes the cycles and . This is a trivalent decoration which consists of m chains containing n pairs of hexagons connected by . See Figure 8. Adjoining these chains by connecting the vertices of hexagons together, an octagon is formed. The adjacency matrix for this class of graph is  matrix that can be represented as the sum of three adjacency matrices of the hexagons, squares and octagons respectively. Note that all the adjacency matrices considered here are of the order  and only the edges are taken according to the corresponding subgraph namely, hexagons, squares and octagons. The characteristic polynomial of each of these adjacency matrices which constitute the sum may be computed using Theorem 1. With these formulations, one can easily obtain the characteristic polynomial for this class of graphs and hence the theorem follows.

Spectral Parameters of the Homologous Series of Extruded Benzenoid Systems

This section includes the findings on the spectral parameters of some homologous series of extruded benzenoid systems which extend with respect to one parameter.

Theorem 11. The benzenoidsystem , given in Figure 9, has the following spectral parameters:

Proof. The benzenoid system D_n is a class of graphs that extends in three directions for one dimension. The total number of vertices in each dimension is 12n + 6. For n = 0, it follows from Lemma 1 that the spectrum of D_n is

and hence E(D₀) = 8. As the dimension of D_n increases by one, the vertices count increase by 12 and the value of energy increases by 17 (approx.). Using mathematical induction, it follows that E(D_n) =17n + 8. (ii) to (vi) can be proved in a similar manner.

Theorem 12. The benzenoidsystem E_n, given in Figure 10, has the following spectral parameters:

Proof. The benzenoid system E_n extends in each dimension with the attachment of three hexagons to the graph of preceeding dimension. See Figure 10. The total number of vertices for this class of graph is 12n + 2. The number of vertices increase by 12 for increase in one dimension which in turn increases the energy by 19 (approx.). Using mathematical induction, it is clear that E(E_n) = 17n + 2. Similarly, (ii) to (vi) can be proved.                                     □

Theorem 13. The benzenoidsystem F_n, given in Figure 11, has the following spectral parameters:

Proof. The benzenoid system  is a class of graphs that possesses 10n + 4 vertices which extends by appending three hexagons to the graph of the preceeding dimension. It can be observed that the vertices count increase by 10 and the value of energy increases by 25 (approx.) with increase in one dimension. Using mathematical induction, one can see that E(F_n) = 15n + 4. (ii) to (vi) can be proved in a similar manner.                                        □

Along similar lines, we prove the following results.

Theorem 14. The benzenoidsystem G_n, given in Figure 12, has the following spectral parameters:

Theorem 15. The benzenoidsystem I_n, given in Figure 13, has the following spectral parameters:

Theorem 16. The benzenoidsystem J_n, given in Figure 14, has the following spectral parameters:

Theorem 17. The benzenoidsystem K_n, given in Figure 15, has the following spectral parameters:

Theorem 18. The benzenoidsystem L_n, given in Figure 16, has the following spectral parameters:

Conclusion 

The various chemical structures considered in this chapter have vast practical applications. With the motive of obtaining the quantum-theoretic characteristics of these molecules, some spectral parameters are computed for the same. In particular, analytic expressions have been derived for different spectral parameters of various classes of chemical graphs. It is also observed that energy increases with increase in dimension for all the chemical graphs considered. Further, the results obtained in this article verify the fact that all molecular graphs are non-hyperenergetic. We believe that the results obtained in this article will pave way for a cost effective, time saving interpretations about chemical graphs and interconnection networks.

Acknowledgement 

We thank DST (FIST 2015) MATLAB R2017b which was used for computational purposes. This research is supported by the SEED Grant of the Stella Maris Centre for Human Resource Development (SMCHRD), Stella Maris College, Chennai, India.

Funding Sources

The author(s) received no financial support for the research, authorship, and/or publication of this article.

Conflict of Interest

The author(s) do not have any conflict of interest.

Data Availability Statement

This statement does not apply to this article.

Ethics Statement

This research did not involve human participants, animal subjects, or any material that requires ethical approval.

References 

1. Brouwer, A. E.; Haemers, H. W.; Spectra of Graphs. 2012, Springer, New York.
   CrossRef
2. Choudum, S. A.; Sunitha, V.; Networks. 2002, 40(2), 71–84.
   CrossRef
3. Clement, J.; Topological indices of polycyclic benzenoid and its related chemical structures. 2018, Ph.D. Thesis, University of Madras, Chennai.
4. Fan, Y. Z.; Yu, G. D.; Wang, Y.; The Electronic Journal of Combinatorics. 2012, 19(1), 1–8.
   CrossRef
5. Gutman, I.; Berichte der Mathematisch-StatistischenSektionimForschungszentrum Graz. 1978, 103, 1–22.
6. Gutman, I.; Dömötör, G.; Lam, P. C. B.; Shiu, W. C.; Popović, L.; Polycyclic Aromatic Compounds. 1996, 8(4), 259–270.
   CrossRef
7. Hong, W. X.; You, L. H.; Transactions on Combinatorics. 2014, 3(3), 1–9.
8. Li, X.; Shi, Y.; Gutman, I.; Graph Energy. 2012, Springer Science and Business Media, New York.
   CrossRef
9. Sarah Surya, S.; JasinthaQuadras, S.; Subbulakshmi, P.; Eurasian Chemical Communications. 2022, 4(2), 113–123.
10. Sarah Surya, S.; Subbulakshmi, P.; Communications in Mathematics and Applications. 2023, 14(1), 349–373.
    CrossRef
11. Tzeng, N. F.; Wei, S.; IEEE Transactions on Computers. 1991, 40(3), 284–294.
    CrossRef
12. Wang, T.; Jia, L.; Sun, F.; The Scientific World Journal. 2014, 2014, 1–7.
    CrossRef