The spectral theory of graph is an important branch of graph theory,and the main part of this theory is the connection between the spectral properties and the structural properties,characterization of the structural p...The spectral theory of graph is an important branch of graph theory,and the main part of this theory is the connection between the spectral properties and the structural properties,characterization of the structural properties of graphs.We discuss the problems about singularity,signature matrix and spectrum of mixed graphs.Without loss of generality,parallel edges and loops are permitted in mixed graphs.Let G1 and G2 be connected mixed graphs which are obtained from an underlying graph G.When G1 and G2 have the same singularity,the number of induced cycles in Gi(i=1,2)is l(l=1,l>1),the length of the smallest induced cycles is 1,2,at least 3.According to conclusions and mathematics induction,we find that the singularity of corresponding induced cycles in G1 and G2 are the same if and only if there exists a signature matrix D such that L(G2)=DTL(G1)D.D may be the product of some signature matrices.If L(G2)=D^TL(G1)D,G1 and G2 have the same spectrum.展开更多
Using resting-state functional magnetic resonance imaging (fMRI) technology to assist in identifying brain diseases has great potential. In the identification of brain diseases, graph-based models have been widely use...Using resting-state functional magnetic resonance imaging (fMRI) technology to assist in identifying brain diseases has great potential. In the identification of brain diseases, graph-based models have been widely used, where graph represents the similarity between patients or brain regions of interest. In these models, constructing high-quality graphs is of paramount importance. Researchers have proposed various methods for constructing graphs from different perspectives, among which the simplest and most popular one is Pearson Correlation (PC). Although existing methods have achieved significant results, these graphs are usually fixed once they are constructed, and are generally operated separately from downstream task. Such a separation may result in neither the constructed graph nor the extracted features being ideal. To solve this problem, we use the graph-optimized locality preserving projection algorithm to extract features and the population graph simultaneously, aiming in higher identification accuracy through a task-dependent automatic optimization of the graph. At the same time, we incorporate supervised information to enable more flexible modelling. Specifically, the proposed method first uses PC to construct graph as the initial feature for each subject. Then, the projection matrix and graph are iteratively optimized through graph-optimization locality preserving projections based on semi-supervised learning, which fully employs the knowledge in various transformation spaces. Finally, the obtained projection matrix is applied to construct the subject-level graph and perform classification using support vector machines. To verify the effectiveness of the proposed method, we conduct experiments to identify subjects with mild cognitive impairment (MCI) and Autism spectrum disorder (ASD) from normal controls (NCs), and the results showed that the classification performance of our method is better than that of the baseline method.展开更多
Let D(G) =(d_(ij))_(n×n) denote the distance matrix of a connected graph G with order n, where d_(ij) is equal to the distance between vertices viand vjin G. A graph is called distance integral if all eigenvalues...Let D(G) =(d_(ij))_(n×n) denote the distance matrix of a connected graph G with order n, where d_(ij) is equal to the distance between vertices viand vjin G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a sufficient and necessary condition for complete r-partite graphs K_(p1,p2,···,pr)=K_(a1·p1,a2·p2,···,as···ps) to be distance integral and obtained such distance integral graphs with s = 1, 2, 3, 4. However distance integral complete multipartite graphs K_(a1·p1,a2·p2,···,as·ps) with s > 4 have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs K_(a1·p1,a2·p2,···,as·ps) with s = 5, 6. The problem of the existence of such distance integral graphs K_(a1·p1,a2·p2,···,as·ps) with arbitrarily large number s remains open.展开更多
A graph G is called integral if all the eigenvalues of the adjacency matrix A（G） of G are integers. In this paper, the graphs G4（a, b） and Gs（a, b） with 2a ＋ 6b vertices are defined. We give their characteristi...A graph G is called integral if all the eigenvalues of the adjacency matrix A（G） of G are integers. In this paper, the graphs G4（a, b） and Gs（a, b） with 2a ＋ 6b vertices are defined. We give their characteristic polynomials from matrix theory and prove that the （n ＋ 2）-regular graphs G4（n, n＋ 2） and G5（n, n ＋ 2） are a pair of non-isomorphic connected cospectral integral regular graphs for any positive integer n.展开更多
Let G be a graph of order n and let λ1, λ2,...,λn be its eigenvalues. The Estrada index[2] of G is defined as EE = EE（G） =∑i=1^n e^λi.In this paper, new bounds for EE are established, as well as some relations ...Let G be a graph of order n and let λ1, λ2,...,λn be its eigenvalues. The Estrada index[2] of G is defined as EE = EE（G） =∑i=1^n e^λi.In this paper, new bounds for EE are established, as well as some relations between EE and graph energy E.展开更多
For a simple graph G,let matrix Q(G)=D(G) + A(G) be it's signless Laplacian matrix and Q G (λ)=det(λI Q) it's signless Laplacian characteristic polynomial,where D(G) denotes the diagonal matrix of vertex deg...For a simple graph G,let matrix Q(G)=D(G) + A(G) be it's signless Laplacian matrix and Q G (λ)=det(λI Q) it's signless Laplacian characteristic polynomial,where D(G) denotes the diagonal matrix of vertex degrees of G,A(G) denotes its adjacency matrix of G.If all eigenvalues of Q G (λ) are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K(n_1,n_2,···,n_t).We prove that the complete t-partite graphs K(n,n,···,n)t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K(m,···,m)s(n,···,n)t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K(m,···,m,)s1(n,···,n,)s2(l,···,l)s3.展开更多
In this paper, an equivalent condition of a graph G with t （2≤ t ≤n） distinct Laplacian eigenvalues is established. By applying this condition to t = 3, if G is regular （necessarily be strongly regular）, an equi...In this paper, an equivalent condition of a graph G with t （2≤ t ≤n） distinct Laplacian eigenvalues is established. By applying this condition to t = 3, if G is regular （necessarily be strongly regular）, an equivalent condition of G being Laplacian integral is given. Also for the case of t = 3, if G is non-regular, it is found that G has diameter 2 and girth at most 5 if G is not a tree. Graph G is characterized in the case of its being triangle-free, bipartite and pentagon-free. In both cases, G is Laplacian integral.展开更多
基金Quality Engineering Project of Anhui Province,China(No.2017zhkt036)
文摘The spectral theory of graph is an important branch of graph theory,and the main part of this theory is the connection between the spectral properties and the structural properties,characterization of the structural properties of graphs.We discuss the problems about singularity,signature matrix and spectrum of mixed graphs.Without loss of generality,parallel edges and loops are permitted in mixed graphs.Let G1 and G2 be connected mixed graphs which are obtained from an underlying graph G.When G1 and G2 have the same singularity,the number of induced cycles in Gi(i=1,2)is l(l=1,l>1),the length of the smallest induced cycles is 1,2,at least 3.According to conclusions and mathematics induction,we find that the singularity of corresponding induced cycles in G1 and G2 are the same if and only if there exists a signature matrix D such that L(G2)=DTL(G1)D.D may be the product of some signature matrices.If L(G2)=D^TL(G1)D,G1 and G2 have the same spectrum.
文摘Using resting-state functional magnetic resonance imaging (fMRI) technology to assist in identifying brain diseases has great potential. In the identification of brain diseases, graph-based models have been widely used, where graph represents the similarity between patients or brain regions of interest. In these models, constructing high-quality graphs is of paramount importance. Researchers have proposed various methods for constructing graphs from different perspectives, among which the simplest and most popular one is Pearson Correlation (PC). Although existing methods have achieved significant results, these graphs are usually fixed once they are constructed, and are generally operated separately from downstream task. Such a separation may result in neither the constructed graph nor the extracted features being ideal. To solve this problem, we use the graph-optimized locality preserving projection algorithm to extract features and the population graph simultaneously, aiming in higher identification accuracy through a task-dependent automatic optimization of the graph. At the same time, we incorporate supervised information to enable more flexible modelling. Specifically, the proposed method first uses PC to construct graph as the initial feature for each subject. Then, the projection matrix and graph are iteratively optimized through graph-optimization locality preserving projections based on semi-supervised learning, which fully employs the knowledge in various transformation spaces. Finally, the obtained projection matrix is applied to construct the subject-level graph and perform classification using support vector machines. To verify the effectiveness of the proposed method, we conduct experiments to identify subjects with mild cognitive impairment (MCI) and Autism spectrum disorder (ASD) from normal controls (NCs), and the results showed that the classification performance of our method is better than that of the baseline method.
基金Supported by the National Natural Science Foundation of China（11171273） Supported by the Graduate Starting Seed Fund of Northwestern Polytechnical University（Z2014173）
文摘Let D(G) =(d_(ij))_(n×n) denote the distance matrix of a connected graph G with order n, where d_(ij) is equal to the distance between vertices viand vjin G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a sufficient and necessary condition for complete r-partite graphs K_(p1,p2,···,pr)=K_(a1·p1,a2·p2,···,as···ps) to be distance integral and obtained such distance integral graphs with s = 1, 2, 3, 4. However distance integral complete multipartite graphs K_(a1·p1,a2·p2,···,as·ps) with s > 4 have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs K_(a1·p1,a2·p2,···,as·ps) with s = 5, 6. The problem of the existence of such distance integral graphs K_(a1·p1,a2·p2,···,as·ps) with arbitrarily large number s remains open.
基金Supported by the National Natural Science Foundation of China (10871158, 70871098)the Natural Science Basic Research Plan in Shaanxi Province of China (SJ08A01, 2007A09) and SRF for ROCS, SEM
文摘A graph G is called integral if all the eigenvalues of the adjacency matrix A（G） of G are integers. In this paper, the graphs G4（a, b） and Gs（a, b） with 2a ＋ 6b vertices are defined. We give their characteristic polynomials from matrix theory and prove that the （n ＋ 2）-regular graphs G4（n, n＋ 2） and G5（n, n ＋ 2） are a pair of non-isomorphic connected cospectral integral regular graphs for any positive integer n.
基金Supported by the National Natural Science Foundation of China(10771080)by the Fund of Fuzhou Uni-versity(XRC-0956)by the Natural Science Foundation of Fujian Province(2010J05005)
文摘Let G be a graph of order n and let λ1, λ2,...,λn be its eigenvalues. The Estrada index[2] of G is defined as EE = EE（G） =∑i=1^n e^λi.In this paper, new bounds for EE are established, as well as some relations between EE and graph energy E.
基金Supported by the NSFC(60863006)Supported by the NCET(-06-0912)Supported by the Science-Technology Foundation for Middle-aged and Yong Scientist of Qinghai University(2011-QGY-8)
文摘For a simple graph G,let matrix Q(G)=D(G) + A(G) be it's signless Laplacian matrix and Q G (λ)=det(λI Q) it's signless Laplacian characteristic polynomial,where D(G) denotes the diagonal matrix of vertex degrees of G,A(G) denotes its adjacency matrix of G.If all eigenvalues of Q G (λ) are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K(n_1,n_2,···,n_t).We prove that the complete t-partite graphs K(n,n,···,n)t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K(m,···,m)s(n,···,n)t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K(m,···,m,)s1(n,···,n,)s2(l,···,l)s3.
基金Supported by the Anhui Provincial Natural Science Foundation(050460102)National Natural Science Foundation of China(10601001,10571163)+3 种基金NSF of Department of Education of Anhui Province(2004kj027,2005kj005zd)Foundation of Anhui Institute of Architecture and Industry(200510307)Foundation of Mathematics Innovation Team of Anhui UniversityFoundation of Talents Group Construction of Anhui University
文摘In this paper, an equivalent condition of a graph G with t （2≤ t ≤n） distinct Laplacian eigenvalues is established. By applying this condition to t = 3, if G is regular （necessarily be strongly regular）, an equivalent condition of G being Laplacian integral is given. Also for the case of t = 3, if G is non-regular, it is found that G has diameter 2 and girth at most 5 if G is not a tree. Graph G is characterized in the case of its being triangle-free, bipartite and pentagon-free. In both cases, G is Laplacian integral.
