Paper Info
Title
Estimation of Laplacian spectra of direct and strong product graphs
Abstract
Calculating a product of multiple graphs has been studied in mathematics, engineering, computer science, and more recently in network science, particularly in the context of multilayer networks. One of the important questions to be addressed in this area is how to characterize spectral properties of a product graph using those of its factor graphs. While several such characterizations have already been obtained analytically (mostly for adjacency spectra), characterization of Laplacian spectra of direct product and strong product graphs has remained an open problem. Here we develop practical methods to estimate Laplacian spectra of direct and strong product graphs from spectral properties of their factor graphs using a few heuristic assumptions. Numerical experiments showed that the proposed methods produced reasonable estimation with percentage errors confined within a ¿ 10 % range for most eigenvalues.
Year
DOI
Venue
2015
10.1016/j.dam.2015.12.006
Discrete Applied Mathematics
Keywords
Field
DocType
Laplacian spectrum,Product graph,Direct product,Strong product,Multilayer network
Factor graph,Adjacency list,Discrete mathematics,Laplacian matrix,Combinatorics,Open problem,Direct product,Graph product,Eigenvalues and eigenvectors,Mathematics,Laplace operator
Journal
Volume
Issue
ISSN
abs/1507.03030
C
0166-218X
Citations 
PageRank 
References 
5
0.47
6
Authors
1
Name
Order
Citations
PageRank
Hiroki Sayama131949.14