Geodesic
Graph Isomorphism and Equality of Simplices
Matematičeskie zametki, Tome 85 (2009) no. 5, pp. 758-767 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We show that the graph isomorphism problem is equivalent to the problem of recognizing equal simplices in $\mathbb R^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.
Mots-clés : graph isomorphism, graph invariants, simplex invariants.
Keywords: graph recognition 
@article{MZM_2009_85_5_a11,
     author = {V. Yu. Protasov},
     title = {Graph {Isomorphism} and {Equality} of {Simplices}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {758--767},
     year = {2009},
     volume = {85},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2009_85_5_a11/}
}
TY  - JOUR
AU  - V. Yu. Protasov
TI  - Graph Isomorphism and Equality of Simplices
JO  - Matematičeskie zametki
PY  - 2009
SP  - 758
EP  - 767
VL  - 85
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/MZM_2009_85_5_a11/
LA  - ru
ID  - MZM_2009_85_5_a11
ER  - 
%0 Journal Article
%A V. Yu. Protasov
%T Graph Isomorphism and Equality of Simplices
%J Matematičeskie zametki
%D 2009
%P 758-767
%V 85
%N 5
%U http://geodesic.mathdoc.fr/item/MZM_2009_85_5_a11/
%G ru
%F MZM_2009_85_5_a11
V. Yu. Protasov. Graph Isomorphism and Equality of Simplices. Matematičeskie zametki, Tome 85 (2009) no. 5, pp. 758-767. http://geodesic.mathdoc.fr/item/MZM_2009_85_5_a11/

[1] V. N. Zemlyachenko, N. M. Korneenko, R. I. Tyshkevich, “Problema izomorfizma grafov”, Teoriya slozhnosti vychislenii. I, Zap. nauchn. sem. LOMI, 118, Izd-vo «Nauka», Leningrad. otd., L., 1982, 83–158 | MR | Zbl

[2] J. Köbler, U. Schöning, J. Torán, The Graph Isomorphism Problem: Its Stuctural Complexity, Progr. Theoret. Comput. Sci., Birkhäuser Boston, Boston, MA, 1993 | MR | Zbl

[3] D. M. Cvetković, M. Doob, H. Sachs, Spectra of Graphs. Theory and Application, Pure Appl. Math., 87, Academic Press, New York–London, 1980 | MR | Zbl

[4] D. Cvetković, P. Rowlinson, S. Simić, Eigenspaces of Graphs, Encyclopedia Math. Appl., 66, Cambridge Univ. Press, Cambridge, 1997 | MR | Zbl

[5] C. R. Johnson, M. Newman, “A note on cospectral graphs”, J. Combin. Theory Ser. B, 28:1 (1980), 96–103 | DOI | MR | Zbl

[6] F. John, “Extremum problems with inequalities as subsidiary conditions”, Studies and Essays Presented to R. Courant on his 60th Birthday, Intersci. Publ., New York, 1948, 187–204 | MR | Zbl

[7] S. P. Tarasov, L. G. Khachiyan, I. I. Erlikh, “Metod vpisannykh ellipsoidov”, Dokl. AN SSSR, 298:5 (1988), 1081–1085 | MR | Zbl

[8] C. D. Godsil, B. D. McKay, “Spectral conditions for reconstuctibility of a graph”, J. Combin. Theory Ser. B, 30:3 (1981), 285–289 | DOI | MR | Zbl