labelled graph characteristic polynomial

Question

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.

Answer 1

OK, if you wish to obtain an answer here then I confirm my above comments that your should talk with a specialist. My google search extended my knowledge of an answer not far from zero.

I didn’t find exactly the same generalization of a characteristic polynomial of a graph as you proposed but I guess there should be some of them. See, for instance a paper “A Generalization of the Characteristic Polynomial of a Graph” by Richard J. Lipton and Nisheeth K. Vishnoi.

Personally I see two natural directions in which a further generalization may be useful. The first is a problem of an isomorphism of vertex or edge colored graphs. The second is a problem of a simultaneous isomorphism of two graphs with common vertex set (If I remember it right, a corresponding problem for the similarity of pairs of matrices is so called “wild problem” and when specialists in matrices encounter an equivalent problem they said with respect: “O-o, so it is the wild problem” and stop. Here is even written (in Russian) that it is not expected to obtain a reasonable answer to such a problem).

how to go about constructing non-isomorphic graphs with matching characteristic polynomial with a single "edge label".

I suggest such graphs exist, because the quest to find two non-isomorphic graphs with matching characteristic polynomials (so called cospectral graphs) and even more additional restrictions, looks elaborated. See, for instance, the following papers:

• Anthony DiGenio “A Construction of Cospectral Graphs”.
• Haruo Hosoya, Kyoko Ohta, Masaki Satomi “Topological twin graphs II. Isospectral polyhedral graphs with nine and ten vertices”.
• M. Randić , W. R. Müller , J. V. Knop , and N. Trinajstić “The Characteristic Polynomial as a Structure Discriminator”.