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.

  • 1
    $\begingroup$ 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. $\endgroup$ Aug 5 '16 at 17:05
  • $\begingroup$ @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. $\endgroup$ Aug 6 '16 at 0:21
  • $\begingroup$ 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. $\endgroup$ Aug 6 '16 at 9:19
  • 1
    $\begingroup$ 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 $\endgroup$
    – kbau
    Aug 8 '16 at 10:43
  • $\begingroup$ @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. $\endgroup$ Aug 13 '16 at 7:13

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:


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.