Article in volume
Authors:
Title:
The walks and CDC of graphs with the same main eigenspace
PDFSource:
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:
- J. Curmi, , private communication.
- 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 - D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, 3rd Edition (Heidelberg, Johann Ambrosius Barth, 1995).
- 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 - Wolfram Research, , Inc. Mathematica, Version 12.0..
- J. Lauri, R. Mizzi and R. Scapellato, Two-fold orbital digraphs and other constructions, Int. J. Pure Appl. Math. 1 (2004) 63–93.
- F. Liu and J. Siemons, Unlocking the walk matrix of a graph ((2020).
arXiv: 1911.00062v3 - 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 - 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 - P. Rowlinson, The main eigenvalues of a graph: A survey, Appl. Anal. Discrete Math. 1 (2007) 445–471.
https://doi.org/10.2298/AADM0702445R - I. Sciriha and D.M. Cardoso, Necessary and sufficient conditions for a Hamiltonian graph, J. Combin. Math. Combin. Comput. (JCMCC) 80 (2012) 127–150.
- B. Zelinka, Double covers and logics of graphs, Czechoslovak Math. J. 33 (1983) 354–360.
https://doi.org/10.21136/CMJ.1983.101887
Close