uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
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. , 138 p.
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
Keyword [sv]
National Category
Research subject
Mathematical Statistics
URN: urn:nbn:se:uu:diva-1211ISBN: 91-506-1268-9OAI: oai:DiVA.org:uu-1211DiVA: 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

By organisation
Department of Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 224 hits
ReferencesLink to record
Permanent link

Direct link