colored graph characteristic polynomial

Question

This was asked previously on stackexchange and it was suggested to bring it here where more specialists could see it.

Given the adjacency matrix $\mathbf{A}$ for a simple connected graph, the characteristic polynomial is defined as: $$ p(\lambda) = \det(\lambda \mathbf{I} - \mathbf{A})$$

Now if an edge between vertex $i$ and $j$ is specially "colored" / "marked" with another variable $x$, then we could consider a bivariate polynomial:

$$ f(\lambda,x) = \det(\lambda \mathbf{I} + x (\mathbf{e}_{ij}+\mathbf{e}_{ji}) - \mathbf{A})$$

where $\mathbf{e}_{ij}$ is the matrix with all entries zero except row $i$, column $j$, which is 1.

Or similarly, if the vertex $i$ was colored with the variable $x$, we could consider the polynomial:

$$ g(\lambda,x) = \det(\lambda \mathbf{I} + x \mathbf{e}_{ii} - \mathbf{A})$$

This of course could be extended to more colored / marked vertices or edges. If all vertices are "colored" with a different variable, the resulting "colored characteristic polynomial" completely determines the graph. I'm not sure what set of edges would need to be labelled to say the same. Currently though I'm mostly interested in graphs with a single marked edge or vertex, to try to better understand the basics of this generalization.

Has this generalization of a characteristic polynomial for graphs been studied before, and is there a name for these kinds of polynomials?

I'd also appreciate any insight one could share on what additional information this would provide about a graph ... as well as what information it wouldn't provide about a graph. For instance what special properties a graph would necessarily have if a single labelled edge could be added to a graph to form two non-isomorphic graphs, yet have the same "colored characteristic polynomial". Such as, $$\det(\lambda \mathbf{I} + x(\mathbf{e}_{ij}+\mathbf{e}_{ji}) - A) = \det(\lambda \mathbf{I} + x(\mathbf{e}_{mn}+\mathbf{e}_{nm}) - A)$$ where $mn$ and $ij$ are distinct edges.

Answer 1

One difficulty here is that you are asking a number of questions, none of which have short answers.

It follows from results in Chapter 5 of my "Algebraic Combinatorics" that, if you add a loop of weight $\lambda$ to a vertex $a$ in a graph $X$, the characteristic polynomial of the "looped" graph" is determined by $\phi(X,t)$, $\phi(X\setminus a,t)$ and $\lambda$. (I'm using $\phi(X,t)$ to denote the characteristic polynomial $\det(tI-A)$. Similarly, if you increase the weight of an edge joining vertices $a$ and $b$, the characteristic polynomial of the weighted graph is determined by the four polynomials $\phi(X,t)$, $\phi(X\setminus a,t)$, $\phi(X\setminus b,t)$, $\phi(X\setminus\{a,b\},t)$.

Next consider the case where $X$ is strongly regular. Then $X$ is walk regular and the characteristic polynomial of $X\setminus a$ is independent of $a$. (This can be taken as the definition of walk regular.) So the characteristic polynomial of the looped graph only depends on $\phi(X,t)$ and the loop weight.

The edge case is more complicated. The summary is that if $X$ is strongly regular then the characteristic polynomial of the weighted graph depends on $\lambda$ and on whether $a$ or $b$ are adjacent or not. Since I am not aware of a reference for this, I sketch a proof. If $B$ denotes the adjacency matrix of the complement of $X$, then there are rational functions $\alpha(t)$, $\beta(t)$, $\gamma(t)$ such that \[ (tI-A)^{-1} = \alpha(t)I + \beta(t)A +\gamma(t)B \] and these rational functions are determined by the four parameters $(n,k,a,c)$ of the strongly regular graph. Let $((tI-A)^{-1})_{D,D}$ denote the submatrix of $(tI-A)^{-1}$ with rows and columns indexed by the subset $D$ of $V(X)$. Then by a theorem of Jacobi (which appears in Chapter 5) we have \[ \det(((tI-A)^{-1})_{D,D}) = \phi(X\setminus D,t)/\phi(X,t). \] The left hand side is determined by our three rational functions and the subgraph induced by $D$. Since the rational functions are themselves determined by the parameters of the strongly graph, we deduce that $\phi(X\setminus D,t)$. (If the subgraph induced by $D$ is regular, it is only its characteristic polynomial that matters, not the graph itself.)

Answer 2

This sort of thing has been studied. In particular, the Alexander polynomial of a knot is this kind of colored determinant, for more see my paper and the papers of Stark and Terras on the Ihara zeta functions (which are, again, a form of colored characteristic polynomial).