Quantum compact graphs
Keywords:
Quantum Isomorphism, Compact Graphs, Automorphism Group, Quantum AutomorphismAbstract
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.
Downloads
References
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.
