ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


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



The walks and CDC of graphs with the same main eigenspace



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 ,


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.


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


  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.
  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.
  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.
  9. D.L. Powers and M.M. Sulaiman, The walk partition and colorations of a graph, Linear Algebra Appl. 48 (1982) 145–159.
  10. P. Rowlinson, The main eigenvalues of a graph: A survey, Appl. Anal. Discrete Math. 1 (2007) 445–471.
  11. I. Sciriha and D.M. Cardoso, Necessary and sufficient conditions for a Hamiltonian graph, J. Combin. Math. Combin. Comput. (JCMCC) 80 (2012) 127–150.
  12. B. Zelinka, Double covers and logics of graphs, Czechoslovak Math. J. 33 (1983) 354–360.