On the Laplacian spectra of product graphs

Applicable Analysis and Discrete Mathematics

article

S. Barik¹  R. B. Bapat²  S. Pati³ 

[1] School of Basic Sciences, Indian Institute of Technology Bhubaneswar;Stat-Math Unit, Indian Statistical Institute;Department of Mathematics, Indian Institute of Technology Guwahati

关键词: Product graphs;    Laplacian matrix;    Laplacian eigenvalues;    Characteristic set;    Algebraic connectivity;   

DOI  :  10.2298/AADM150218006B

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

Graph products and their structural properties have been studied extensivelyby many researchers. We investigate the Laplacian eigenvalues and eigenvectors of the product graphs for the four standard products, namely, the Cartesian product, the direct product, the strong product and the lexicographicproduct. A complete characterization of Laplacian spectrum of the Cartesianproduct of two graphs has been done by Merris. We give an explicit complete characterization of the Laplacian spectrum of the lexicographic productof two graphs using the Laplacian spectra of the factors. For the other twoproducts, we describe the complete spectrum of the product graphs in someparticular cases. We supply some new results relating to the algebraic connectivity of the product graphs. We describe the characteristic sets for theCartesian product and for the lexicographic product of two graphs. As anapplication we construct new classes of Laplacian integral graphs.

【 授权许可】

Unknown