Open Access
Issue
Wuhan Univ. J. Nat. Sci.
Volume 27, Number 3, June 2022
Page(s) 185 - 188
DOI https://doi.org/10.1051/wujns/2022273185
Published online 24 August 2022

© Wuhan University 2022

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

0 Introduction

Research on labeling of graceful graph is on the rise following the process of computing science[1-7]. Researches on the gracefulness of fan graph, especially double fan graph, are very important for the study of graph[8]. The gracefulness of union graphs of double fan graph, linear graph and star graph has been proved[9], and the gracefulness of union graphs of double fan graph and all graceful graphs has also been proved[10]. The gracefulness of union graphs of fan graph and non-graceful graphs has rarely been studied, thus it is rather significant to have further research on the gracefulness of fan graph and non-graceful graphs.

The graphs in the following are all simple undirected graphs. Let be a graph, be the set of vertices of graph G, be the set of edges of graph G, be the order of the set A, be the path with n vertices, be the trivial graph with one vertex, be the joint graph of and , be the complementary graph of G.

Definition 1   Let be a graph, and let k be a positive integer. If there is a injection :{ }, such that for every edge induces a bijection { }, then we call a k-graceful graph, call f a k-graceful label of graph . 1-graceful graph is also called graceful graph, and 1-graceful label is called graceful label.

1 The Gracefulness of Graph

Theorem 1   For natural number , , is a graceful graph.

Proof   For {},,, ,,, , then , .

Define the vertex label f of graph as follows:

We shall prove that label f is a graceful label of graph .

(ⅰ) By the definition of f :

Hence mapping : {}is an injection.

(ⅱ) For every edge , let .

Then

Hence

Hence

: {} is a bijection, graph is a graceful graph.

2 The Gracefulness of Graph

Theorem 2   For natural number , , is a graceful graph.

Proof   For {},,

, then .

Define the vertex label f of graph as follows:

We shall prove that label f is a graceful label of graph .

(ⅰ) By the definition of f :

Hence mapping :{}}is an injection.

(ⅱ) Let

Hence

Hence

is a bijection, and graph is a graceful graph.

3 Conclusion

The gracefulness on two kinds of unconnected double fan graphs with even vertices, and , were proved. The vertex label f of graph was defined by the definition of graceful graph, and f was proved as injection/bijection. The graceful theorem of the union of unconnected triple graphs was proved. The research will be beneficial to the study of gracefulness on union graph of multiple graphs.

References

  1. Acharya B D, Heged S M. Arithmetic graph [J]. J Theory, 1990, 14(3): 275-299. [Google Scholar]
  2. Gardner M. Mathematical games [J]. Scientific American, 1970, 222(1): 124-127. [CrossRef] [Google Scholar]
  3. Eckler A R. The construction of Missile guidance codes resistant to random interference [J]. Bell Syst Technical J, 1960, 39(4):973-994. [CrossRef] [Google Scholar]
  4. Golomb S W. How to Number a Graph, Graph Theory and Computing [M]. New York: Academic Press, 1972: 23-37. [CrossRef] [Google Scholar]
  5. Pan W, Lu X. The gracefulness of two kinds of unconnected graphs Formula and Formula [J]. Journal of Jilin University (Science Edition), 2003, 41(2): 152-154 (Ch). [Google Scholar]
  6. Basher M. Odd-even graceful labeling of planar grid and prism graphs[J]. Journal of Information and Optimization Sciences, 2021, 42(4) :747-751. [CrossRef] [Google Scholar]
  7. Pereira J, Singh T, Arumugam S. Edge consecutive gracefulness of a graph[J]. Discrete Applied Mathematics, 2020, 280: 214-220. [CrossRef] [MathSciNet] [Google Scholar]
  8. Liu J B, Pan X F. The gracefulness of wheels and fans [J]. Journal of Anhui University (Natural Science Edition), 2009, 33(4): 11-139 (Ch). [Google Scholar]
  9. Sun C Y, Wang T. The gracefulness of unconnected graphs Formula and Formula [J]. ACTA Scientiarum Naturalium Universitatis Sun Yatseni, 2014, 53(3): 52-56 (Ch). [Google Scholar]
  10. Wang T. The Graceful Graph[M]. Beijing: Tsinghua University Press, 2016: 71-109 (Ch). [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.