Geodesic
On some properties of the Laplacian matrix revealed by the RCM algorithm
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 603-620

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
DOI : 10.1007/s10587-016-0281-y
Classification : 05C50, 15B36
Keywords: ordering algorithm; reverse Cuthill-McKee algorithm; graph partitioning; Laplacian matrix 
@article{10_1007_s10587_016_0281_y,
     author = {Pedroche, Francisco and Rebollo, Miguel and Carrascosa, Carlos and Palomares, Alberto},
     title = {On some properties of the {Laplacian} matrix revealed by the {RCM} algorithm},
     journal = {Czechoslovak Mathematical Journal},
     pages = {603--620},
     publisher = {mathdoc},
     volume = {66},
     number = {3},
     year = {2016},
     doi = {10.1007/s10587-016-0281-y},
     mrnumber = {3556856},
     zbl = {06644022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0281-y/}
}
TY  - JOUR
AU  - Pedroche, Francisco
AU  - Rebollo, Miguel
AU  - Carrascosa, Carlos
AU  - Palomares, Alberto
TI  - On some properties of the Laplacian matrix revealed by the RCM algorithm
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 603
EP  - 620
VL  - 66
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0281-y/
DO  - 10.1007/s10587-016-0281-y
LA  - en
ID  - 10_1007_s10587_016_0281_y
ER  - 
%0 Journal Article
%A Pedroche, Francisco
%A Rebollo, Miguel
%A Carrascosa, Carlos
%A Palomares, Alberto
%T On some properties of the Laplacian matrix revealed by the RCM algorithm
%J Czechoslovak Mathematical Journal
%D 2016
%P 603-620
%V 66
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0281-y/
%R 10.1007/s10587-016-0281-y
%G en
%F 10_1007_s10587_016_0281_y
Pedroche, Francisco; Rebollo, Miguel; Carrascosa, Carlos; Palomares, Alberto. On some properties of the Laplacian matrix revealed by the RCM algorithm. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 603-620. doi: 10.1007/s10587-016-0281-y

Cité par Sources :