gráfico etiquetado polinomio característico

Question

Dada la matriz de adyacencia $\mathbf{A}$ para un gráfico conectado simple, el polinomio característico se define como $$ p(\lambda) = \det(\lambda \mathbf{I} - \mathbf{A})$$

Ahora bien, si una arista entre los vértices $i$ y $j$ está "etiquetada" con otra variable $x$ entonces podríamos considerar un polinomio bivariado:

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

donde $\mathbf{e}_{ij}$ es la matriz con todas las entradas nulas excepto la fila $i$ , columna $j$ , que es 1.

O de forma similar, si el vértice $i$ fue etiquetada con la variable $x$ podríamos considerar el polinomio:

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

Por supuesto, esto podría ampliarse a más etiquetas, pero por el momento me interesan sobre todo los gráficos con una sola etiqueta.

¿Se han estudiado antes y existe un nombre para este tipo de polinomios?

Estoy particularmente interesado en aprender acerca de los grafos simples conectados que no son isomorfos, y que tienen el mismo "polinomio característico etiquetado", pero que difieren sólo por una sola arista etiquetada como $$\det(\lambda \mathbf{I} + x(\mathbf{e}_{ij}+\mathbf{e}_{ji}) - A) = \det(\lambda \mathbf{I} + x(\mathbf{e}_{mn}+\mathbf{e}_{nm}) - A)$$ donde $mn$ y $ij$ son bordes distintos. Supongo que eso es posible dada la dificultad del isomorfismo de los grafos, pero no estoy seguro de cómo construir esos grafos.

Answer 1

De acuerdo, si desea obtener una respuesta aquí, confirmo mis comentarios anteriores de que debería hablar con un especialista. Mi búsqueda en Google amplió mi conocimiento de una respuesta no muy lejos de cero.

No he encontrado exactamente la misma generalización de un polinomio característico de un gráfico que tú propones, pero supongo que debe haber alguna. Ver, por ejemplo un artículo " Una generalización del polinomio característico de un gráfico "por Richard J. Lipton y Nisheeth K. Vishnoi.

Personalmente, veo dos direcciones naturales en las que puede ser útil una mayor generalización. La primera es un problema de un isomorfismo de grafos con vértices o aristas. La segunda es un problema de un isomorfismo simultáneo de dos grafos con un conjunto de vértices común (Si no recuerdo mal, un problema correspondiente para la similitud de pares de matrices es el llamado "problema salvaje" y cuando los especialistas en matrices se encuentran con un problema equivalente dicen con respeto: "O-o, entonces es el problema salvaje" y se detienen. Aquí incluso está escrito (en ruso) que no se espera obtener una respuesta razonable a tal problema).

cómo construir grafos no isomórficos con polinomio característico coincidente con una sola "etiqueta de arista".

Sugiero que tales grafos existen, porque la búsqueda de dos grafos no isomórficos con polinomios característicos coincidentes (los llamados gráficos cospectrales ) y aún más restricciones adicionales, parece elaborado. Véanse, por ejemplo, los siguientes documentos:

• Anthony DiGenio " Una construcción de grafos cospectrales ".
• Haruo Hosoya, Kyoko Ohta, Masaki Satomi " Grafos gemelos topológicos II. Grafos poliédricos isoespectrales con nueve y diez vértices ".
• M. Randic , W. R. Müller , J. V. Knop , y N. Trinajstic " El polinomio característico como discriminador de estructuras ".