Header menu link for other important links
Generating graceful unicyclic graphs from a given forest
G. Sethuraman,
Published in Taylor and Francis Ltd.
Volume: 17
Issue: 1
Pages: 592 - 605
Acharya (1982) proved that every connected graph can be embedded in a graceful graph. The generalization of this result that, any set of graphs can be packed into a graceful graph was proved by Sethuraman and Elumalai (2005). Recently, Sethuraman et al. (2016) have shown that, every tree can be embedded in an graceful tree. Inspired by these fundamental structural properties of graceful graphs, in this paper, we prove that any acyclic graph can be embedded in an unicyclic graceful graph. This result is proved algorithmically by constructing graceful unicyclic graphs from a given acyclic graph. Our result strongly supports the Truszczynski’s Conjecture that “All unicyclic graphs except the cycle (Formula presented.) with (Formula presented.) or 2(mod 4) are graceful”. © 2018 Kalasalingam University. Published with license by Taylor & Francis Group, LLC.
About the journal
JournalData powered by TypesetAKCE International Journal of Graphs and Combinatorics
PublisherData powered by TypesetTaylor and Francis Ltd.