DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

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


Authors:

I. Sciriha

Irene Sciriha

Department of Mathematics
Faculty of Science
University of Malta

email: irene.sciriha-aquilina@um.edu.mt

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

PDF

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.
    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

Close