On the largest strong components in m-out digraphs

W.C.Stephen Suen

doi:10.1016/0012-365X(91)90305-L

On the largest strong components in m-out digraphs

W.C.Stephen Suen

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

1 Citation (Scopus)

Abstract

A digraph is m-out if every vertex in the digraph has an outdegree equal to m. For n > m ≥ 2, we consider the m-out digraph D(m, n) obtain by randomly choosing a digraph from the set of all m-out digraphs with n vertices. We show by using a constructive method that for any fixed m ≥ 2, almost every D(m, n) contains a unique largest strongly connected subgraph and that if N(m, n) is the number of vertices in this subgraph, then n^-1N(m, n) converges in probability to (1- y(m)) where y(m) is the smallest root of y = e^m(y-1). © 1991.

Original language	English
Pages (from-to)	45-52
Journal	Discrete Mathematics
Volume	94
Issue number	1
DOIs	https://doi.org/10.1016/0012-365X(91)90305-L
Publication status	Published - 27 Nov 1991
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

Most of the results appeared in this paper were obtained while the author was a postgraduate student at the University of Bristol, England. The author would like to thank the University for a scholarship award which made this work possible. The author would also like to thank Dr G.R. Grimmett for his supervision.

Access Output

10.1016/0012-365X(91)90305-LLicence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{41a9cad28b7b4d7c9c2d4f65f1c63ec7,

title = "On the largest strong components in m-out digraphs",

abstract = "A digraph is m-out if every vertex in the digraph has an outdegree equal to m. For n > m ≥ 2, we consider the m-out digraph D(m, n) obtain by randomly choosing a digraph from the set of all m-out digraphs with n vertices. We show by using a constructive method that for any fixed m ≥ 2, almost every D(m, n) contains a unique largest strongly connected subgraph and that if N(m, n) is the number of vertices in this subgraph, then n-1N(m, n) converges in probability to (1- y(m)) where y(m) is the smallest root of y = em(y-1). {\textcopyright} 1991.",

author = "W.C.Stephen Suen",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1991",

month = nov,

day = "27",

doi = "10.1016/0012-365X(91)90305-L",

language = "English",

volume = "94",

pages = "45--52",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - On the largest strong components in m-out digraphs

AU - Suen, W.C.Stephen

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1991/11/27

Y1 - 1991/11/27

N2 - A digraph is m-out if every vertex in the digraph has an outdegree equal to m. For n > m ≥ 2, we consider the m-out digraph D(m, n) obtain by randomly choosing a digraph from the set of all m-out digraphs with n vertices. We show by using a constructive method that for any fixed m ≥ 2, almost every D(m, n) contains a unique largest strongly connected subgraph and that if N(m, n) is the number of vertices in this subgraph, then n-1N(m, n) converges in probability to (1- y(m)) where y(m) is the smallest root of y = em(y-1). © 1991.

AB - A digraph is m-out if every vertex in the digraph has an outdegree equal to m. For n > m ≥ 2, we consider the m-out digraph D(m, n) obtain by randomly choosing a digraph from the set of all m-out digraphs with n vertices. We show by using a constructive method that for any fixed m ≥ 2, almost every D(m, n) contains a unique largest strongly connected subgraph and that if N(m, n) is the number of vertices in this subgraph, then n-1N(m, n) converges in probability to (1- y(m)) where y(m) is the smallest root of y = em(y-1). © 1991.

UR - https://www.scopus.com/pages/publications/44949274525

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-44949274525&origin=recordpage

U2 - 10.1016/0012-365X(91)90305-L

DO - 10.1016/0012-365X(91)90305-L

M3 - RGC 21 - Publication in refereed journal

SN - 0012-365X

VL - 94

SP - 45

EP - 52

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -

On the largest strong components in m-out digraphs

Abstract

Bibliographical note

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this