Contents

On the super edge-magicness of graphs with a specific degree sequence

Author(s): Rikio Ichishima1, Francesc-Antoni Muntaner-Batle2
1Department of Sport and Physical Education, Faculty of Physical Education, Kokushikan University, 7-3-1 Nagayama, Tama-shi, Tokyo 206-8515, Japan.
2Graph Theory and Applications Research Group, School of Electrical Engineering and Computer Science, Faculty of Engineering and Built Environment, The University of Newcastle, NSW 2308 Australia.
Copyright © Rikio Ichishima, Francesc-Antoni Muntaner-Batle. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

A graph \(G\) is said to be super edge-magic if there exists 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(V \left(G\right)\right) =\left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert \right\}\) and \(f\left(u\right) + f\left(v\right) + f\left(uv\right)\) is a constant for each \(uv\in E\left( G\right)\). In this paper, we study the super edge-magicness of graphs of order \(n\) with degree sequence \(s:4, 2, 2, \ldots, 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; Graph labeling.

1. Introduction

Only graphs without loops or multiple edges will be considered in this paper. Undefined graph theoretical notation and terminology can be found in [1] or [2]. The vertex set of a graph \(G\) is denoted by \(V \left(G\right)\), while the edge set of \(G\) is denoted by \(E\left (G\right)\).

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 be super edge-magic if there exists 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(V \left(G\right)\right) =\left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert \right\}\) and \(f\left(u\right) + f\left(v\right) + f\left(uv\right)\) is a constant (called the valence \(\text{val}\left(f\right)\) of \(f\)) for each \(uv\in E\left( G\right)\). 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.

Lemma 1. A graph \(G\) is super edge-magic if and only if there exists a bijective function \(f:V\left( G\right) \rightarrow \left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert \right\}\) such that the set \[S=\left\{ f\left( u\right) +f\left( v\right) : uv\in E\left( G\right) \right\}\] consists of \(\left\vert E\left( G\right) \right\vert\) consecutive integers. In such a case, \(f\) extends to a super edge-magic labeling of \(G\) with valence \(k=\left\vert V\left( G\right) \right\vert +\left\vert E\left( G\right) \right\vert +s\), where \(s=\min \left( S\right)\) and \[S=\left\{ k-\left( \left\vert V\left( G\right) \right\vert +1\right), k-\left( \left\vert V\left( G\right) \right\vert +2\right), \ldots , k-\left( \left\vert V\left( G\right) \right\vert +\left\vert E\left( G\right) \right\vert \right) \right\} \text{.}\]

It is worth to mention that Acharya and Hegde [6] introduced the concept of strongly indexable graph that turns out to be equivalent to the concept of super edge-magic graph (see [7]). The study of super edge-magic labelings of graphs has proven to be crucial in the last two decades, since many relations with other types of labelings 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]).

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 Bač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, \ldots, 2\). In particular, we would like to stress the family of graphs that we define next that will be a point of study in the subsequent pages of this paper. For integers \(m \geq 3\) and \(n \geq 3\), let \(C(m,n)\) denote the graph consisting of two cycles \(C_{m}\) and \(C_{n}\) of orders \(m\) and \(n\) in such a way that the two cycles share exactly 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 the super 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 in this paper. For this purpose, the degree of a vertex \(v\) is denoted by \(\deg_{G} (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 \in V\left(G\right)\) and \(\left\vert E\left( G\right) \right\vert \equiv 2\pmod{4}\). Then \(G\) is not super edge-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 \geq 6\) with degree sequence \(s:4, 2, 2, \ldots, 2\). Then \(G\) is not super edge-magic.

Proof. Consider such a graph \(G\) with a super edge-magic labeling \(f\). Then \[\left\vert E\left( G\right) \right\vert = \sum_{v \in V\left(G\right)} \deg (v) = \frac{4+2\left(n-1\right)}{2}=n+1 \text{.}\] Thus, the valence \(\text{val}\left(f\right)\) of \(f\) can be computed as follows: \[%\begin{split} \text{val}\left(f\right) = \frac{ 2\sum_{i=1}^{n} i +\sum_{i=n+1}^{2n+1} i +2\alpha}{n+1} = \frac{ \sum_{i=1}^{n} i +\sum_{i=1}^{2n+1} i +2\alpha}{n+1}=\frac{5n^2+7n+\left(2+4\alpha\right)}{2\left(n+1\right)} \text{,} %\end{split}\] where \(\alpha \in \left[1,n\right]\). We next examine for which values of \(\alpha \in \left[1,n\right]\), \(4\alpha\) is a multiple of \(2\left(n+1\right)\) or, equivalently, \(2\alpha\) is a multiple of \(n+1\). Observe that if \(\alpha \in \left[1,n/2\right]\), then we have \(2\alpha \leq n <n+1\). On the other hand, if \(\alpha \in \left[n/2+1,n\right]\), then we have \[n+1<n+2\leq 2\alpha \leq 2n <2n+1 \text{.}\] Consequently, in either case, \(2\alpha\) cannot be a multiple of \(n+1\). Now, \[5n^2+7n+\left(2+4\alpha\right)=2\left(n+1\right)\left(\frac{5n}{2}+1\right)+4\alpha\] so that \[\text{val}\left(f\right)=\frac{5n^2+7n+\left(2+4\alpha\right)}{2\left(n+1\right)}=\left(\frac{5n}{2}+1\right)+ \frac{2\alpha}{n+1} \text{.}\] Note that \(5n/2+1\) is a positive integer, since \(n\) is an even integer \(n \geq 6\). However, since \(2\alpha\) is not a multiple of \(n+1\), it follows from the last equation that \(\text{val}\left(f\right)\) 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 \geq 3\) and \(n \geq 3\), the graph \(C\left(m,n\right)\) is not super edge-magic when \(m+n\) is odd.

At this point, a question raises naturally as the next problem indicates.

Problem 5. What can be said about the super edge-magicness of graphs of odd order \(n \geq 5\) with degree sequence \(s:4, 2, 2, \ldots, 2\)?

A partial solution to Problem 5 comes directly from Lemma 2. It is clear that a graph of odd order \(n\) with degree sequence \(s:4, 2, 2, \ldots, 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 \geq 7\) with \(\left\vert E\left( G\right) \right\vert \equiv 0\pmod{4}\) and degree sequence \(s:4, 2, 2, \ldots, 2\). What can be said about the super edge-magicness of \(G\)?

We know so far that the family of graphs \(C\left(m,n\right)\) cannot be super edge-magic except possibly in the case when \(m+n \equiv 0\pmod{4}\). This leads to propose the following problem.

Problem 7. What can be said about the super edge-magicness of \(C\left(m.n\right)\) when \(m+n \equiv 0\pmod{4}\)?

An exhaustive computer search shows that \(C\left(3,5\right)\) is not super edge-magic but is this true in general? It is especially interesting to know whether \(C\left(3,4k-3\right)\) is super edge-magic for integers \(k \geq 3\).

3. Conclusions

We have established the super edge-magicness of the family of graphs \(C\left(m,n\right)\) when \(m+n\) is odd (see Corollary 4), and different problems have emerged out of this study. In particular, we want to highlight the following 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 \(S_{G}\) denote the set \[%\begin{split} %\begin{multline*} S_{G} = \Biggl\lbrace \frac{\sum_{u \in V\left(G\right)} \text{deg}(u)g(u) + \sum_{i=p+1}^{p+q} i }{q} \text{:} \text{ the function } g:V\left(G\right) \rightarrow \left[1,p\right] \text{ is bijective} \Biggr\rbrace \text{.} %\end{multline*} %\end{split}\] If \(\lceil \min S_{G} \rceil \leq \lfloor \max S_{G} \rfloor\), then the super edge-magic interval of \(G\) is the set \[I_G = [\lceil \min S_{G} \rceil, \lfloor \max S_{G} \rfloor] \cap \mathbb{N} \text{,}\] where \(\mathbb{N}\) denotes the set of natural numbers. The super edge-magic set of \(G\) is \[\sigma_{G} = \left\lbrace k \in I_G \right. \text{: there exists a super edge-magic labeling of } G \text{ with valence } k \left. \right\rbrace.\] López et al. called a graph \(G\) perfect super edge-magic if \(I_G = \sigma_G\).

Hence, we would like to encourage researchers to study which graphs, if any, in this family are perfect super edge-magic. It is worth to mention to finish this paper that similar ideas to the ones of perfect super edge-magic graphs had already appeared in some other works. The interested reader may consult the results in [16] and [17].

Acknowledgements

The authors are gratefully indebted to Yukio Takahashi for his continuous encouragement and technical assistance during this work. The authors would also like to acknowledge the referees for their valuable work.

References

  1. Chartrand, G., & Lesniak, L. (1996). Graphs & Digraphs 3th ed. CRC Press, Boca Raton.

  2. West, D.B. (1996). Introduction to Graph Theory. Prentice-Hall, Upper Saddle River, NJ.

  3. Kotzig, A., & Rosa, A. (1970). Magic valuations of finite graphs. Canadian Mathematical Bulletin, 13, 451–461.

  4. Enomoto, H., Lladó, A., Nakamigawa, T., & Ringel, G. (1998). Super edge-magic graphs. SUT Journal of Mathematics, 34, 105–109.

  5. 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.

  6. Acharya, B. D., & Hegde, S. M. (1991). Strongly indexable graphs. Discrete Mathematics, 93, 123–129.

  7. Hegde, S., & Shetty, S. (2003). Strongly \(k\)-indexable and super edge-magic labelings are equivalent. NITK Research Bulletin, 12, 23–28.

  8. López, S. C., & Muntaner-Batle, F. A. (2016). Langford sequences and a product of digraphs. European Journal of Combinatorics, 53, 86–95.

  9. López, S. C., Muntaner-Batle, F. A., & Prabu, M. (2017). On the super edge-magicness of graphs of equal order and size. arXiv:1706.00211.

  10. López, S. C., Muntaner-Batle, F. A., & Rius-Font, M. (2014). The jumping knight and other (super) edge-magic constructions. Mediterranean Journal of Mathematics, 11(2), 217–235.

  11. Gallian, J. A. (2022). A dynamic survey of graph labeling. Electronic Journal of Combinatorics, #DS6.

  12. Bača, M., & Miller, M. (2007). Super edge-antimagic graphs: a wealth of problems and some solutions. Brown Walker Press, Boca Raton, FL, USA.

  13. Chartrand, G., Egan, C., & Zhang, P. (2019). How to Label a Graph. SpringerBriefs in Mathematics. Springer, Cham.

  14. López, S. C., & Muntaner-Batle, F. A. (2017). Graceful, Harmonious and Magic Type Labelings: Relations and Techniques. SpringerBriefs in Mathematics, Springer, Cham.

  15. Marr, A. M., & Wallis, W. D. (2023). Magic Graphs Second ed. Birkh\(\ddot{a}\)user/Springer, New York.

  16. López, S. C., Muntaner-Batle, F. A., & Rius-Font, M. (2012). Perfect super edge-magic graphs. Bulletin Mathématique de la Société des Sciences Mathématiques de Roumanie, 55(103)(2), 199–208.

  17. López, S. C., Muntaner-Batle, F. A., & Rius-Font, M. (2014). Perfect edge-magic graphs. Bulletin Mathématique de la Société des Sciences Mathématiques de Roumanie, 57(105)(1), 81–91.