Degree sequence of configuration model with vertex faults

Yilun Shang
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 17, 2011, Number 4, Pages 14–17
Full paper (PDF, 166 Kb)

Details

Authors and affiliations

Yilun Shang
¹ Department of Mathematics, Shanghai Jiao Tong University
Shanghai 200240, China
² Institute for Cyber Security, University of Texas at San Antonio
San Antonio, Texas 78249, USA

Abstract

We study the degree sequence of configuration model of random graphs with random vertex deletion. The degree sequences are characterized under various deletion probabilities. Our results have implications in communication networks where random faults due to inner consumption and outer disturbance often occur.

Keywords

• Configuration model
• Random graph
• Degree sequence
• Faulty graph

AMS Classification

• 05C80

References

1. Bollobás, B. Random Graphs. Cambridge University Press, Cambridge, 2001.
2. Chung, F., L. Lu. Complex Graphs and Networks. AMS Publications, 2006.
3. Greenhill, C., F. B. Holt, N.Wormald. Expansion properties of a random regular graph after random vertex deletions. European J. Combin., Vol. 29, 2008, 1139–1150.
4. Janson, S., T. Łuczak, A. Ruciński. Random Graphs. Wiley, New York, 2000.
5. Paradis, L., Q. Han. A survey of fault management in wireless sensor networks. J. Netw. Syst. Manag., Vol. 15, 2007, 171–190.
6. Shang, Y. Focusing of maximum vertex degrees in random faulty scaled sector graphs. arXiv:0909.2933v1.
7. Van der Hofstad, R. Random Graphs and Complex Networks. Book in preparation, 2009. http://www.win.tue.nl/~rhofstad/NotesRGCN2009.pdf