Geodesic
The walks and CDC of graphs with the same main eigenspace
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 507-532 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

The main eigenvalues of a graph G are those eigenvalues of the (0,1)-adjacency matrix 𝐀 with a corresponding eigenspace not orthogonal to 𝐣 = (1| 1| ⋯ | 1)^𝖳. The principal main eigenvector associated with a main eigenvalue is the orthogonal projection of the corresponding eigenspace onto 𝐣. 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 
@article{DMGT_2023_43_2_a13,
     author = {Sciriha, Irene and Collins, Luke},
     title = {The walks and {CDC} of graphs with the same main eigenspace},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {507--532},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a13/}
}
TY  - JOUR
AU  - Sciriha, Irene
AU  - Collins, Luke
TI  - The walks and CDC of graphs with the same main eigenspace
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 507
EP  - 532
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a13/
LA  - en
ID  - DMGT_2023_43_2_a13
ER  - 
%0 Journal Article
%A Sciriha, Irene
%A Collins, Luke
%T The walks and CDC of graphs with the same main eigenspace
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 507-532
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a13/
%G en
%F DMGT_2023_43_2_a13
Sciriha, Irene; Collins, Luke. The walks and CDC of graphs with the same main eigenspace. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 507-532. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a13/

[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. https://doi.org/10.2298/AADM0702445R

[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. https://doi.org/10.21136/CMJ.1983.101887