2
$\begingroup$

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}}
]

enter image description here

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!

$\endgroup$
  • $\begingroup$ Welcome to the community. You might also be interested in mathematica.se. In either case, there are useful formatting tools for typeset mathematics and code. I edited your question to make the code more accessible. Have fun! $\endgroup$ – Mark McClure Apr 29 '15 at 13:27
1
$\begingroup$

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. tensor product

$\endgroup$
  • $\begingroup$ Thank you so much, this is exactly the information I was looking for! Do you have any idea whether another type of graph product exists that would help decompose a triangular grid graph like the one I showed? $\endgroup$ – user235166 May 2 '15 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.