In Discrete Mathematics 306 (2005) 153-158, So proposed a conjecture saying that integral circulant graphs with different connection sets have different spectra. This conjecture is still open. We ...prove that this conjecture holds for integral circulant graphs whose orders have prime factorization of 4 types.
L.A. Bunimovich and B.Z. Webb developed a theory for isospectral graph reduction. We make a simple observation regarding the relation between eigenvectors of the original graph and its reduction, ...that sheds new light on this theory. As an application we propose an updating algorithm for the maximal eigenvector of the Markov matrix associated with a large sparse dynamical network.
Coronae Graphs and Their α-Eigenvalues Tahir, Muhammad Ateeq; Zhang, Xiao-Dong
Bulletin of the Malaysian Mathematical Sciences Society,
07/2020, Letnik:
43, Številka:
4
Journal Article
Recenzirano
Odprti dostop
Let
G
1
and
G
2
be two simple connected graphs. The properties of
α
-
eigenvalues of four coronal graphs of
G
1
and
G
2
:
G
1
∘
G
2
,
G
1
◊
G
2
,
G
1
⊙
G
2
and
G
1
⊝
G
2
have been studied. As an ...application, we construct infinitely many pairs of non-isomorphic graphs with the same
α
-eigenvalues.
L. A. Bunimovich and B. Z. Webb developed a theory for transforming a finite weighted graph while preserving its spectrum, referred as isospectral reduction theory. In this workwe extend this theory ...to a class of operators on Banach spaces that include Markov type operators. We apply this theory to infinite countable weighted graphs admitting a finite structural set to calculate the stationary measures of a family of countable Markov chains.
To track the gradual change of the adjacency matrix of a simple graph G into the signless Laplacian matrix, V. Nikiforov in 35 suggested the study of the convex linear combination Aα (α-adjacency ...matrix),Aα(G)=αD(G)+(1−α)A(G), for α∈0,1, where A(G) and D(G) are the adjacency and the diagonal vertex degrees matrices of G, respectively. Taking this definition as an idea the next matrix was considered for a,b∈R. The matrix Aa,b defined byAa,b(G)=aD(G)+bA(G), extends the previous α-adjacency matrix. This matrix is designated the (a,b)-adjacency matrix ofG. Both adjacency matrices are examples of universal matrices already studied by W. Haemers. In this paper, we study the (a,b)-adjacency spectra for a family of compound graphs formed by disjoint balanced trees whose roots are identified to the vertices of a given graph. In consequence, new families of cospectral (adjacency, Laplacian and signless Laplacian) graphs, new hypoenergetic graphs (graphs whose energy is less than its vertex number) and new explicit formulae for Estrada, signless Laplacian Estrada and Laplacian Estrada indices of graphs were obtained. Moreover, sharp upper bounds of the above indices for caterpillars, in terms of length of the path and of the maximum number of its pendant vertices, are given.
Via the process of isospectral graph reduction the adjacency matrix of a graph can be reduced to a smaller matrix while its spectrum is preserved up to some known set. It is then possible to estimate ...the spectrum of the original matrix by considering Gershgorin-type estimates associated with the reduced matrix. The main result of this paper is that eigenvalue estimates associated with Gershgorin, Brauer, Brualdi, and Varga improve as the matrix size is reduced. Moreover, given that such estimates improve with each successive reduction, it is also possible to estimate the eigenvalues of a matrix with increasing accuracy by repeated use of this process.
A new code, binary 2-dimentional code (B2DC), is proposed for polyominoes. An algorithm based on the B2DC and the reverse search method are proposed for enumerating nonisomorphic planar simply ...connected polyominoes. An enumeration tree and a new father-son relationship are defined for enumerating polyominoes. Then we propose an algorithm to build adjacent matrices and laplacian matrices by B2DCs of polyominoes and search isospectral polyomino graphs by computing characteristic polynomials of those matrices.
On Isospectral Graphs TAN, Jinsong
Interdisciplinary Information Sciences,
1998, Letnik:
4, Številka:
2
Journal Article
Odprti dostop
We study combinatorial Laplacians of graphs, and provide examples of isospectral graphs, including finite and infinite ones, as well as isospectral graphs with boundaries. Two general methods for the ...construction of isospectral graphs with boundaries are also presented.