On some properties of the Laplacian matrix revealed by the RCM algorithm

Czechoslovak Mathematical Journal

Miguel Rebollo¹  Francisco Pedroche² 

[1] Carlos Carrascosa,Alberto Palomares, Departament de Sistemes Informátics i Computació, Universitat Politècnica de València, Cam'i de Vera s/n. 46022. València, Spain;Institut de Matemàtica Multidisciplinària, Universitat Politècnica de València, Cam'i de Vera s/n. 46022. València, Spain

关键词: ordering algorithm;    reverse Cuthill-McKee algorithm;    graph partitioning;    Laplacian matrix;   

DOI  :  

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

In this paper we present some theoretical results about the irreducibility of the Laplacian matrix ordered by the Reverse Cuthill-McKee (RCM) algorithm. We consider undirected graphs with no loops consisting of some connected components. RCM is a well-known scheme for numbering the nodes of a network in such a way that the corresponding adjacency matrix has a narrow bandwidth. Inspired by some properties of the eigenvectors of a Laplacian matrix, we derive some properties based on row sums of a Laplacian matrix that was reordered by the RCM algorithm. One of the theoretical results serves as a basis for writing an easy MATLAB code to detect connected components, by using the function "symrcm" of MATLAB. Some examples illustrate the theoretical results.

【 授权许可】

Unknown