Generating graceful unicyclic graphs from a given forest
| Autor: | V. Murugan, G. Sethuraman |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
graceful tree embedding
Conjecture Graph labeling Generalization graceful tree graceful labeling lcsh:Mathematics graph labeling Directed acyclic graph lcsh:QA1-939 Tree (graph theory) Physics::Geophysics Set (abstract data type) Combinatorics Graceful labeling Physics::Space Physics Discrete Mathematics and Combinatorics graceful unicyclic graph Connectivity Computer Science::Databases Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | AKCE International Journal of Graphs and Combinatorics, Vol 17, Iss 1, Pp 592-605 (2020) |
| ISSN: | 2543-3474 0972-8600 |
| Popis: | 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 C n with n ≡ 1 or 2(mod 4) are graceful”. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|