Umeå University's logo

umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
The thresholds for diameter 2 in random Cayley graphs
School of Computing and Mathematics, UCLan Cyprus, Pyla, Cyprus.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2014 (engelsk)Inngår i: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 45, nr 2, s. 218-235Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

Given a group G, the model G(G,p) denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. In this article we show that for any epsilon>0 and any family of groups G(k) of order n(k) for which nk, a graph kG(Gk,p) with high probability has diameter at most 2 if p(2+epsilon)lognknk and with high probability has diameter greater than 2 if p(14+epsilon)lognknk. We also provide examples of families of graphs which show that both of these results are best possible. Of particular interest is that for some families of groups, the corresponding random Cayley graphs achieve Diameter 2 significantly faster than the Erds-Renyi random graphs.

sted, utgiver, år, opplag, sider
John Wiley & Sons, 2014. Vol. 45, nr 2, s. 218-235
Emneord [en]
random graphs, Cayley graphs, diameter
HSV kategori
Identifikatorer
URN: urn:nbn:se:umu:diva-92705DOI: 10.1002/rsa.20486ISI: 000340278700003Scopus ID: 2-s2.0-84905002071OAI: oai:DiVA.org:umu-92705DiVA, id: diva2:742344
Tilgjengelig fra: 2014-09-01 Laget: 2014-09-01 Sist oppdatert: 2023-03-23bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Person

Markström, Klas

Søk i DiVA

Av forfatter/redaktør
Markström, Klas
Av organisasjonen
I samme tidsskrift
Random structures & algorithms (Print)

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 311 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf