Adjacency matrix of subdivision graph.

Question

Is there a way to get from an adjacency matrix of a simple graph to an arbitrary subdivision of the graph? I believe I found a way to get from $G$ to $G^{1/2}$ using the incidence matrix, but in particular I want a way to get from $G$ to $G^{1/3}$ without needing to manually type out 1600+ entries.

Answer 1

I assume that the graphs $G$ and $G^{1/3}$ are undirected. Let $A=\|a_{ij}\|$ be an adjacency $n\times n$-matrix of the graph $G$. Let $E=\{(i,j): i<j$ and $a_{ij}=1\}$. To obtain an adjacency matrix for the graph $G^{1/3}$ we add to the matrix $A$ $2|E|$ rows and $2|E|$ columns. Each of these rows and columns is indexed by a $(i,j,t)$, where $(i,j)\in E$ and $t\in \{1,2\}$. The only non-zero elements of the extended matrix $A$ are $a_{i, (i,j,1)}$, $a_{(i,j,1),i}$, $a_{j, (i,j,2)}$, $a_{(i,j,2),j}$, $a_{(i,j,1), (i,j,2)}$, and $a_{(i,j,2), (i,j,1)}$, where $i$ ranges over $1,\dots, n$ and $(i,j)$ ranges over $E$.