Article

On the super edge-magicness of graphs with a specificdegree sequence
Rikio Ichishima1,∗ , Francesc-Antoni Muntaner-Batle2
12*Department of Sport and Physical Education, Faculty of Physical Education, Kokushikan University, 7-3-1
Nagayama, Tama-shi, Tokyo 206-8515, Japan.; ichishim@kokushikan.ac.jp
Graph Theory and Applications Research Group, School of Electrical Engineering and Computer Science, Faculty ofEngineering and Built Environment, The University of Newcastle, NSW 2308 Australia.; famb1es@yahoo.es
Correspondence: ichishim@kokushikan.ac.jp; Tel. +81-42-339-7210

Communicated by: Muhammad Kamran Jamil
Received: 14 August 2023; Accepted: 26 September 2023; Published: 25 December 2023

Abstract: A graph G is said to be super edge-magic if there exists a bijective function f ∶ V (G) ∪ E (G) →{1, 2, . . . , ∣V (G)∣ + ∣E (G)∣} such that f (V (G)) = {1, 2, . . . , ∣V (G)∣} and f (u) + f (v) + f (uv) is a constant foreach uv ∈ E (G). In this paper, we study the super edge-magicness of graphs of order n with degree sequences ∶ 4, 2, 2, . . . , 2. We also investigate the super edge-magic properties of certain families of graphs. This leads
us to propose some open problems.
Keywords: (Super) edge-magic graph; (Super) edge-magic labeling; Vertex degree; Degree sequence; Graphlabeling
MSC: 05C07; 05C78

1. Introduction
nly graphs without loops or multiple edges will be considered in this paper. Undefined graphtheoretical notation and terminology can be found in [1] or [2]. The vertex set of a graph G is denotedby V (G), while the edge set of G is denoted by E (G).
Motivated by the notion of magic valuation of graphs introduced by Kotzig and Rosa [3], Enomoto, Lladó,Nakamigawa, and Ringel [4] introduced the concept of super edge-magic graphs. A graph G is said to besuper edge-magic if there exists a bijective function f ∶ V (G) ∪ E (G) → {1, 2, . . . , ∣V (G)∣ + ∣E (G)∣} such thatf (V (G)) = {1, 2, . . . , ∣V (G)∣} and f (u) + f (v) + f (uv) is a constant (called the valence val ( f ) of f ) for eachuv ∈ E (G). Such a function is called a super edge-magic labeling.
The following lemma found in [5] is a very useful characterization of super edge-magic graphs.

OLemma 1. A graph G is super edge-magic if and only if there exists a bijective function f ∶ V (G) → {1, 2, . . . , ∣V (G)∣}such that the set
S = { f (u) + f (v) ∶ uv ∈ E (G)}consists of ∣E (G)∣ consecutive integers. In such a case, f extends to a super edge-magic labeling of G with valencek = ∣V (G)∣ + ∣E (G)∣ + s, where s = min (S) andS = {k − (∣V (G)∣ + 1) , k − (∣V (G)∣ + 2) , . . . , k − (∣V (G)∣ + ∣E (G)∣)} .
It is worth to mention that Acharya and Hegde [6] introduced the concept of strongly indexable graph thatturns out to be equivalent to the concept of super edge-magic graph (see [7]). The study of super edge-magiclabelings of graphs has proven to be crucial in the last two decades, since many relations with other types oflabelings have been found (see [5]), and relations with other concepts such as Skolem and Langford sequences(see [8]), and dual shuffle primes and Jacobsthal sequences (see [9] and [10]).

Open J. Discret. Appl. Math. 2023, 6(3), 22-25; doi:10.30538/psrp-odam2023.0089

https://pisrt.org/psr-press/journals/odam

23Open J. Discret. Appl. Math. 2023, 6(3), 22-25

For a thorough study of graph labeling problems, see the extensive survey by Gallian [11]. For more
information on super edge-magic graphs and related topics, see the books by Bača and Miller [12], Chartrand,Egan, and Zhang [13], López and Muntaner-Batle [14], and Marr and Wallis [15].
One of the main goals of this paper is to study the super edge-magic properties of graphs of order n with
degree sequence s ∶ 4, 2, 2, . . . , 2. In particular, we would like to stress the family of graphs that we define nextthat will be a point of study in the subsequent pages of this paper. For integers m ≥ 3 and n ≥ 3, let C(m, n)denote the graph consisting of two cycles Cm and Cn of orders m and n in such a way that the two cycles shareexactly one vertex in common. Observe that this family of graphs is the simplest case of the family of graphs
for which all blocks are cycles. In fact, another goal for this paper is to spread around the interest about thesuper edge-magic properties of graphs of this type.
Next, we proceed with the following lemma found in [5] that will be useful to obtain certain results inthis paper. For this purpose, the degree of a vertex v is denoted by degG (v) or simply by deg(v) if the graph
G under discussion is clear.
Lemma 2. Let G be a graph such that deg(v) is even for all v ∈ V (G) and ∣E (G)∣ ≡ 2 (mod 4). Then G is not superedge-magic.

2. Main results
We are now ready to state and prove our first result.
Theorem 3. Let G be a graph of even order n ≥ 6 with degree sequence s ∶ 4, 2, 2, . . . , 2. Then G is not super edge-magic.
Proof. Consider such a graph G with a super edge-magic labeling f . Then∣E (G)∣ =∑ deg(v) =v∈V(G)

4 + 2 (n − 1)
= n + 1.
2Thus, the valence val ( f ) of f can be computed as follows:val ( f ) =n2n+1ni + ∑2n+12 ∑i=1
∑ i + ∑i=1 i + 2α 5n2 + 7n + (2 + 4α)
i=n+1 i + 2α
= i=1=,n+1n+1
2 (n + 1)

where α ∈ [1, n]. We next examine for which values of α ∈ [1, n], 4α is a multiple of 2 (n + 1) or, equivalently,
2α is a multiple of n + 1. Observe that if α ∈ [1, n/2], then we have 2α ≤ n < n + 1. On the other hand, ifα ∈ [n/2 + 1, n], then we haven + 1 < n + 2 ≤ 2α ≤ 2n < 2n + 1.
Consequently, in either case, 2α cannot be a multiple of n + 1. Now,
5n2 + 7n + (2 + 4α) = 2 (n + 1) (so thatval ( f ) =5n+ 1) + 4α
25n2 + 7n + (2 + 4α)
5n2α= ( + 1) +.
2 (n + 1)
2n+1Note that 5n/2 + 1 is a positive integer, since n is an even integer n ≥ 6. However, since 2α is not a multiple ofn + 1, it follows from the last equation that val ( f ) is not a positive integer, which is impossible.
Observe that the preceding result excludes many graphs from being super edge-magic. In particular, we
immediately obtain the following corollary.
Corollary 4. For every two integers m ≥ 3 and n ≥ 3, the graph C (m, n) is not super edge-magic when m + n is odd.
At this point, a question raises naturally as the next problem indicates.

24Open J. Discret. Appl. Math. 2023, 6(3), 22-25

Problem 5. What can be said about the super edge-magicness of graphs of odd order n ≥ 5 with degree
sequence s ∶ 4, 2, 2, . . . , 2?
A partial solution to Problem 5 comes directly from Lemma 2. It is clear that a graph of odd order n withdegree sequence s ∶ 4, 2, 2, . . . , 2 has even size. If the size is not only even, but also not divisible by 4, then it
meets the hypothesis of Lemma 2, and hence it is not super edge-magic. Then Problem 5 becomes as follows.
Problem 6. Let G be a graph of odd order n ≥ 7 with ∣E (G)∣ ≡ 0 (mod 4) and degree sequence s ∶ 4, 2, 2, . . . , 2.
What can be said about the super edge-magicness of G?
We know so far that the family of graphs C (m, n) cannot be super edge-magic except possibly in the casewhen m + n ≡ 0 (mod 4). This leads to propose the following problem.
Problem 7. What can be said about the super edge-magicness of C (m.n) when m + n ≡ 0 (mod 4)?
An exhaustive computer search shows that C (3, 5) is not super edge-magic but is this true in general? Itis especially interesting to know whether C (3, 4k − 3) is super edge-magic for integers k ≥ 3.

3. Conclusions
We have established the super edge-magicness of the family of graphs C (m, n) when m + n is odd (seeCorollary 4), and different problems have emerged out of this study. In particular, we want to highlight thefollowing problem.
Problem 8. What can be said about the super edge-magicness of graphs that consist of blocks, which are all
isomorphic to a cycle?
We formulate the preceding problem in the most general sense possible, that is, the following concepts
were introduced in [16]. Let G be a graph of order p, size q and let SG denote the setp+q⎫⎧⎪⎪⎪⎪ ∑u∈V(G) deg(u)g(u) + ∑i=p+1 i: the function g ∶ V (G) → [1, p] is bijective⎬.
SG = ⎨⎪⎪q⎪⎪⎭⎩If ⌈min SG ⌉ ≤ ⌊max SG ⌋, then the super edge-magic interval of G is the set
IG = [⌈min SG ⌉, ⌊max SG ⌋] ∩ N,
where N denotes the set of natural numbers. The super edge-magic set of G isσG = {k ∈ IG : there exists a super edge-magic labeling of G with valence k } .
López et al. called a graph G perfect super edge-magic if IG = σG .
Hence, we would like to encourage researchers to study which graphs, if any, in this family are perfectsuper edge-magic. It is worth to mention to finish this paper that similar ideas to the ones of perfect superedge-magic graphs had already appeared in some other works. The interested reader may consult the resultsin [16] and [17].

Acknowledgements
The authors are gratefully indebted to Yukio Takahashi for his continuous encouragement and technicalassistance during this work. The authors would also like to acknowledge the referees for their valuable work.
Author Contributions: All authors contributed equally to the writing of this paper. All authors read and approved thefinal manuscript.
Conflicts of Interest: “The authors declare no conflict of interest.”

References

Open J. Discret. Appl. Math. 2023, 6(3), 22-25

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]

25

Chartrand, G., & Lesniak, L. (1996). Graphs & Digraphs 3th ed. CRC Press, Boca Raton.
West, D.B. (1996). Introduction to Graph Theory. Prentice-Hall, Upper Saddle River, NJ.
Kotzig, A., & Rosa, A. (1970). Magic valuations of finite graphs. Canadian Mathematical Bulletin, 13, 451–461.
Enomoto, H., Lladó, A., Nakamigawa, T., & Ringel, G. (1998). Super edge-magic graphs. SUT Journal of Mathematics,34, 105–109.
Figueroa-Centeno, R. M., Ichishima, R., & Muntaner-Batle, F. A. (2001). The place of super edge-magic labelings
among other classes of labelings. Discrete Mathematics, 231, 153–168.
Acharya, B. D., & Hegde, S. M. (1991). Strongly indexable graphs. Discrete Mathematics, 93, 123–129.
Hegde, S., & Shetty, S. (2003). Strongly k-indexable and super edge-magic labelings are equivalent. NITK Research
Bulletin, 12, 23–28.
López, S. C., & Muntaner-Batle, F. A. (2016). Langford sequences and a product of digraphs. European Journal ofCombinatorics, 53, 86–95.
López, S. C., Muntaner-Batle, F. A., & Prabu, M. (2017). On the super edge-magicness of graphs of equal order andsize. arXiv:1706.00211.
López, S. C., Muntaner-Batle, F. A., & Rius-Font, M. (2014). The jumping knight and other (super) edge-magicconstructions. Mediterranean Journal of Mathematics, 11(2), 217–235.
Gallian, J. A. (2022). A dynamic survey of graph labeling. Electronic Journal of Combinatorics, #DS6.
Bača, M., & Miller, M. (2007). Super edge-antimagic graphs: a wealth of problems and some solutions. Brown Walker Press,
Boca Raton, FL, USA.
Chartrand, G., Egan, C., & Zhang, P. (2019). How to Label a Graph. SpringerBriefs in Mathematics. Springer, Cham.
López, S. C., & Muntaner-Batle, F. A. (2017). Graceful, Harmonious and Magic Type Labelings: Relations and Techniques.
SpringerBriefs in Mathematics, Springer, Cham.
Marr, A. M., & Wallis, W. D. (2023). Magic Graphs Second ed. Birkhäuser/Springer, New York.
López, S. C., Muntaner-Batle, F. A., & Rius-Font, M. (2012). Perfect super edge-magic graphs. Bulletin Mathématiquede la Société des Sciences Mathématiques de Roumanie, 55(103)(2), 199–208.
López, S. C., Muntaner-Batle, F. A., & Rius-Font, M. (2014). Perfect edge-magic graphs. Bulletin Mathématique de laSociété des Sciences Mathématiques de Roumanie, 57(105)(1), 81–91.
© 2023 by the authors; licensee PSRP, Lahore, Pakistan. This article is an open access article
distributed under the terms and conditions of the Creative Commons Attribution (CC-BY) license(http://creativecommons.org/licenses/by/4.0/).