1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The Walks and CDC of Graphs with the Same Main Eigenspace

Published Online: 21 Jan 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 29 Dec 2019
Accepted: 13 Nov 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

The main eigenvalues of a graph G are those eigenvalues of the (0, 1)-adjacency matrix A with a corresponding eigenspace not orthogonal to j = (1 | 1 | · · · | 1)T. The principal main eigenvector associated with a main eigenvalue is the orthogonal projection of the corresponding eigenspace onto 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 × K2. 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

MSC 2010

[1] J. Curmi, Private communication.Search in Google Scholar

[2] D. Cvetković and M. Petrić, A table of connected graphs on six vertices, Discrete Math. 50 (1984) 37–49. doi:10.1016/0012-365X(84)90033-510.1016/0012-365X(84)90033-5Search in Google Scholar

[3] D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, 3rd Edition (Heidelberg, Johann Ambrosius Barth, 1995).Search in Google Scholar

[4] E.M. Hago, Some results on graph spectra, Linear Algebra Appl. 356 (2002) 103–111. doi:10.1016/S0024-3795(02)00324-510.1016/S0024-3795(02)00324-5Search in Google Scholar

[5] Wolfram Research, Inc. Mathematica, Version 12.0.Search in Google Scholar

[6] J. Lauri, R. Mizzi and R. Scapellato, Two-fold orbital digraphs and other constructions, Int. J. Pure Appl. Math. 1 (2004) 63–93.Search in Google Scholar

[7] F. Liu and J. Siemons, Unlocking the walk matrix of a graph, (2020). arXiv:1911.00062v3 [math.CO].Search in Google Scholar

[8] B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014) 94–112. doi:10.1016/j.jsc.2013.09.00310.1016/j.jsc.2013.09.003Search in Google Scholar

[9] D.L. Powers and M.M. Sulaiman, The walk partition and colorations of a graph, Linear Algebra Appl. 48 (1982) 145–159. doi:10.1016/0024-3795(82)90104-510.1016/0024-3795(82)90104-5Search in Google Scholar

[10] P. Rowlinson, The main eigenvalues of a graph: A survey, Appl. Anal. Discrete Math. 1 (2007) 445–471. doi:10.2298/AADM0702445R10.2298/AADM0702445RSearch in Google Scholar

[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.Search in Google Scholar

[12] B. Zelinka, Double covers and logics of graphs, Czechoslovak Math. J. 33 (1983) 354–360. doi:10.21136/CMJ.1983.10188710.21136/CMJ.1983.101887Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo