In this paper we show that two distinct conjectures, the first proposed by Babai and Godsil in 1982 and the second proposed by Xu in 1998, concerning the asymptotic enumeration of Cayley graphs are in fact equivalent. This result follows from a more general theorem concerning the asymptotic enumeration of a certain family of Cayley graphs.

Spiga, P. (2021). On the equivalence between a conjecture of Babai-Godsil and a conjecture of Xu concerning the enumeration of Cayley graphs. THE ART OF DISCRETE AND APPLIED MATHEMATICS, 4(1), 1-10 [10.26493/2590-9770.1338.0b2].

On the equivalence between a conjecture of Babai-Godsil and a conjecture of Xu concerning the enumeration of Cayley graphs

Spiga P.
Primo
2021

Abstract

In this paper we show that two distinct conjectures, the first proposed by Babai and Godsil in 1982 and the second proposed by Xu in 1998, concerning the asymptotic enumeration of Cayley graphs are in fact equivalent. This result follows from a more general theorem concerning the asymptotic enumeration of a certain family of Cayley graphs.
Articolo in rivista - Articolo scientifico
asymptotic enumeration; automorphism group; Babai-Godsil conjecture; Cayley graph; graphical regular representation; GRR; normal Cayley graph; Regular representation; Xu conjecture;
English
2021
4
1
1
10
#P1.10
open
Spiga, P. (2021). On the equivalence between a conjecture of Babai-Godsil and a conjecture of Xu concerning the enumeration of Cayley graphs. THE ART OF DISCRETE AND APPLIED MATHEMATICS, 4(1), 1-10 [10.26493/2590-9770.1338.0b2].
File in questo prodotto:
File Dimensione Formato  
Spiga-2022-Art Discrete Appl Math-preprint.pdf

accesso aperto

Descrizione: Article
Tipologia di allegato: Submitted Version (Pre-print)
Licenza: Creative Commons
Dimensione 185.91 kB
Formato Adobe PDF
185.91 kB Adobe PDF Visualizza/Apri

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: https://hdl.handle.net/10281/415912
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
Social impact