Let $\theta$ be the adjacency matrix of a simple graph (symmetric and zeros on the diagonal). What is the characterization of those $\theta$ which satisfy $$\theta^2 \equiv 0 \pmod{2}$$ i.e. which $\theta$ are nilpotent of order 2 over $\mathbb{Z}_2$?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ I assume you don't just want "those for which the number of length-2 paths between any two vertices is even". Without some clarification of what sort of answer you expect, this doesn't seem like it's research level to me. $\endgroup$– LSpiceCommented Jul 10, 2019 at 17:59
-
$\begingroup$ I expect that for matrices of this type for every row there is at least one other identical row in the matrix. $\endgroup$– MatthiasCommented Jul 10, 2019 at 20:06
-
$\begingroup$ Perhaps it is possible to count the number of such graphs, i.e., the number of $n\times n$ symmetric matrices $\theta$ over $\mathbb{F}_2$ with 0 diagonal satisfying $\theta^2=0$. The paper win.tue.nl/~aeb/preprints/countsymnilp.pdf may even have a solution, but I haven't checked carefully. In the terminology of this paper, we are interested in matrices corresponding to Young diagrams with at most two columns. $\endgroup$– Richard StanleyCommented Jul 11, 2019 at 21:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I do not think you will find a characterisation that is substantially better than the one suggested by LSpice, because this class includes other classes of graphs for which characterisations are unknown.
In particular, a $(0,2)$-graph is a graph such that each pair of distinct vertices has exactly 0 or 2 common neighbours. So if $A$ is the adjacency matrix of a $(0,2)$-graph, then every off-diagonal entry of $A^2$ is either $0$ or $2$ and hence even.
The diagonal entries of $A^2$ are the vertex degrees, and as $(0,2)$-graphs are regular, the diagonal is constant. So your class includes "even degree $(0,2)$-graphs" which are not known.
Of course there are other graphs that are not $(0,2)$-graphs that still have the nilpotent property. For example, take the prism over the complete graph of even order, i.e., the Cartesian product $K_2 \square K_r$. Then every pair of vertices in the same copy of $K_r$ are connected by $r-2$ paths of length $2$, which is even. Now consider vertices in different copies of $K_r$ — if the vertices are adjacent then there are no paths of length $2$ between them, while if the vertices are not adjacent, then there are exactly $2$ paths of length between them. In addition, these graphs do not have any twin vertices.
There may be a few more things that can be said about such graphs, but almost certainly not a complete characterisation.
answered Jul 11, 2019 at 1:19