0

Let $R^V$ be the real vector space of all functions from $V(G)$ to $R$ and $A(G)$ is the adjacency matrix, while $Q(G):=D(G)+A(G)$ is the signless laplacian matrix. A characteristics function of a subset $U\subset V$ is denoted by $e_U$. As it is well known that if $\pi:=\{V_1,V_2\}$ be an equitable partition of a connected graph $G$ if and only if two dimensional vector space $<e_{V_1},e_{V_2}>\subset R^V$ is $A(G)-$invariant. Also if $\pi$ is an equitable partition then a vector subspace $<e_{V_1},e_{V_2}>^{\perp}$ is $A(G)-$invariant subspace of $R^V$.

So my question, Is this two-dimensional vector subspace is also $Q(G)-$invariant? and its orthogonal complement vector subspace is $Q(G)-$invariant? is the linearity of $Q(G)$ is sufficient to say that they are $Q(G)-$invariant. Secondly, can we generalize this concept for $aD(G)+bA(G)$ matrix of any connected graph?

محمد عتیق طا ہر
  • 13

1 Answers1

1

For this stuff, I prefer to think of the adjacency matrix as an operator of tne vector space $\mathbb{R}^{V(G)}$ of real functions on $V(G)$. If $\pi$ is a partition of $V(G)$, then the functions constant on the cells of $\pi$ form subspace $F(\pi)$ of $\mathbb{R}^{V(ZG)}$. (Such a subspace is closed under Schur multiplication and contains the all-one vector.)

The partition $\pi$ is equitable if and only if $F(\pi)$ is $A$-invariant. More generally, if $S$ is a set of matrices we can say $\pi$ is equitable relative to $S$ if $F(\pi)$ is $S$-invariant.

So now suppose $\pi$ is equitable relative to $A$. Then each cell of $\pi$ induces a regular subgraph of $G$, and to $\pi$ is a refinement of the degree partition of $V(G)$. It follows that $F(\pi)$ is $D$-invariant, and consequently $F(\pi)$ is closed under any matrix in the algebra generated by $A$ and $D$. In particular it is invariant relative to the unsigned Laplacian $A+D$.

If $F(\pi)$ is $Q$-invariant then since the all-ones vector $\textbf1$ lies in $F(\pi)$ and $(A+D)\textbf{1}=2\textbf{1}$ and since $F(\pi)$ is Schur-closed, it follows that $F(\pi)$ is $D$. Thus "$Q$-equitable" implies "$A$-equitable". (This may not have been noticed before.)

Remark: the underlying theory appears in an old paper of mine "Equitable Partions" MR1249711.

Chris Godsil
  • 13,703