Reading: Reconstruction of helm graph and web graph

Download

A- A+
Alt. Display

Articles

Reconstruction of helm graph and web graph

Authors:

K. M. P. G. S. C. Kapuhennayake ,

University of Peradeniya, LK
About K. M. P. G. S. C.
Department of Mathematics, Faculty of Science
X close

A. C. G. Perera,

The Open University of Sri Lanka, LK
About A. C. G.
Faculty of Engineering Technology
X close

K. D. E. Dhananjaya,

University of Peradeniya, LK
About K. D. E.
Department of Mathematics, Faculty of Science
X close

A. A. I. Perera

University of Peradeniya, LK
About A. A. I.
Department of Mathematics, Faculty of Science
X close

Abstract

The graph reconstruction conjecture asserts that every simple undirected graph with number of vertices (where n ≥ 3) is uniquely determined up to isomorphism, by its collection of unlabeled form of vertex deleted sub graphs. If a vertex deleted sub graph of G is given in unlabeled form, then it is called a “card” of G. The collection of all cards of G is called the “deck” of G, and is denoted by D(G) . If we can determine the original graph G from the deck of the graph G, we can say that it is reconstructible. In this paper we propose a new method to reconstruct the helm graph (Hn) and the web graph (Wn), by using the degree sequence of its collection of vertex deleted sub graphs. Helm graph is obtained by adjoining a pendant edge to each node of the cycle of the -wheel graph. Web graph is obtained by joining pendant vertices to the vertices in the outer cycle of the helm graph to form a cycle and again adding pendant vertices to the new cycle. For both graphs we found decks and obtained the degree sequence of each cards. Finally, we reconstructed the original graph using the degree sequences.
DOI: https://doi.org/10.4038/jsc.v13i1.41
How to Cite: Kapuhennayake, K.M.P.G.S.C., Perera, A.C.G., Dhananjaya, K.D.E. and Perera, A.A.I., 2022. Reconstruction of helm graph and web graph. Journal of Science, 13(1), pp.31–39. DOI: http://doi.org/10.4038/jsc.v13i1.41
9
Views
7
Downloads
Published on 28 Nov 2022.
Peer Reviewed

Downloads

  • PDF (EN)

    comments powered by Disqus