Random railways and cycles in random regular graphs
1998 (English)Doctoral thesis, comprehensive summary (Other academic)
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
Mathematics, Random railway, connectivity number, random regular graph, long cycles, asymptotic distribution. 1991 Mathematics Subject Classification. Primary
60F05, 60C05, 05C38, 05C80, 05C40, 05C45
Research subject Mathematical Statistics
IdentifiersURN: urn:nbn:se:uu:diva-1211ISBN: 91-506-1268-9OAI: oai:DiVA.org:uu-1211DiVA: diva2:160768
1998-05-07, Room 247, Building 2, Polacksbacken, Uppsala University, Uppsala, 10:15