A subdivision vertex-edge corona G_1~S?(∪ G_3~E) is a graph that consists of S(G_1),|V(G_1)| copies of G_2 and |I(G_1)| copies of G_3 by joining the i-th vertex in V(G_1) to each vertex in the i-th copy of G_2 and i-...A subdivision vertex-edge corona G_1~S?(∪ G_3~E) is a graph that consists of S(G_1),|V(G_1)| copies of G_2 and |I(G_1)| copies of G_3 by joining the i-th vertex in V(G_1) to each vertex in the i-th copy of G_2 and i-th vertex of I(G_1) to each vertex in the i-th copy of G_3.In this paper, we determine the normalized Laplacian spectrum of G_1~S?(G_2~V∪ G_3~E) in terms of the corresponding normalized Laplacian spectra of three connected regular graphs G_1, G_2 and G_3. As applications, we construct some non-regular normalized Laplacian cospectral graphs. In addition, we also give the multiplicative degree-Kirchhoff index, the Kemeny's constant and the number of the spanning trees of G_1~S?(G_2~V∪ G_3~E) on three regular graphs.展开更多
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.展开更多
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.展开更多
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.展开更多
Let H（n; q, n1, n2, n3, n4） be a unicyclic graph with n vertices containing a cycle Cq and four hanging paths Ph1＋1, Pn2＋1, Pn3＋1 and Pn4＋1 attached at the same vertex of the cycle. In this paper, it is proved t...Let H（n; q, n1, n2, n3, n4） be a unicyclic graph with n vertices containing a cycle Cq and four hanging paths Ph1＋1, Pn2＋1, Pn3＋1 and Pn4＋1 attached at the same vertex of the cycle. In this paper, it is proved that all unicyclic graphs H （n; q, n1, n2, n3, n4） are determined by their Laplacian spectra.展开更多
Let G be a connected graph of order n and D(G) be its distance matrix. The distance eigenvalues of G are the eigenvalues of its distance matrix. Its distance eigenvalues and their multiplicities constitute the distanc...Let G be a connected graph of order n and D(G) be its distance matrix. The distance eigenvalues of G are the eigenvalues of its distance matrix. Its distance eigenvalues and their multiplicities constitute the distance spectrum of G. In this article, we give a complete description of the eigenvalues and the corresponding eigenvectors of a block matrix D_(NC). Further, we give a complete description of the eigenvalues and the corresponding eigenvectors of distance matrix of double neighbourhood corona graphs G^((S))· {G_1, G_2}, G^((Q))· {G_1, G_2}, G^((R))· {G_1, G_2},G^((T))· {G_1, G_2}, where G is a complete graph and G_1, G_2 are regular graphs.展开更多
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.展开更多
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.展开更多
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.展开更多
Let Hn（p,q） be a tree obtained from two stars K1,p and K1,q by identifying the center of K1,p with one end of a path Pn and the center of K1,q with the other end of Pn.We call Hn（p,p-1） a double quasi-star tree.In...Let Hn（p,q） be a tree obtained from two stars K1,p and K1,q by identifying the center of K1,p with one end of a path Pn and the center of K1,q with the other end of Pn.We call Hn（p,p-1） a double quasi-star tree.In this paper,we show that a double quasi-star tree is determined by its Laplacian spectrum.展开更多
Over the past few decades, the world has witnessed a rapid growth in mobile and wireless networks（MWNs） which significantly change human life. However, proliferating mobile demands lead to several intractable challe...Over the past few decades, the world has witnessed a rapid growth in mobile and wireless networks（MWNs） which significantly change human life. However, proliferating mobile demands lead to several intractable challenges that MWN has to face. Software-defined network is expected as a promising way for future network and has captured growing attention. Network virtualization is an essential feature in software-defined wireless network（SDWN）, and it brings two new entities, physical networks and virtual networks. Accordingly, efficiently assigning spectrum resource to virtual networks is one of the fundamental problems in SDWN. Directly orienting towards the spectrum resource allocation problem, firstly, the fluctuation features of virtual network requirements in SDWN are researched, and the opportunistic spectrum sharing method is introduced to SDWN. Then, the problem is proved as NP-hardness. After that, a dynamic programming and graph theory based spectrum sharing algorithm is proposed.Simulations demonstrate that the opportunistic spectrum sharing method conspicuously improves the system performance up to around 20%–30% in SDWN, and the proposed algorithm achieves more efficient performance.展开更多
Let G be a finite group of order n. The strong power graph of G is the undirected graph whose vertex set is G and two distinct vertices x and y are adjacent if x^n1 = y^n2 for some positive integers n1,n2 < n. In t...Let G be a finite group of order n. The strong power graph of G is the undirected graph whose vertex set is G and two distinct vertices x and y are adjacent if x^n1 = y^n2 for some positive integers n1,n2 < n. In this paper, we give the characteristic polynomials of the distance and adjacency matrix of the strong power graph of G, and compute its distance and adjacency spectrum.展开更多
In this paper, we attempt to resolve the problem of grading of brain tumors as grade 2, grade 3, grade 4, using information from magnetic resonance spectroscopy (MRS) image, to assist in clinical diagnosis. This paper...In this paper, we attempt to resolve the problem of grading of brain tumors as grade 2, grade 3, grade 4, using information from magnetic resonance spectroscopy (MRS) image, to assist in clinical diagnosis. This paper proposes a novel approach to extract metabolite values represented in a graphical form in MR Spectroscopy image. Metabolites like N-acetyl aspartate (NAA), Choline (CHO) along with the metabolite ratios NAA/CHO and presence/absence of LACTATE peak play the most important role in deciding the tumor type. The proposed approach consists of several steps including preprocessing, metabolite peak height scanning and classification. Proposed system stores the metabolite values in dataset instead of storing MRS images;so reduces the image processing tasks and memory requirements. Further these metabolite values and ratios are fed to a BPN classifier. Experimental results demonstrate the effectiveness of the proposed approach in classifying the brain tumors.展开更多
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.展开更多
基金Supported by the Young Scholars Science Foundation of Lanzhou Jiaotong University(Grant Nos.20160142017004+3 种基金 2017021)the Education Foundation of Gansu Province(Grant No.2017A-021)the National Natural Science Foundation of China(Grant Nos.11461038 61163010)
文摘A subdivision vertex-edge corona G_1~S?(∪ G_3~E) is a graph that consists of S(G_1),|V(G_1)| copies of G_2 and |I(G_1)| copies of G_3 by joining the i-th vertex in V(G_1) to each vertex in the i-th copy of G_2 and i-th vertex of I(G_1) to each vertex in the i-th copy of G_3.In this paper, we determine the normalized Laplacian spectrum of G_1~S?(G_2~V∪ G_3~E) in terms of the corresponding normalized Laplacian spectra of three connected regular graphs G_1, G_2 and G_3. As applications, we construct some non-regular normalized Laplacian cospectral graphs. In addition, we also give the multiplicative degree-Kirchhoff index, the Kemeny's constant and the number of the spanning trees of G_1~S?(G_2~V∪ G_3~E) on three regular graphs.
基金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.
基金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 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.
基金the National Natural Science Foundation of China(Grant No.11171273)Graduate StartingSeed Fund of Northwestern Polytechnical University(Grant No.Z2014173)
文摘Let H（n; q, n1, n2, n3, n4） be a unicyclic graph with n vertices containing a cycle Cq and four hanging paths Ph1＋1, Pn2＋1, Pn3＋1 and Pn4＋1 attached at the same vertex of the cycle. In this paper, it is proved that all unicyclic graphs H （n; q, n1, n2, n3, n4） are determined by their Laplacian spectra.
基金Supported by the Dalian Science and Technology Project(Grant No.2015A11GX016)
文摘Let G be a connected graph of order n and D(G) be its distance matrix. The distance eigenvalues of G are the eigenvalues of its distance matrix. Its distance eigenvalues and their multiplicities constitute the distance spectrum of G. In this article, we give a complete description of the eigenvalues and the corresponding eigenvectors of a block matrix D_(NC). Further, we give a complete description of the eigenvalues and the corresponding eigenvectors of distance matrix of double neighbourhood corona graphs G^((S))· {G_1, G_2}, G^((Q))· {G_1, G_2}, G^((R))· {G_1, G_2},G^((T))· {G_1, G_2}, where G is a complete graph and G_1, G_2 are regular graphs.
基金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 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 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.
基金Project supported by the Natural Science Foundation of Gausu Province (Grant Nos.3Z5051-A25-037, 0809RJZA017)the National Natural Science Foundation of China (Grant No.50877034)the Foundation of Lanzhou University of Technology(Grant No.0914ZX136)
文摘Let Hn（p,q） be a tree obtained from two stars K1,p and K1,q by identifying the center of K1,p with one end of a path Pn and the center of K1,q with the other end of Pn.We call Hn（p,p-1） a double quasi-star tree.In this paper,we show that a double quasi-star tree is determined by its Laplacian spectrum.
基金supported by the National Natural Science Foundation of China(6102100161133015+4 种基金61171065)the National Natural Science Foundation of China(973 Program)(2013CB329001)the National High Technology ResearchDevelopment Program(863 Program)(2013AA0106052013AA013500)
文摘Over the past few decades, the world has witnessed a rapid growth in mobile and wireless networks（MWNs） which significantly change human life. However, proliferating mobile demands lead to several intractable challenges that MWN has to face. Software-defined network is expected as a promising way for future network and has captured growing attention. Network virtualization is an essential feature in software-defined wireless network（SDWN）, and it brings two new entities, physical networks and virtual networks. Accordingly, efficiently assigning spectrum resource to virtual networks is one of the fundamental problems in SDWN. Directly orienting towards the spectrum resource allocation problem, firstly, the fluctuation features of virtual network requirements in SDWN are researched, and the opportunistic spectrum sharing method is introduced to SDWN. Then, the problem is proved as NP-hardness. After that, a dynamic programming and graph theory based spectrum sharing algorithm is proposed.Simulations demonstrate that the opportunistic spectrum sharing method conspicuously improves the system performance up to around 20%–30% in SDWN, and the proposed algorithm achieves more efficient performance.
基金Supported by the National Natural Science Foundation of China(Grant No.11801441)the Scientific Research Program Funded by Shaanxi Provincial Education Department(Program No.18JK0623)the Natural Science Foundation of Shaanxi Province(Grant No.2019JQ-056)
文摘Let G be a finite group of order n. The strong power graph of G is the undirected graph whose vertex set is G and two distinct vertices x and y are adjacent if x^n1 = y^n2 for some positive integers n1,n2 < n. In this paper, we give the characteristic polynomials of the distance and adjacency matrix of the strong power graph of G, and compute its distance and adjacency spectrum.
文摘In this paper, we attempt to resolve the problem of grading of brain tumors as grade 2, grade 3, grade 4, using information from magnetic resonance spectroscopy (MRS) image, to assist in clinical diagnosis. This paper proposes a novel approach to extract metabolite values represented in a graphical form in MR Spectroscopy image. Metabolites like N-acetyl aspartate (NAA), Choline (CHO) along with the metabolite ratios NAA/CHO and presence/absence of LACTATE peak play the most important role in deciding the tumor type. The proposed approach consists of several steps including preprocessing, metabolite peak height scanning and classification. Proposed system stores the metabolite values in dataset instead of storing MRS images;so reduces the image processing tasks and memory requirements. Further these metabolite values and ratios are fed to a BPN classifier. Experimental results demonstrate the effectiveness of the proposed approach in classifying the brain tumors.
文摘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.
