uu.seUppsala University Publications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Random railways and cycles in random regular graphs
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics.
1998 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

In a cubic multigraph certain restrictions on the paths are made to define what is called a railway. Due to these restrictions a special kind of connectivity is defined. As the number of vertices tends to infinity, the asymptotic probability of obtaining an, in this sense, connected random cubic multigraph is shown to be 1/3.

An equivalence relation on the tracks in the railway (edges in the multigraph) is defined in order to further study the properties of railways. The number of equivalence classes induced by this relation - the connectivity number - is investigated for a random railway achieved from a random cubic multigraph.As a result we obtain the asymptotic distribution of this connectivity number.

In recent years the asymptotic distribution of Hamiltonian cycles in random r-regular graphs has been derived. As a generalization we investigate the asymptotic distribution of the number of cycles of length l in a random r-regular graph. The length of the cycles is defined as a function of the number of vertices n in the graph, thus, l = l(n), where l(n) → ∞ as n → ∞. The resulting limiting distribution turns out to depend on whether

l(n)/n → 0 or l(n)/n> → q, for 0 < q < 1.

In the first case the limit distribution is a weighted sum of Poisson variables while in the other case the limit distribution is similar to the limit distribution of Hamiltonian cycles in a random r-regular graph.

##### Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis , 1998. , p. 138
##### Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 9
##### Keyword [en]
Mathematics, Random railway, connectivity number, random regular graph, long cycles, asymptotic distribution. 1991 Mathematics Subject Classification. Primary 60F05, 60C05, 05C38, 05C80, 05C40, 05C45
MATEMATIK
Mathematics
##### Research subject
Mathematical Statistics
##### Identifiers
ISBN: 91-506-1268-9 (print)OAI: oai:DiVA.org:uu-1211DiVA, id: diva2:160768
##### Public defence
1998-05-07, Room 247, Building 2, Polacksbacken, Uppsala University, Uppsala, 10:15
Available from: 1998-04-16 Created: 1998-04-16Bibliographically approved

#### Open Access in DiVA

No full text in DiVA
##### By organisation
Department of Mathematics
Mathematics

isbn
urn-nbn

#### Altmetric score

isbn
urn-nbn
Total: 568 hits

Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf