Is the adjacency matrix of a given graph (OR any graphs isomorphic to a given graph) a Kronecker product, and if so what are the factors?

Question

I have a few triangular grid graphs that I am trying to express as the direct products of smaller graphs, if possible.

tState = Graph[UndirectedEdge @@@ {
  {1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}, {3, 6}, {4, 5}, {5, 6},
  {4, 7}, {4, 8}, {5, 8}, {5, 9}, {6, 9}, {6, 10}, {7, 8}, {8, 9}, {9, 10}}
]

Normal[AdjacencyMatrix[tState]]

(* Out: 
 {{0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, 
 {1, 0, 1, 1, 1, 0, 0, 0, 0, 0}, 
 {1, 1, 0, 0, 1, 1, 0, 0, 0, 0}, 
 {0, 1, 0, 0, 1, 0, 1, 1, 0, 0}, 
 {0, 1, 1, 1, 0, 1, 0, 1, 1, 0}, 
 {0, 0, 1, 0, 1, 0, 0, 0, 1, 1}, 
 {0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, 
 {0, 0, 0, 1, 1, 0, 1, 0, 1, 0}, 
 {0, 0, 0, 0, 1, 1, 0, 1, 0, 1}, 
 {0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}
*)

I've approached this in Mathematica by representing the graphs as their adjacency matrices and applying the KroneckerProduct function to possible factors (that I'm really just guessing at...)

The problem I'm running into is that I could tell easily if the adjacency matrix is a KroneckerProduct if it were organized differently, so it is hard to guess factors.

Does anyone have any suggestions as to how I might see all isomorphic adjacency matrices of a graph (vertex labels don't matter, I am only trying to preserve the structure) or how I could write a program in Mathematica to cycle through all possible factors (for this case it would be 0,1 5x5 matrices multiplied by 0,1 2x2 matrices to give a total of 10 vertices like in my graph), KroneckerProduct them in every combination, and then show if any of the resulting adjacency matrices are isomorphic to my graph?

(Also, I have read a bit about using permutation matrices for this purpose but am having trouble implementing that in code.)

Thanks in advance, I am new to both Mathematica and stackexchange but the community here seems very helpful!

Answer 1

Note that in the Kronecker product of graphs (also called the Tensor product), the sequence of valencies (also called degrees) of the vertices result from all of the different products of the valencies of the two graph factors.

Thus, if your graph was factorisable into a 5-vertex and 2-vertex part then it must have an even number of vertices of each valency (because all 2-vertex graphs are regular). Since your graph's valency sequence is (6,4,4,4,4,4,4,2,2,2) it cannot be factored in this way.

This idea should also give you a better idea of how to factor graphs in general, partitioning your graph into equal sized vertex sets of valencies which are in the same ratio. For instance, in this graph the valency sequence is (6,4,4,3,3,2,2,2,2,2,1,1) which can be split into (6,3,3), (4,2,2), (4,2,2) and (2,1,1), which indicates that it could come from the product of two graphs with valency sequences (3,2,2,1) and (2,1,1), which is indeed how I generated it.