# labelled graph characteristic polynomial

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 "labelled" 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 labelled 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 labels, but I'm mostly interested in graphs with a single label at the moment.

Have these been studied before, and is there a name for these kinds of polynomials?

I'm particularly interested in learning about simple connected graphs which are non-isomorphic, and have the same "labelled characteristic polynomial", but differ only by a single labelled edge like $$\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. I'm assuming that is possible given the difficulty of graph isomorphism, but I'm not sure how to go about constructing such graphs.

• I recommend you to ask this question at MathOverflow (MO), because it seems too specific for MSE and also chances to obtain a qualified answer look better at MO. Aug 5 '16 at 17:05
• @AlexRavsky I don't really understand the relation between the two sites. I kind of got the impression that MO was for serious researchers. I dont even have a math degree. I'm just curious about math. Aug 6 '16 at 0:21
• Yes, you are right, but your question is specific. For instance, I have a math degree and wrote some papers in graph theory, but I don't know an answer to your question. Aug 6 '16 at 9:19
• Did you ask this on MO then? I'm interested too! Also, I haven't had time to properly look at it, but a lot on graph labelling in here (and a tremendous compilation of references): combinatorics.org/ojs/index.php/eljc/article/viewFile/DS6/pdf
– kbau
Aug 8 '16 at 10:43
• @kbau I finally asked on MO mathoverflow.net/questions/247416/… I'm still digesting the references Alex gave, but based on his answer I think I should have said "color" instead of "label" a vertex/edge. Aug 13 '16 at 7:13