On some algorithmic investigations of star partitions of graphs
type: Item
instance of: scholarly article
title: On some algorithmic investigations of star partitions of graphs
zbMATH Open document ID: 0838.05079
DOI: 10.1016/0166-218X(94)00149-8
author: P. Rowlinson
author: Dragoš Cvetković
author: Slobodan K. Simić
published in: Discrete Applied Mathematics
publication date: 1996-05-30T00:00:00Z
review text: Let \(A\) be a adjacency matrix of a given graph with vertices \(1,\dots, n\). Let \(\mu_1,\dots, \mu_m\) be the distinct eigenvalues of \(A\), with corresponding eigenspaces \(E(\mu_1),\dots, E(\mu_m)\). Let \(A= \mu_1 P_1+\cdots+ \mu_m P_m\) be the spectral decomposition of \(A\), where each \(P_i\) represents the orthogonal projection onto \(E(\mu_i)\). A partition \(X_1\dot\cup\cdots \dot\cup X_m\) of the vertex set \(\{1,\dots, n\}\) is called a star partition, if for each \(i\in \{1,\dots, m\}\), the vectors \(P_i e_j\) \((j\in X_i)\) are linearly independent, where \(\{e_1,\dots e_n\}\) is the standard basis of \(\mathbb{R}^n\). In this situation, the vectors \(P_i e_j\) \((j\in X_i)\) form a basis \(B_i\) of \(E(\mu_i)\) and \(B_1\cup \cdots \cup B_m\) is a base of \(\mathbb{R}^n\), which is called by the authors a star basis corresponding to \(A\) [Linear Algebra Appl. 182, 45-66 (1993; Zbl 0778.05057)]. In the present paper, they give a polynomial algorithm for finding a star partition.
reviewed by: Toru Ishihara
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 806411
zbMATH Keywords: vertex set
zbMATH Keywords: adjacency matrix
zbMATH Keywords: eigenvalues
zbMATH Keywords: eigenspaces
zbMATH Keywords: spectral decomposition
zbMATH Keywords: partition
zbMATH Keywords: star partition
zbMATH Keywords: star basis
zbMATH Keywords: polynomial algorithm
MaRDI profile type: Publication
cites work: TWO THEOREMS IN GRAPH THEORY
cites work: The symbiotic relationship of combinatorics and matrix theory
cites work: Recent results in the theory of graph spectra
cites work: Q3907599
cites work: A study of eigenspaces of graphs
cites work: Matroid Intersection
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Matching theory
cites work: Q4281313
cites work: Q4172091
full work available at URL: 0166-218x(94)00149-8
OpenAlex ID: W2063596425
description: scientific article; zbMATH DE number 806411