Search

In this article, we discuss the spectral properties of the general extended adjacency matrix for chain graphs. In particular, we discuss the eigenvalues of the general extended adjacency matrix of the chain graphs and obtain its general extended adjacency inertia. We obtain bounds for the largest and the smallest general extended adjacency eigenvalues and characterize the extremal graphs. We also obtain a lower bound for the spread of the general extended adjacency matrix. We characterize chain graphs with all the general extended adjacency eigenvalues being simple and chain graphs that are non-singular under the general extended adjacency matrix. Further, we determine the explicit formula for the determinant and the trace of the square of the general extended adjacency matrix of chain graphs. Finally, we discuss the energy of the general extended adjacency matrix and obtain some bounds for it. We characterize the extremal chain graphs attaining these bounds. [ABSTRACT FROM AUTHOR]

Applying machine learning algorithms to graph-structured data has garnered significant attention in recent years due to the prevalence of inherent graph structures in real-life datasets. However, the direct application of traditional deep learning algorithms, such as Convolutional Neural Networks (CNNs), is limited as they are designed for regular Euclidean data like 2D grids and 1D sequences. In contrast, graph-structured data are in a non-Euclidean form. Graph Neural Networks (GNNs) are specifically designed to handle non-Euclidean data and make predictions based on connectivity rather than spatial structure. Real-life graph data can be broadly categorized into two types: spatially-invariant graphs, where the link structure between nodes is independent of their spatial positions, and spatially-variant graphs, where node positions provide additional information about the graph's properties. However, there is limited understanding of the effect of spatial variance on the performance of Graph Neural Networks. In this study, we aim to address this issue by comparing the performance of GNNs and CNNs on spatially-variant and spatially-invariant graph data. In the case of spatially-variant graphs, when represented as adjacency matrices, they can exhibit Euclidean-like spatial structure. Based on this distinction, we hypothesize that CNNs may outperform GNNs when working with spatially-variant graphs, while GNNs may excel on spatially-invariant graphs. To test this hypothesis, we compared the performance of CNNs and GNNs under two scenarios: (i) graphs in the training and test sets had the same connectivity pattern and spatial structure, and (ii) graphs in the training and test sets had the same connectivity pattern but different spatial structures. Our results confirmed that the presence of spatial structure in a graph allows for the effective use of CNNs, which may even outperform GNNs. Thus, our study contributes to the understanding of the effect of spatial graph structure on the performance of machine learning methods and allows for the selection of an appropriate algorithm based on the spatial properties of the real-life graph dataset. [ABSTRACT FROM AUTHOR]

Let G be a graph with the adjacency matrix A (G) , and let D (G) be the diagonal matrix of the degrees of G. Nikiforov first defined the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , 0 ≤ α ≤ 1 , which shed new light on A (G) and Q (G) = D (G) + A (G) , and yielded some surprises. The α − adjacency energy E A α (G) of G is a new invariant that is calculated from the eigenvalues of A α (G) . In this work, by combining matrix theory and the graph structure properties, we provide some upper and lower bounds for E A α (G) in terms of graph parameters (the order n, the edge size m, etc.) and characterize the corresponding extremal graphs. In addition, we obtain some relations between E A α (G) and other energies such as the energy E (G) . Some results can be applied to appropriately estimate the α -adjacency energy using some given graph parameters rather than by performing some tedious calculations. [ABSTRACT FROM AUTHOR]

For a simple graph with vertex set { v 1 , v 2 , ... , v n } with degree sequence d v i of vertex v i , i = 1 , 2 , ... , n , the inverse sum indeg matrix ( I S I -matrix) A I S I (G) = (a i j) n × n of G is defined by a i j = d v i d v j d v i + d v j , if v i is adjacent to v j , and zero, otherwise. The multiset of eigenvalues of A I S I (G) is the I S I -spectrum of G and the sum of their absolute values is the I S I -energy of G . In this paper, we modify the two results of (Li, Ye and Broersma, 2022), give the correct characterization of the extremal graphs and thereby obtain better bounds than the already known results. Moreover, we also discuss the QSPR analysis and carry the statistical modelling (linear, logarithmic and quadratic) of the physicochemical properties of anticancer drugs with the I S I -index (energy). [ABSTRACT FROM AUTHOR]

In a certain class of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum. A connected graph containing two or three cycles is called a bicyclic graph if its number of edges is equal to its number of vertices plus one. Let G1,nc and G2,ncbe the classes of the connected graphs of order n whose complements are bicyclic with exactly two and three cycles, respectively. In this paper, we characterize the unique minimizing graph among all the graphs which belong to Gnc= G1,nc [ G2,nc, a class of the connected graphs of order n whose complements are bicyclic. [ABSTRACT FROM AUTHOR]

The Estrada index of a graph G is defined as E E (G) = ∑ i = 1 n e λ i , where λ 1 , λ 2 , ... , λ n are the eigenvalues of the adjacency matrix of G. A unicyclic graph is a connected graph with a unique cycle. Let U (n , d) be the set of all unicyclic graphs with n vertices and diameter d. In this paper, we give some transformations which can be used to compare the Estrada indices of two graphs. Using these transformations, we determine the graphs with the maximum Estrada indices among U (n , d) . We characterize two candidate graphs with the maximum Estrada index if d is odd and three candidate graphs with the maximum Estrada index if d is even. [ABSTRACT FROM AUTHOR]

For α ∈ [ 0 , 1 ] , let A α (G σ) = α D (G) + (1 − α) A (G σ) , where G is a simple undirected graph, D (G) is the diagonal matrix of its vertex degrees and A (G σ) is the adjacency matrix of the signed graph G σ whose underlying graph is G. In this paper, basic properties of A α (G σ) are obtained, its positive semidefiniteness is studied and some bounds on its eigenvalues are derived—in particular, lower and upper bounds on its largest eigenvalue are obtained. [ABSTRACT FROM AUTHOR]

Let G be a graph on n vertices. The Estrada index of G is an invariant that is calculated from the eigenvalues of the adjacency matrix of a graph. V. Nikiforov studied hybrids of A (G) and D (G) and defined the A α -matrix for every real α ∈ [ 0 , 1 ] as: A α (G) = α D (G) + (1 − α) A (G). In this paper, using a different demonstration technique, we present a way to compare the Estrada index of the A α -matrix with the Estrada index of the adjacency matrix of the graph G. Furthermore, lower bounds for the Estrada index are established. [ABSTRACT FROM AUTHOR]

Let A (G) be the adjacent matrix and D (G) the diagonal matrix of the degrees of a graph G, respectively. For 0 ≤ α ≤ 1 , the A α -matrix is the general adjacency and signless Laplacian spectral matrix having the form of A α (G) = α D (G) + (1 − α) A (G) . Clearly, A 0 (G) is the adjacent matrix and 2 A 1 2 is the signless Laplacian matrix. A cactus is a connected graph such that any two of its cycles have at most one common vertex, that is an extension of the tree. The A α -spectral radius of a cactus graph with n vertices and k cycles is explored. The outcomes obtained in this paper can imply some previous bounds from trees to cacti. In addition, the corresponding extremal graphs are determined. Furthermore, we proposed all eigenvalues of such extremal cacti. Our results extended and enriched previous known results. [ABSTRACT FROM AUTHOR]

This paper puts forward an innovative theory and method to calculate the canonical labelings of graphs that are distinct to N a u t y 's. It shows the correlation between the canonical labeling of a graph and the canonical labeling of its complement graph. It regularly examines the link between computing the canonical labeling of a graph and the canonical labeling of its o p e n k- n e i g h b o r h o o d s u b g r a p h . It defines d i f f u s i o n d e g r e e s e q u e n c e s and e n t i r e d i f f u s i o n d e g r e e s e q u e n c e . For each node of a graph G, it designs a characteristic m _ N e a r e s t N o d e to improve the precision for calculating canonical labeling. Two theorems established here display how to compute the first nodes of M a x Q (G) . Another theorem presents how to determine the second nodes of M a x Q (G) . When computing C m a x (G) , if M a x Q (G) already holds the first i nodes u 1 , u 2 , ⋯ , u i , Diffusion and Nearest Node theorems provide skill on how to pick the succeeding node of M a x Q (G) . Further, it also establishes two theorems to determine the C m a x (G) of disconnected graphs. Four algorithms implemented here demonstrate how to compute M a x Q (G) of a graph. From the results of the software experiment, the accuracy of our algorithms is preliminarily confirmed. Our method can be employed to mine the frequent subgraph. We also conjecture that if there is a node v ∈ S (G) meeting conditions C m a x (G − v) ⩽ C m a x (G − w) for each w ∈ S (G) ∧ w ≠ v , then u 1 = v for M a x Q (G) . [ABSTRACT FROM AUTHOR]

Energies of molecular graphs have various applications in chemistry, polymerization, computer networking and pharmacy. In this paper, we give general closed forms of distance and adjacency energies of generalized wheel networks W n , m . Consequently, we give these results for classical wheel graphs. We also give pictorial dependencies of energies on the involved parameters m ≥ 3 and n . [ABSTRACT FROM AUTHOR]