Samenvatting
Let G be a graph on n vertices with adjacency matrix A, and let 1 be the all-ones vector. We call G controllable if the set of vectors 1, A1,., An-11 spans the whole space Rn. We characterize the isomorphism problem of controllable graphs in terms of other combinatorial, geometric and logical problems. We also describe a polynomial time algorithm for graph isomorphism that works for almost all graphs.
Originele taal-2 | Engels |
---|---|
Pagina's (van-tot) | 20-27 |
Aantal pagina's | 8 |
Tijdschrift | Procedia Computer Science |
Volume | 223 |
DOI's | |
Status | Gepubliceerd - 2023 |
Evenement | 12th Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2023 - Huatulco, Mexico Duur: 18 sep. 2023 → 22 sep. 2023 |
Financiering
The research of A. Abiad is partially supported by the FWO grant 1285921N. The research of O. Zapata is partially supported by the SNI grant 620178.
Financiers | Financiernummer |
---|---|
Fonds Wetenschappelijk Onderzoek | 1285921N |