On some algorithmic investigations of star partitions of graphs (Q1900141)

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.