Conta sullo spanning tree con G e il suo grafo complementare G '

Question

Ho un problema davvero difficile che ci sono grafi G (G non è un grafo auto-complementare) che ha lo stesso conteggio di spanning tree con il suo complemento albero G '?

Ho provato più metodi per ottenere il risultato ma non ho ottenuto nulla.

Ho provato a utilizzare Java per generare tutti i grafici e ottenere il suo grafico di complemento e confrontare i loro conteggi di spanning tree. È invecchiato in modo che l'ho interrotto durante la generazione di grafici di ordine 10. Cioè, ora so che non esiste con i grafici che hanno meno di 10 vertici. Ho provato a utilizzare la matrice dei gradi di G per mostrare se può o non può esserci lo stesso co-fattore con una matrice grafica con la sua matrice del grafo del complemento, ma poiché il calcolo era basato sulle matrici, non ho ottenuto un risultato ragionevole che può provare qualsiasi cosa. Quindi, ci sono grafici che hanno lo stesso numero di spanning tree con il suo grafo complementare e perché?

Grazie!

Answer 1

Ci sono tali grafici. Infatti, ci sono infiniti grafi non autocomplementari che hanno lo stesso polinomio di Tutte come complemento; guarda questo post di mathoverflow . Poiché il polinomio di Tutte codifica il numero di foreste che si estendono su un grafo (cioè se$T_G$ è il polinomio di Tutte di $G$, $T_G(1,1)$ è il numero di foreste che si estendono), questo risponde affermativamente alla tua domanda.

Bene, tranne che stavi chiedendo di superare gli alberi e sto parlando di attraversare le foreste . Ma a una rapida occhiata sembra che la costruzione citata nel collegamento fornisca grafici connessi con complementi collegati, nel qual caso le due nozioni sono le stesse.