Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
|
Visit for more related articles at Journal of Global Research in Computer Sciences
A sequence of nonnegative integers can represent degrees of a graph G and for the graph H. there may be many different 1-to-1 or 1-to-many mapping functions by which G can be mapped into H. That is it is feasible to construct isomorphic or regular or connected or disconnected graphs. Finding connectedness of a graph from degree sequence is analogues to Reconstruction Conjecture problem. It is our intention in this paper to infer about the connectedness of the graph only from the degree sequence and no need of any other information. It is evident that there is no unique conclusion about the connectedness of a given graph from the algorithm we project here. However, we can say that whether the sequence represents a connected or disconnected graph.
Keywords |
| Graphic Sequence, Connectedness, Regular graph, Graph Isomorphism, Reconstruction Conjecture |
INTRODUCTION |
| A sequence x = d1, d2, d3, …., dn of nonnegative integers is called a degree sequence of given graph G if the vertices of G can be labeled V1, V2, V3, …, Vn so that degree Vi = di; for all i=1,2,3,…..n [2]. For a given graph G, a degree sequence of G can be easily determined [1]. Now the question arise, given a sequence x = d1, d2, d3, …, dn of nonnegative integers, then under what conditions does there exist a graph G. A necessary and sufficient condition for a sequence to be graphical was found by Havel and later rediscovered by Hakimi [1,2]. As a sequel of this another question arises, if the sequence x = d1, d2, d3, …, dn, be a graphic sequence then is there any condition for which we can say that x represents a connected or disconnected Graph sequence[4,5,6,7,8]. |
PRELIMINARIES |
| Definition 1: A sequence x = d1, d2, d3,…, dn of nonnegative integers is said to be graphic sequence if there exists a graph G whose vertices have degree di and G is called realization of x [1]. |
| Definition 2: For any graph G, we define |
| d(G) = min{ deg(v) | v Î V(G)} and |
 |
 |
 |
 |
| A is graphic but B is not graphic. Then x can not represent any disconnected sequence. This is true for the theta graph. |
WHERE THE OWNERS PRESENTLY |
| The Reconstruction Conjecture states that every finite simple symmetric graph for three or more vertices is resolute, up to isomorphism, by its cluster of induced subgraphs [5]. The conjecture was first invented in 1941 and confers a number of associated problems. |
CONCLUSION |
| The algorithms we proposed actually identifies that the given graphic sequence represents any connected or disconnected Graph sequence or not. Any two isomorphic graphs represent the exactly same sequence. However, the converse is not true [1]. So, the proposed theorem and criterions actually determines that if the given graphic sequence is a connected sequence or disconnected sequence or at least one Graph can be possible for the sequence (which is connected or disconnected). |
References |
|