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

Title:

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

Creator:

Pedroche, Francisco, Rebollo, Miguel, Carrascosa, Carlos, and Palomares, Alberto

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:ad70e796-19a8-452a-8bd5-5c61bb52b7ff
uuid:ad70e796-19a8-452a-8bd5-5c61bb52b7ff
issn:0011-4642

Subject:

matematika, mathematics, ordering algorithm, reverse Cuthill-McKee algorithm, graph partitioning, Laplacian matrix, 13, and 51

Type:

model:article and TEXT

Format:

print, bez média, and svazek

Description:

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., Francisco Pedroche, Miguel Rebollo, Carlos Carrascosa, Alberto Palomares., and Obsahuje seznam literatury

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

603-620

Source:

Czechoslovak Mathematical Journal | 2016 Volume:66 | Number:3

Harvested from:

CDK

Metadata only:

false