# Smith Normal Form and the Generalized Spectral Characterization of Graphs

@inproceedings{Qiu2021SmithNF, title={Smith Normal Form and the Generalized Spectral Characterization of Graphs}, author={Lihong Qiu and Wei Wang and Hao Zhang}, year={2021} }

Spectral characterization of graphs is an important topic in spectral graph theory, which has received a lot of attention from researchers in recent years. It is generally very hard to show a given graph to be determined by its spectrum. Recently, Wang [10] gave a simple arithmetic condition for graphs being determined by their generalized spectra. Let G be a graph with adjacency matrix A on n vertices, and W = [e, Ae, . . . , Ae] (e is the allone vector) be the walk-matrix of G. A theorem of… Expand

#### One Citation

Graphs with at most one generalized cospectral mate

- Mathematics
- 2021

Let G be an n-vertex graph with adjacency matrix A, and W = [e,Ae, . . . , An−1e] be the walk-matrix of G, where e is the all-one vector. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the… Expand

#### References

SHOWING 1-10 OF 11 REFERENCES

A new arithmetic criterion for graphs being determined by their generalized Q-spectrum

- Computer Science, Mathematics
- Discret. Math.
- 2019

It is shown that if det W Q ( G) is odd and square-free, then G is DGQS, which is said to be determined by the generalized Q -spectrum (DGQS for short). Expand

A sufficient condition for a family of graphs being determined by their generalized spectra

- Mathematics, Computer Science
- Eur. J. Comb.
- 2006

This paper proposes a new method for determining whether a family of graphs (which have no special properties) are DS with respect to their generalized spectra, obtained by employing some arithmetic properties of a certain matrix associated with a graph. Expand

On the Generalized Spectral Characterizations of Eulerian Graphs

- Computer Science, Mathematics
- Electron. J. Comb.
- 2019

A simple method for a large family of Eulerian graphs to be DGS is given and numerical experiments are presented to illustrate the effectiveness of the proposed method. Expand

On the Smith normal form of walk matrices

- Mathematics
- 2021

Abstract Let G be a graph with n vertices. The walk matrix W ( G ) of G is the matrix [ e , A e , … , A n − 1 e ] , where A is the adjacency matrix of G and e is the all-one vector. Let W be a walk… Expand

Developments on spectral characterizations of graphs

- Computer Science, Mathematics
- Discret. Math.
- 2009

A survey of answers to the question of which graphs are determined by the spectrum of some matrix associated to the graph and some research questions on the topic are given. Expand

A simple arithmetic criterion for graphs being determined by their generalized spectra

- Mathematics, Computer Science
- J. Comb. Theory, Ser. B
- 2017

It is shown that the conjecture that every graph in $\mathcal{F}_n$ is DGS is actually true, thereby giving a simple arithmetic condition for determining whether a graph is D GS. Expand

A note on cospectral graphs

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 1980

It is shown that in many instances this adjacency matrix is superior to the usual (0, 1) adjacencies, and will distinguish cospectral pairs, when the latter will not. Expand

Which graphs are determined by their spectrum

- Mathematics
- 2003

For almost all graphs the answer to the question in the title is still unknown. Here we survey the cases for which the answer is known. Not only the adjacency matrix, but also other types of… Expand

Theory of linear and integer programming

- Mathematics, Computer Science
- Wiley-Interscience series in discrete mathematics and optimization
- 1999

Introduction and Preliminaries. Problems, Algorithms, and Complexity. LINEAR ALGEBRA. Linear Algebra and Complexity. LATTICES AND LINEAR DIOPHANTINE EQUATIONS. Theory of Lattices and Linear… Expand

Graphs with at most one generalized cospectral mate

- Mathematics
- 2021

Let G be an n-vertex graph with adjacency matrix A, and W = [e,Ae, . . . , An−1e] be the walk-matrix of G, where e is the all-one vector. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the… Expand