DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

I. Sciriha

Irene Sciriha

Department of Mathematics
Faculty of Science
University of Malta

L. Collins

Luke Collins

Department of Mathematics13 Faculty of Science14 University of Warwick

email: luke.collins@um.edu.mt

Title:

The walks and CDC of graphs with the same main eigenspace

Source:

Discussiones Mathematicae Graph Theory 43(2) (2023) 507-532

Received: 2019-12-29 , Revised: 2020-11-13 , Accepted: 2020-11-13 , Available online: 2020-12-20 , https://doi.org/10.7151/dmgt.2386

Abstract:

The main eigenvalues of a graph $G$ are those eigenvalues of the $(0,1)$-adjacency matrix $\mathbf A$ with a corresponding eigenspace not orthogonal to $\boldsymbol j = (1| 1| \cdots | 1)^{\mathsf T}$. The principal main eigenvector associated with a main eigenvalue is the orthogonal projection of the corresponding eigenspace onto $\boldsymbol j$. The main eigenspace of a graph is generated by all the principal main eigenvectors and is the same as the image of the walk matrix. We explore a new concept to see to what extent the main eigenspace determines the entries of the walk matrix of a graph. The CDC of a graph $G$ is the direct product $G× K_2$. We establish a hierarchy of inclusions connecting classes of graphs in view of their CDC, walk matrix, main eigenvalues and main eigenspaces. We provide a new proof that graphs with the same CDC are characterized as TF-isomorphic graphs. A complete list of TF-isomorphic graphs on at most 8 vertices and their common CDC is also given.

Keywords:

bipartite (canonical) double covering, main eigenspace, comain graphs, walk matrix, two-fold isomorphism

References:

1. J. Curmi, , private communication.
2. D. Cvetković and M. Petrić, A table of connected graphs on six vertices, Discrete Math. 50 (1984) 37–49.
https://doi.org/10.1016/0012-365X(84)90033-5
3. D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, 3rd Edition (Heidelberg, Johann Ambrosius Barth, 1995).
4. E.M. Hago, Some results on graph spectra, Linear Algebra Appl. 356 (2002) 103–111.
https://doi.org/10.1016/S0024-3795(02)00324-5
5. Wolfram Research, , Inc. Mathematica, Version 12.0..
6. J. Lauri, R. Mizzi and R. Scapellato, Two-fold orbital digraphs and other constructions, Int. J. Pure Appl. Math. 1 (2004) 63–93.
7. F. Liu and J. Siemons, Unlocking the walk matrix of a graph ((2020).
arXiv: 1911.00062v3
8. B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014) 94–112.
https://doi.org/10.1016/j.jsc.2013.09.003
9. D.L. Powers and M.M. Sulaiman, The walk partition and colorations of a graph, Linear Algebra Appl. 48 (1982) 145–159.
https://doi.org/10.1016/0024-3795(82)90104-5
10. P. Rowlinson, The main eigenvalues of a graph: A survey, Appl. Anal. Discrete Math. 1 (2007) 445–471.