Rikio Ichishima, Francesc-Antoni Muntaner-Batle, Akito Oshima, Yukio Takahashi: On certain labelings of disjoint unions of cycles and stars, 199-217

Abstract:

First, an edge-magic labeling of a graph $G$ is defined to be a bijective function $f:V\left(G\right) \cup E\left(G\right)\rightarrow \left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert +\left\vert E\left( G\right) \right\vert \right\}$ such that $f\left(u\right) + f\left(v\right) + f\left(uv\right)$ is a constant for each $uv\in E\left( G\right)$. Also, an edge-magic labeling $f$ of $G$ with the additional property that $f\left(V \left(G\right)\right) =\left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert \right\}$ is called a super edge-magic labeling. In this paper, we investigate the (super) edge-magic properties of disjoint unions of cycles and stars. The super edge-magic results obtained in this paper yield felicitous labelings for the same class of graphs. We also propose a conjecture and several open problems arising from this study. Furthermore, we settle an old problem proposed by Wallis in his book “Magic Graphs”.

Key Words: (Super) edge-magic graph (labeling), consecutively super edge-magic graph (labeling), felicitous graph (labeling), cycle, path, star, graph labeling.

2020 Mathematics Subject Classification: Primary 05C78 ; Secondary 05C35, 05C76, 90C35.

Download the paper in pdf format here.