Abstrakt

Connectedness of a Graph from its Degree Sequence and it is Relevent with Reconstruction Conjecture

Saptarshi Naskar, Krishnendu Basuli, Samar Sen Sarma

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.