Estimation of Laplacian spectra of direct and strong product graphs

Hiroki Sayama*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)160-170
Number of pages11
JournalDiscrete Applied Mathematics
Publication statusPublished - 2016
Externally publishedYes


  • Direct product
  • Laplacian spectrum
  • Multilayer network
  • Product graph
  • Strong product

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Estimation of Laplacian spectra of direct and strong product graphs'. Together they form a unique fingerprint.

Cite this