We show that the graph isomorphism problem is equivalent to the problem of recognizing equal simplices in ℝn. This result can lead to new methods in the graph isomorphism problem based on geometrical properties of simplices. In particular, relations between several well-known classes of invariants of graphs and geometrical invariants of simplices are established. © Pleiades Publishing, Ltd., 2009.

Graph isomorphism and equality of simplices

Protasov, Vladimir
2009

Abstract

We show that the graph isomorphism problem is equivalent to the problem of recognizing equal simplices in ℝn. This result can lead to new methods in the graph isomorphism problem based on geometrical properties of simplices. In particular, relations between several well-known classes of invariants of graphs and geometrical invariants of simplices are established. © Pleiades Publishing, Ltd., 2009.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/123640
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact