Search

Let Γ be a simple finite graph with vertex set V (Γ) and edge set E (Γ) . Let R be an equivalence relation on V (Γ) . The R -super Γ graph Γ R is a simple graph with vertex set V (Γ) and two distinct vertices are adjacent if either they are in the same R -equivalence class or there are elements in their respective R -equivalence classes that are adjacent in the original graph Γ . We first show that Γ R is a generalized join of some complete graphs and using this we obtain the adjacency and Laplacian spectrum of conjugacy super commuting graphs and order super commuting graphs of dihedral group D 2 n (n ≥ 3) , generalized quaternion group Q 4 m (m ≥ 2) and the nonabelian group Z p ⋊ Z q of order pq, where p and q are distinct primes with q | (p - 1) . [ABSTRACT FROM AUTHOR]

In light of the successful investigation of the adjacency matrix, a significant amount of its modification is observed employing numerous topological indices. The matrix corresponding to the well-known first Zagreb index is one of them. The entries of the first Zagreb matrix are d u i + d u j , if u i is connected to u j ; 0, otherwise, where d u i is degree of i-th vertex. The current work is concerned with the mathematical properties and chemical significance of the spectral radius ( ρ 1 ) associated with this matrix. The lower and upper bounds of ρ 1 are computed with characterizing extremal graphs for the class of unicyclic graphs and trees. The chemical connection of the first Zagreb spectral radius is established by exploring its role as a structural descriptor of molecules. The isomer discrimination ability of ρ 1 is also explained. [ABSTRACT FROM AUTHOR]

Let (G, w) be a weighted graph with the adjacency matrix A. The group inverse of (G, w), denoted by (G # , w #) is the weighted graph with the weight w # (v i v j) of an edge v i v j in G # is defined as the ijth entry of A # , the group inverse of A. We study the group inverse of singular weighted trees. It is shown that if (T, w) is a singular weighted tree, then (T # , w #) is again a weighted tree if and only if (T, w) is a star tree, which in turn holds if and only if (T # , w #) is graph isomorphic to (T, w). A new class T w of weighted trees is introduced and studied here. It is shown that the group inverse of the adjacency matrix of a positively weighted tree in T w is signature similar to a non-negative matrix. [ABSTRACT FROM AUTHOR]

Accurate prediction of traffic flow plays an important role in maintaining traffic order and traffic safety, which is a key task in the application of intelligent transportation systems (ITS). However, the urban road network has complex dynamic spatial correlation and nonlinear temporal correlation, and achieving accurate traffic flow prediction is a highly challenging task. Traditional methods use sensors deployed on roads to construct the spatial structure of the road network and capture spatial information by graph convolution. However, they ignore that the spatial correlation between nodes is dynamically changing, and using a fixed adjacency matrix cannot reflect the real road spatial structure. To overcome these limitations, this paper proposes a new spatial-temporal deep learning model: gated fusion adaptive graph neural network (GFAGNN). GFAGNN first extracts long-term dependencies on raw data through stacking expansion causal convolution, Then the spatial features of the dynamics are learned by adaptive graph attention network and adaptive graph convolutional network respectively, Finally the fused information is passed through a lightweight channel attention to extract temporal features. The experimental results on two public data sets show that our model can effectively capture the spatiotemporal correlation in traffic flow prediction. Compared with GWNET-conv model on METR-LA dataset, the three indexes in the 60-minute task prediction improved by 2.27%,2.06% and 2.13%, respectively. [ABSTRACT FROM AUTHOR]

A formula for the group inverse of trees, obtained recently, is shown to be applicable to a special class of weighted graphs G w studied here. Certain handpicked results, which hold for bipartite graphs, are shown to be true for this class. [ABSTRACT FROM AUTHOR]

Epilepsy is a chronic brain disease, and identifying seizures based on electroencephalogram (EEG) signals would be conducive to implement interventions to help patients reduce impairment and improve quality of life. In this paper, we propose a classification algorithm to apply dynamical graph neural network with attention mechanism to single channel EEG signals. Empirical mode decomposition (EMD) are adopted to construct graphs and the optimal adjacency matrix is obtained by model optimization. A multilayer dynamic graph neural network with attention mechanism is proposed to learn more discriminative graph features. The MLP-pooling structure is proposed to fuse graph features. We performed 12 classification tasks on the epileptic EEG database of the University of Bonn, and experimental results showed that using 25 runs of ten-fold cross-validation produced the best classification results with an average of 99.83 % accuracy, 99.91 % specificity, 99.78 % sensitivity, 99.87 % precision, and 99.47 % F 1 score for the 12 classification tasks. [ABSTRACT FROM AUTHOR]

We introduce a graph attached to mutually orthogonal Sudoku Latin squares. The spectra of the graphs obtained from finite fields are explicitly determined. As a corollary, we then use the eigenvalues to distinguish non-isomorphic Sudoku Latin squares. [ABSTRACT FROM AUTHOR]

Entropy is widely applied to graph theory and complex networks as a powerful tool for measuring uncertainty in a complex system. Due to the fact that traditional probability distribution entropy cannot effectively characterize the global topology information of complex networks, some entropy measures constructed by the adjacency matrix A come into being, such as information-theoretic entropy EE and communicability sequence entropy. Despite substantial efforts to explore the properties of these measures, there remain some imperfections. For instance, the adjacency matrix only reflects the dependence between direct neighbors. Therefore, in this paper, we propose the r -power adjacency matrix entropy ( AME r ) to measure the indirect relationship between nodes in a network. And then, we compare the abilities of AME r , EE, and CSE in capturing the network global topology changes. Furthermore, we establish the Jenson–Shannon divergence based on AME r to quantify the structural dissimilarities of the networks. Finally, we apply the proposed methods to analyze the urban economic connection networks. The results demonstrate the availability of the proposed measures in identifying network topology changes and quantifying network structure differences. [ABSTRACT FROM AUTHOR]

Twin vertices in simple unweighted graphs are vertices that have the same neighbours, and, in the case of weighted graphs with possible loops, the corresponding incident edges have equal weights. In this paper, we explore the role of twin vertices in quantum state transfer. In particular, we provide characterizations of periodicity, perfect state transfer, and pretty good state transfer between twin vertices in a weighted graph with respect to its adjacency, Laplacian and signless Laplacian matrices. As an application, we provide characterizations of all simple unweighted double cones on regular graphs that exhibit periodicity, perfect state transfer, and pretty good state transfer. [ABSTRACT FROM AUTHOR]

For a group G, the generating graph Γ (G) is defined as the graph with the vertex set G, and any two distinct vertices of Γ (G) are adjacent if they generate G. In this paper, we study the generating graph of D n , where D n is a Dihedral group of order 2n. We explore various graph theoretic properties, and determine complete spectrum of the adjacency and the Laplacian matrix of Γ (D n) . Moreover, we compute some distance and degree based topological indices of Γ (D n) . [ABSTRACT FROM AUTHOR]

PM2.5, as the main component of haze, is a serious hazard to human health. Accurate prediction of PM2.5 concentration can help the government to effectively reduce the damage caused by haze events. The prediction of PM2.5 concentration using deep learning models has gradually become a research hotspot. For predicting PM2.5 concentration considering the non-Euclidean distribution characteristics of air quality monitoring stations and the time-series characteristics of pollutant concentration data, a hybrid model combining multi-graph convolution and Long Short-Term Memory network (MGC-LSTM) was proposed in this study, based on the six pollutant concentration data of CO, NO2, O3, PM10, PM2.5, and SO2. Two different methods are used in the study to construct adjacency matrices to build multiple graphs composed of stations, and then, the two matrices were fused into a new graph. We use the adjacency matrix of the new graph and Graph Convolutional Network (GCN) to extract spatial features of the input data, and then transfer the results of GCN into Long Short-Term Memory network (LSTM) to obtain the predicted values of PM2.5 concentration. This empirical study shows that the newly constructed model makes full use of spatiotemporal information and has higher prediction accuracy compared with that of the comparison model. [ABSTRACT FROM AUTHOR]

In this paper, first we introduce the notions of size, order, and degree of vertices and edges in a soft graph, and we give some examples for a better understanding of these concepts. Then, we define the fundamental concepts of the adjacency matrix of soft graphs, complement of soft graphs, and regularity based on the degree of vertices of soft graphs, and we investigate some related results. Moreover, we introduce the concept of soft multiset and soft multigraph and define the notions of union, intersection, complement, and sum, and then we investigate the relations among them. Finally, we give an application of soft graphs in controlling urban traffic flows. [ABSTRACT FROM AUTHOR]

There is a type of distance-regular graph, said to be Q-polynomial. In this paper, we investigate a generalized Q-polynomial property involving a graph that is not necessarily distance-regular. We give a detailed description of an example associated with the projective geometry L N (q) . [ABSTRACT FROM AUTHOR]

We formalize the notion of a sedentary vertex and present a relaxation of the concept of a sedentary family of graphs introduced by Godsil (Linear Algebra Appl 614:356–375, 2021. https://doi.org/10.1016/j.laa.2020.08.027). We provide sufficient conditions for a given vertex in a graph to exhibit sedentariness. We also show that a vertex with at least two twins (vertices that share the same neighbours) is sedentary. We prove that there are infinitely many graphs containing strongly cospectral vertices that are sedentary, which reveals that, even though strong cospectrality is a necessary condition for pretty good state transfer, there are strongly cospectral vertices which resist high probability state transfer to other vertices. Moreover, we derive results about sedentariness in products of graphs which allow us to construct new sedentary families, such as Cartesian powers of complete graphs and stars. [ABSTRACT FROM AUTHOR]

Let λ 2 be the second largest eigenvalue of the adjacency matrix of a connected graph. In 2021, Liu, Chen and Stanić determined all the connected { K 1 , 3 , K 5 - e } -free graphs whose second largest eigenvalue λ 2 ⩽ 1 . In this paper, we completely identify all the connected { K 2 , 3 , K 4 } -minor free graphs whose second largest eigenvalue does not exceed 1. That is, we characterize all the connected outerplanar graphs satisfying λ 2 ⩽ 1 . Furthermore, all the maximal outerplanar graphs having the same property can be deduced by our result obtained in this paper. Our main tools include analyzing the local structure of the outerplanar graph with respect to its girth. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with all non-zero zero divisors Z ∗ (R) of R . Then Γ (R) is said to be a zero divisor graph if and only if a · b = 0 where a , b ∈ V (Γ (R)) = Z ∗ (R) and (a , b) ∈ E (Γ (R)) . Graph energy E (Γ (R)) is defined as the sum of the absolute eigenvalues of the adjacency matrix of Γ (R) , then E (Γ (R)) = ∑ i = 1 n | λ i | . A topological index is a numeric quantity associated with a chemical structure that attempts to link the chemical structure to various physicochemical properties, chemical reactivity, or biological activity. This paper discusses the graph energy and various topological indices of zero divisor graph associated with the commutative ring. [ABSTRACT FROM AUTHOR]

In this article, we undertake the problem of finding the first four trees on a fixed number of vertices with the maximum smallest positive eigenvalue. Let T n , d denote the class of trees on n vertices with diameter d. First, we obtain the bounds on the smallest positive eigenvalue of trees in T n , d for d = 2 , 3 , 4 and then upper bounds on the smallest positive eigenvalue of trees are obtained in general class of all trees on n vertices. Finally, the first four trees on n vertices with the maximum, second maximum, third maximum and fourth maximum smallest positive eigenvalue are characterized. [ABSTRACT FROM AUTHOR]

Let G be a connected d-regular graph and λ 2 (G) be the second largest eigenvalue of its adjacency matrix. Mohar and O (private communication) asked a challenging problem: what is the best upper bound for λ 2 (G) which guarantees that κ (G) ≥ t + 1 , where 1 ≤ t ≤ d - 1 and κ (G) is the vertex-connectivity of G, which was also mentioned by Cioabă. As a starting point, we determine a sharp bound for λ 2 (G) to guarantee κ (G) ≥ 2 (i.e., the case that t = 1 in this problem), and characterize all families of extremal graphs. [ABSTRACT FROM AUTHOR]

Tardive dyskinesia is a involuntary hyperkinetic disorder which usually occurs in older patients after long-term treatment with antipsychotic drugs. These dyskinesias are mostly irreversible and are frequently expressed in the tongue, cheeks, mandible, perioral area and other regions of the face. In this theoretical study we asked the question, why does tardive dyskinesia often have orofacial predominance? What might be the underlying neural network structure which contributes to this propensity? Graph analysis of high-level cortico-striato-thalamo-cortical network structure suggests a connectivity bottleneck. The number of walks of different lengths from the substantia nigra pars reticulata (SNr) to other vertices, as well as the returning cycles are the lowest in the network, which may indicate a higher damage susceptibility of this node. Analysis was also performed on published data from a recent high resolution histological study on cortico-striato-thalamo-cortical networks in rodents. Finer network partitioning and adjacency matrices demonstrated that the SNr has a heterogeneous connectivity structure and the number of local walks from nodes neighboring orofacial neural representation is higher, indicating possible early compensatory escape routes. However, with more extensive SNr damage the larger circuit compensation might be limited. This area of inquiry is important for future research, because identifying key vulnerable structures may provide more targeted therapeutical interventions. [ABSTRACT FROM AUTHOR]

We consider an inhomogeneous Erdős-Rényi random graph G N with vertex set [ N ] = { 1 , ⋯ , N } for which the pair of vertices i , j ∈ [ N ] , i ≠ j , is connected by an edge with probability r (i N , j N) , independently of other pairs of vertices. Here, r : [ 0 , 1 ] 2 → (0 , 1) is a symmetric function that plays the role of a reference graphon. Let λ N be the maximal eigenvalue of the adjacency matrix of G N . It is known that λ N / N satisfies a large deviation principle as N → ∞ . The associated rate function ψ r is given by a variational formula that involves the rate function I r of a large deviation principle on graphon space. We analyse this variational formula in order to identify the properties of ψ r , specially when the reference graphon is of rank 1. [ABSTRACT FROM AUTHOR]

A pointed graph (Γ , v 0) induces a family of transition matrices in Wildberger's construction of a hermitian hypergroup using a random walk on Γ starting from v 0 . In this study, we propose a necessary condition for producing a hermitian hypergroup considering a weaker condition than the distance-regularity for (Γ , v 0) . Furthermore, we show that the condition obtained connects the transition and adjacency matrices associated with Γ . [ABSTRACT FROM AUTHOR]

New proofs of formulae for the inverses of nonsingular adjacency matrices of cycles, and the group inverses of singular adjacency matrices of cycles, are presented. A new columnwise description for the inverse of the adjacency matrix of an even path, and block matrix representations for the group inverse of adjacency matrices of wheels and brooms are also obtained. [ABSTRACT FROM AUTHOR]

Topological indices are widely used in mathematical chemistry to study graphs of molecules of a chemical compound. The comaximal graph of a ring R, denoted by Γ (R) , has elements of R as vertices, and any two distinct vertices x, y of Γ (R) are adjacent if and only if R x + R y = R . In this paper, we find the eigenvalues of the adjacency matrix, and the topological indices of the comaximal graph Γ (Z n) of the ring Z n . We determine the Wiener index, the first and the second Zagreb index, as well as the adjacency and the Laplacian energy of Γ (Z n) . A SAGE code for evaluating the above indices has also been provided at the end of this paper. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set { v 1 , v 2 , ... , v n } and let d i denote the degree of vertex v i . The geometric–arithmetic matrix GA (G) of G is indexed by the vertices of G, whose (i, j) -th entry is 2 d i d j d i + d j if the vertices i and j are adjacent and 0 otherwise. The multi-set of eigenvalues of GA (G) is known as the geometric–arithmetic spectrum of G. In this article, we obtain geometric–arithmetic spectra of various families of graphs and characterize the connected graphs with two and three distinct GA eigenvalues. We obtain several upper and lower bounds for the geometric arithmetic energy and characterize the graphs attaining such bounds. [ABSTRACT FROM AUTHOR]

Let S n and A n denote the symmetric and alternating group on the set { 1 , ... , n } , respectively. In this paper we are interested in the second largest eigenvalue λ 2 (Γ) of the Cayley graph Γ = Cay (G , H) over G = S n or A n for certain connecting sets H. Let 1 < k ≤ n and denote the set of all k-cycles in S n by C(n, k). For H = C (n , n) we prove that λ 2 (Γ) = (n - 2) ! (when n is even) and λ 2 (Γ) = 2 (n - 3) ! (when n is odd). Further, for H = C (n , n - 1) we have λ 2 (Γ) = 3 (n - 3) (n - 5) ! (when n is even) and λ 2 (Γ) = 2 (n - 2) (n - 5) ! (when n is odd). The case H = C (n , 3) has been considered in Huang and Huang (J Algebraic Combin 50:99–111, 2019). Let 1 ≤ r < k < n and let C (n , k ; r) ⊆ C (n , k) be set of all k-cycles in S n which move all the points in the set { 1 , 2 , ... , r }. That is to say, g = (i 1 , i 2 , ... , i k) (i k + 1) ⋯ (i n) ∈ C (n , k ; r) if and only if { 1 , 2 , ... , r } ⊂ { i 1 , i 2 , ... , i k }. Our main result concerns λ 2 (Γ) , where Γ = Cay (G , H) with H = C (n , k ; r) with 1 ≤ r < k < n when G = S n if k is even and G = A n if k is odd. Here we observe that λ 2 (Γ) ≥ (k - 2) ! n - r k - r 1 n - r ((k - 1) (n - k) - (k - r - 1) (k - r) n - r - 1 ). We prove that this bound is attained in the special case k = r + 1 , giving λ 2 (Γ) = r ! (n - r - 1) . The cases with H = C (n , 3 ; 1) and H = C (n , 3 ; 2) were considered earlier in [6]. [ABSTRACT FROM AUTHOR]

We investigate signed graphs with just 2 or 3 distinct eigenvalues, mostly in the context of vertex-deleted subgraphs, the join of two signed graphs or association schemes. [ABSTRACT FROM AUTHOR]

In this paper, we present a new connection between representation theory of noncommutative hypersurfaces and combinatorics. Let S be a graded ( ± 1 )-skew polynomial algebra in n variables of degree 1 and f = x 1 2 + ⋯ + x n 2 ∈ S . We prove that the stable category CM ̲ Z (S / (f)) of graded maximal Cohen–Macaulay module over S/(f) can be completely computed using the four graphical operations. As a consequence, CM ̲ Z (S / (f)) is equivalent to the derived category D b (mod k 2 r) , and this r is obtained as the nullity of a certain matrix over F 2 . Using the properties of Stanley–Reisner ideals, we also show that the number of irreducible components of the point scheme of S that are isomorphic to P 1 is less than or equal to r + 1 2 . [ABSTRACT FROM AUTHOR]

Recent exponential expansion of users adopting to applications on the mobile internet, like e-commerce and social networks, warrants mining of the huge data collected from users' past actions, for improving businesses and services. The core step for mining is to cluster the data meaningfully, conforming to the application. Social network data are structured, and graphical presentation reveals that structure. Therefore, graph clustering is an effective way to divulge the underlying structure in the data. For clustering, calculating similarity between a pair of vectors is the first step. The large dimension of the data, which is often noisy and sparse, makes distance measurement hard. In high dimension, most of the conventional distance metrics fail to work, as the data points are distributed over the surface of the high-dimensional hyper-space. The traditional concept of similarity, and nearest-neighbor does not hold. The variance of distance between any pair of points shrinks as the dimension increases. In this work, we investigate the efficacy of various similarity measures and clustering algorithms on high dimensional data. We experimented with a real-world high-dimensional matrix data, the ratings of movies by users. Clustering of movie items depends on a number of factors like movie genre, actors, directors, prominent acclaimed movie or an obscure one, etc. Different similarity measurements and clustering algorithms were experimented. Clustering results were evaluated by matching with known annotations of the movies. Finally, we proposed a novel recommendation algorithm based on item clustering. Its performance was evaluated with different distance metrics and clustering algorithms. Methods elaborated are applicable to other structured data generated in social network applications, or in biological investigations. [ABSTRACT FROM AUTHOR]

There is substantial interest in the current literature – spanning finance, economics, engineering and medical imaging – on the relationship structure between several nodes in a complex system. In this paper, we extend the literature by developing model and inference for complex networks in terms of latent factors, by extracting the hidden factors that plays significant role in the configuration of inter node relationships. Together, we extend inferences to applications where the underlying network structure is also latent; that is, the adjacency matrix is unobserved. Here, we consider a Bayesian variant of the matrix factorization technique to develop a structural model of the latent adjacency matrix. There are many potential applications. For illustration, we consider a latent network of firms in the in the US automotive sector, where the central object is to understand the impact of an economic shock on firms (or nodes of the network). An important question centers around the factors that affect the stability and resilience of inter node relationships in a network. In the automotive sector application, we would like to know whether these relationship structures are driven by collaborative or competitive environments? What are the effects of a collaborative or competitive role played by a specific firm on the configuration of the relationship network? Using accounting data on firm sales and costs, we use our proposed object oriented factorization methodology to provide explanation of the estimated network links between 3 major US auto manufacturers and their intermediate suppliers. [ABSTRACT FROM AUTHOR]

Isomorphism identification plays an important role in structural design and innovative design. Based on the adjacency matrix and loop theory, a new method is proposed in this paper to identify the isomorphic kinematic chains. It enriches the application of loop-based theory for isomorphism identification. In the kinematic chain, links and joints are connected alternatively and every link corresponds to a fixed link degree. Due to the inherent characteristics, the labeled sequence of links can be random, which does not affect the result of isomorphism identification. By the programming software MATLAB, some examples with 6-, 8-, 10-, 11-, 12-link kinematic chains, and 15-vertex topological graphs are presented. Results show that the proposed method applies to topology graphs and kinematic chains with one or multiple joints. Compared with other methods, the proposed method is confirmed correctly. And there is no counterexample. It lays a solid foundation for structural synthesis in the future. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the conditions for constructing a single deletion error-correcting codes for protecting quantum information. According to the recent study by Nakayama and Hagiwara, this code can be constructed by using two sets of binary sequences satisfying certain three conditions, namely NH conditions. The NH conditions are described only combinatorially, but they are very complicated and only two examples have been given so far. In the present study, we aim to provide many examples of new deletion error-correcting codes by constructing various types of sets that satisfy the NH conditions discussed in the previous research. We show two families of sets satisfying the NH conditions and present a recursive construction method. This allows us to construct n-qubit codes in which the value of n is 4 or more. Furthermore, by discussing the NH conditions in terms of the adjacency matrices of the graph, we obtain all examples with length 5 or less. [ABSTRACT FROM AUTHOR]

We study the balance of G-gain graphs, where G is an arbitrary group, by investigating their adjacency matrices and their spectra. As a first step, we characterize switching equivalence and balance of gain graphs in terms of their adjacency matrices in M n (C G) . Then we introduce a represented adjacency matrix, associated with a gain graph and a group representation, by extending the theory of Fourier transforms from the group algebra C G to the algebra M n (C G) . We prove that, anytime G admits a finite-dimensional faithful unitary representation π , a G-gain graph is balanced if and only if the spectrum of the represented adjacency matrix associated with π coincides with the spectrum of the underlying graph, with multiplicity given by the degree of the representation. We show that the complex adjacency matrix of complex unit gain graphs and the adjacency matrix of a cover graph are indeed particular cases of our construction. This enables us to recover some classical results and prove some new characterizations of balance in terms of spectrum, index or structure of these graphs. [ABSTRACT FROM AUTHOR]

We propose a definition of hub in complex networks by using the eigenvectors of the Laplacian matrix, and suggest a method of detecting hubs. The proposed definition provides a different concept from the classical measures such as the centrality or degree. Also, a method of determining the number of hubs is suggested using a scree plot. Illustrative examples based on artificial data sets and real data sets are given. [ABSTRACT FROM AUTHOR]

We consider the notion of χ -completeness of a locally finite graph and we extend this notion to the weighted magnetic graph. Moreover, we establish a link between the magnetic adjacency matrix on line graph and the magnetic discrete Laplacian on 1-forms. [ABSTRACT FROM AUTHOR]

For a given complex square matrix A with constant row sum, we establish two new eigenvalue inclusion sets. Using these bounds, first, we derive bounds for the second largest and the smallest eigenvalues of adjacency matrices of fc-regular graphs. Then we establish some bounds for the second largest and the smallest eigenvalues of the normalized adjacency matrices of graphs and the second smallest and the largest eigenvalues of the Laplacian matrices of graphs. The sharpness of these bounds is verified by examples. [ABSTRACT FROM AUTHOR]

In this paper, we consider a generalized join operation, the H ˙ -join on signed graphs, where H ˙ is an arbitrary signed graph. We characterize the balancedness of the H ˙ -join graph, determine the adjacency spectra of graphs obtained by this operation on net regular graphs and the Laplacian spectra of graphs obtained on negatively regular graphs. Some additional consequences relevant to integral or cospectral graphs are also given. [ABSTRACT FROM AUTHOR]

The anti-Gallai graph Δ (G) of a graph G, has the edges of G as its vertices and two distinct edges are adjacent in Δ (G) if they lie on a triangle in G. In this paper we characterize the graphs whose anti-Gallai graph has only one or two eigenvalues and study the adjacency spectrum of the anti-Gallai graph of (K 4 , H) -free graphs, where H is the Hajos graph and graphs in which two diamonds share at most one vertex. We also find expressions for the adjacency spectrum of anti-Gallai graph of graphs after applying certain binary operations. [ABSTRACT FROM AUTHOR]

After Curl, Kroto and Smalley were awarded 1996 the Nobel Prize in chemistry, fullerenes have been subject of much research. One part of that research is the prediction of a fullerene's stability using topological descriptors. It was mainly done by considering the distribution of the twelve pentagonal facets on its surface, calculations mostly were performed on all isomers of C40, C60 and C80. This paper suggests a novel method for the classification of combinatorial fullerene isomers using spectral graph theory. The classification presupposes an invariant scheme for the facets based on the Schlegel diagram. The main idea is to find clusters of isomers by analyzing their graph structure of hexagonal facets only. We also show that our classification scheme can serve as a formal stability criterion, which became evident from a comparison of our results with recent quantum chemical calculations (Sure et al. in Phys Chem Chem Phys 19:14296–14305, 2017). We apply our method to classify all isomers of C60 and give an example of two different cospectral isomers of C44. Calculations are done with our own Python scripts available at (Bille et al. in Fullerene database and classification software, https://www.uni-ulm.de/mawi/mawi-stochastik/forschung/fullerene-database/, 2020). The only input for our algorithm is the vector of positions of pentagons in the facet spiral. These vectors and Schlegel diagrams are generated with the software package Fullerene (Schwerdtfeger et al. in J Comput Chem 34:1508–1526, 2013). [ABSTRACT FROM AUTHOR]

An eigenvalue of a real symmetric matrix is called main if there is an associated eigenvector not orthogonal to the all-1 vector j. Main eigenvalues are frequently considered in the framework of simple undirected graphs. In this study we generalize some results and then apply them to signed graphs. [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices and m edges. The edges energy is defined as the sum of the absolute values of eigenvalues of the adjacency matrix of line graph of G. In this paper, the minimum edge dominating energy of the graph G is introduced and the minimum edge dominating energy of some graphs is computed. We also investigate the bounds of the minimum edge dominating energy of graphs. [ABSTRACT FROM AUTHOR]

In the current paper, we study the discrete Laplacian acting on 2-forms which was introduced and investigated by Chebbi (Potential Anal 49(2):331–358, 2018). We establish a new criterion of essential self-adjointness using the Nelson lemma. Moreover, we give an upper bound on the infimum of the essential spectrum. Furthermore, we establish a link between the adjacency matrix and the discrete Laplacian on 2-forms. [ABSTRACT FROM AUTHOR]

The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5 ⩽ k ⩽ 8 and n ⩾ k + 5) with the minimal least eigenvalue. [ABSTRACT FROM AUTHOR]

We present a method to derive the complete spectrum of the lift Γ α of a base digraph Γ , with voltage assignment α on a (finite) group G. The method is based on assigning to Γ a quotient-like matrix whose entries are elements of the group algebra C [ G ] , which fully represents Γ α . This allows us to derive the eigenvectors and eigenvalues of the lift in terms of those of the base digraph and the irreducible characters of G. Thus, our main theorem generalizes some previous results of Lovász and Babai concerning the spectra of Cayley digraphs. [ABSTRACT FROM AUTHOR]

A threshold graph G of order n is defined by binary sequence of length n. In this paper, we consider the adjacent matrix of a connected threshold graph, and give the eigenvalues distribution in threshold graphs. Moreover, we pick out all the threshold graphs with distinct eigenvalues, and determine the HOMO–LUMO index of threshold graphs. [ABSTRACT FROM AUTHOR]

Hand Gestures Recognition (HGR) is one of the main areas of research for Human Computer Interaction applications. Most existing approaches are based on local or geometrical properties of pixels. Still, there are some serious challenges on HGR methods such as sensitivity to rotation, scale, illumination, perturbation, and occlusion. In this paper, we study HGR from graph viewpoints. We introduce a set of meaningful shape features based on a graph constructed by Growing Neural Gas (GNG) algorithm. These features are constructed from topological properties of this graph. Graph properties in conserving topological features improve stability against different deformations, scale, and noise. We evaluate our method on NTU Hand Digits dataset with state-of-the-art methods. We also prepared a comprehensive dataset (SBU-1) for different hand gestures containing 2170 images. This dataset includes many possible deformations and variations and some articulations. Most of the existing datasets don't capture these variations. We show the robustness of the algorithm to scale, rotation and noise, while preserving similar recognition rate in comparison with the state-of-the-art results. [ABSTRACT FROM AUTHOR]

Information extraction from scanned document page images is an important issue in image analysis. The main objectives of this work are: vectorization of image of the digital logic-gate circuits as graph, and automatic generation of Boolean expression. We have employed a novel method for circuit component separation using morphological operators. Connecting wires (in the form of poly lines in the image) lead to adjacency matrix describing directed interconnection between logic gates. Logic gate symbols are recognized by support vector machine (SVM) based on the features obtained by deep convolutional neural network (DCNN). Finally, we exploit this abstract representation of digital logic circuit as a graph to determine the Boolean expression. The approach is tested on a dataset developed by us and the results are encouraging. [ABSTRACT FROM AUTHOR]

Connected planar graphs are of interest to a variety of scholars. Being able to simulate a database of such graphs with selected properties would support specific types of inference for spatial analysis and other network-based disciplines. This paper presents a simple, efficient, and flexible connected planar graph generator for this purpose. It also summarizes a comparison between an empirical set of specimen graphs and their simulated counterpart set, and establishes evidence for positing a conjecture about the principal eigenvalue of connected planar graphs. Finally, it summarizes a probability assessment of the algorithm’s outcomes as well as a comparison between the new algorithm and selected existing planar graph generators. [ABSTRACT FROM AUTHOR]

How to mine many interesting subgraphs in uncertain graph has become an important research field in data mining. In this paper, a novel algorithm Uncertain Maximal Frequent Subgraph Mining Algorithm Based on Adjacency Matrix and Weight (UMFGAMW) is proposed. The definition of the adjacency matrix and the standard matrix coding for uncertain graph are presented. The correspondence between the adjacency matrix and uncertain graph is established. A new vertex ordering policy for computing the standard coding of uncertain graph adjacency matrix is designed. The complexity of uncertain graph standard coding is reduced, and the matching speed of uncertain subgraph standard coding is improved. The definition of the weight of uncertain graph and the mean weight of uncertain edge is proposed. The importance of the uncertain subgraphs that meet the minimum support threshold in the graph dataset is fully considered. Finally, a depth-first search weighted uncertain maximal frequent subgraph mining algorithm is discussed. According to the limiting condition of the uncertain maximum frequent subgraph and weighed uncertain edge, the number of mining results is reduced effectively. Experimental results demonstrate that the UMFGAMW algorithm has higher efficiency and better scalability. [ABSTRACT FROM AUTHOR]

In this paper, a tolerance representation model for generating tolerance specification schemes and corresponding tolerance zones is proposed to meet the requirement of the representation of tolerance information semantics. This model is hierarchically organized and consists of five layers. They are component, geometric feature, variational geometric constraint, tolerance specification scheme, and tolerance zone layers. The mating relations between components in the component layer, the mating relations between geometric features in the geometric feature layer, the variational geometric constraints between geometric features in the variational geometric constraint layer, the tolerance specification schemes of component in the tolerance specification scheme layer, and the tolerance zones of tolerance specification schemes in the tolerance zone layer are formally defined by one or more adjacency matrices, respectively. Based on the model, a method for generating tolerance specification schemes for component and their resultant tolerance zones is designed. This method shows how to adopt a top-down strategy to carry out tolerance specification for an arbitrary assembly designed in a CAD system. The paper also provides a practical example to illustrate how the method works. [ABSTRACT FROM AUTHOR]