International Journal of Advanced Networking and Applications

Open Access Open Access  Restricted Access Subscription Access

Finding All Graphic Sequences and Generating Random Graphs


Affiliations
1 Indore Institute of Science and Technology, Indore - 453331, India
 

Graphs are basic requirement of research in many fields like electrical circuits, computer networks, Genome sequencing, traffic flow, compiler design and cryptography to name a few. There are three fundamental issues one has to address in respect of an undirected graph. First, given a number of nodes, how many unique degree sequences can be there to handle? Second, out of these unique degree sequences, how many are graphic? And third, how to generate random graphs for a degree sequence? This paper presents working solutions for all these issues. An efficient algorithm to find all unique degree sequences for a given number of nodes is presented. An algorithm based on Havel-Kasami algorithm is presented which is more efficient than Erdos-Gallai algorithm to test the connectivity. Finally, an algorithm to generate random graphs is also presented.

Keywords

Adjacency List, Connected Graph, Degree Sequence, Erdos-Gallai, Havel-Kasami.
User
Notifications
Font Size

  • N. Deo, Graph Theory with Applications to Engineering and Computer Science (New Delhi: Prentice-Hall of India, 1974).

  • F. Harary, Graph Theory (New Delhi: Narosa Publishing House, 1987).

  • S. A. Choudham, A First Course in Graph Theory (Madras: MacMillan India, 1987).

  • P. Erdos and T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lapok, 11, 1960, 264-274.

  • A. Tripathi and H. Tyagi, A simple criterion on degrees of vertices, Discrete Applied Mathematics, 156, 2008, 3516-3517.

  • A. Tripathi, S. Venugopalan, and D. B. West, A short constructive proof of the Erdos-Gallai characterization of graphic lists, Discrete Mathematics, 310, 2010, 843-844.

  • V. Havel, A remark on existence of finite graphs, Casopis propestovani matematiky (in Czech), 80, 1955, 477-480.1962, 496-506.

  • S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph, SIAM Journal on Applied Mathematics, 10, 1962, 496-506.

  • B. K. Joshi, Digit and Vector classes for graph applications, unpublished.


Abstract Views: 94

PDF Views: 0




  • Finding All Graphic Sequences and Generating Random Graphs

Abstract Views: 94  |  PDF Views: 0

Authors

Brijendra Kumar Joshi
Indore Institute of Science and Technology, Indore - 453331, India

Abstract


Graphs are basic requirement of research in many fields like electrical circuits, computer networks, Genome sequencing, traffic flow, compiler design and cryptography to name a few. There are three fundamental issues one has to address in respect of an undirected graph. First, given a number of nodes, how many unique degree sequences can be there to handle? Second, out of these unique degree sequences, how many are graphic? And third, how to generate random graphs for a degree sequence? This paper presents working solutions for all these issues. An efficient algorithm to find all unique degree sequences for a given number of nodes is presented. An algorithm based on Havel-Kasami algorithm is presented which is more efficient than Erdos-Gallai algorithm to test the connectivity. Finally, an algorithm to generate random graphs is also presented.

Keywords


Adjacency List, Connected Graph, Degree Sequence, Erdos-Gallai, Havel-Kasami.

References