Quantum compact graphs

Autores/as

  • Thiago Assis Universidade Federal de Minas Gerais
  • Pedro Baptista Universidade Federal de Minas Gerais
  • Gabriel Coutinho Universidade Federal de Minas Gerais
  • Chris Godsil University of Waterloo

Palabras clave:

Quantum Isomorphism, Compact Graphs, Automorphism Group, Quantum Automorphism

Resumen

One of the main topics of research on graphs is its automorphism group Aut(G). Although it is known that most graphs have a trivial automorphism group, it is not yet known if the problem of deciding for a given graph G if it has a trivial Aut(G) is in P or is NP-complete. Elements of Aut(G) can be viewed as permutation matrices P such that PA(G) = A(G)P, where A(G) is the adjacency matrix of the graph. This paper introduces the concept of quantum compact graphs, a novel generalization of compact graphs, and explores their properties and implications.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

A. Atserias, L. Mančinska, D. E. Roberson, R. Šámal, S. Severini, and A. Varvitsiotis. “Quantum and non-signalling graph isomorphisms”. In: Journal of Combinatorial Theory, Series B 136 (2019), pp. 289–328. issn: 0095-8956. doi: 10.1016/j.jctb.2018.11.002.

P. Erdős and A. Rényi. “Asymmetric graphs”. In: Acta Mathematica Academiae Scientiarum Hungaricae 14 (3-4 1963), pp. 295–315. issn: 15882632. doi: 10.1007/BF01895716/METRICS.

C.D. Godsil. “Compact graphs and equitable partitions”. In: Linear Algebra and its Applications 255.1 (1997), pp. 259–266. issn: 0024-3795. doi: 10.1016/S0024-3795(97)83595-1.

S. Schmidt. “Quantum automorphism groups of finite graphs”. PhD thesis. Fakultät für Mathematik und Informatik/Universität des Saarlandes, 2020. doi: http://dx.doi.org/10.22028/D291-31806.

G. Tinhofer. “A note on compact graphs”. In: Discrete Applied Mathematics 30.2 (1991), pp. 253–264. issn: 0166-218X. doi: 10.1016/0166-218X(91)90049-3.

G. Tinhofer. “Graph isomorphism and theorems of Birkhoff type”. In: Computing 36 (4 Dec. 1986), pp. 285–300. issn: 0010485X. doi: 10.1007/BF02240204/METRICS.

Descargas

Publicado

2025-01-20

Número

Sección

Resumos