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 dans 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
Mots-clés : 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 = {https://geodesic-test.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  - https://geodesic-test.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 https://geodesic-test.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. https://geodesic-test.mathdoc.fr/articles/10.1007/s10587-016-0281-y/

Cité par Sources :