A study on consecutive edge-magic labelings and safe sets through graph operations

Abstract

In this thesis, we utilize graph operations to study consecutive edge-magic labelings and safe sets of graphs.

An edge-magic total labeling $f$ of a graph $G$ is a bijective function from $V(G) \cup E(G)$ to $\{1,\ldots,

V(G)

+

E(G)

\}$ such that for each $uv \in E(G)$, $f(u)+f(v)+f(uv)=c$ for some positive integer $c$. If $f(E(G))$ is a set of consecutive integer, then $f$ is called a consecutive edge-magic labeling and $G$ is said to be consecutive edge-magic. Especially, if $f(E(G)) = \{

+1,\ldots,

\}$, then $f$ is called a super edge-magic labeling and $G$ is said to be super-edge magic. The notion of $b$-edge consecutive magic labeling is derived from the notion of super edge-magic labeling, that is, if a consecutive edge-magic labeling $f$ of $G$ satisfies $f(E(G)) = \{b+1,\ldots, b+

\}$, then $f$ is called a $b$-edge consecutive magic labeling and $G$ is said to be $b$-edge consecutive magic.

Study on consecutive edge-magic labelings is one of the most popular topic on the study of graph labeling. Especially, characterizing consecutive edge-magic graphs is one of the most popular topic in the study of consecutive edge-magic labeling. Though there has been much study on the topic, determining whether or not it yields a consecutive edge-magic labeling remains open even for graphs with rather simple structures. In this thesis, we first study properties of consecutive edge-magic graphs and construct new consecutive edge-magic graph from existing consecutive edge-magic graphs through graph operation. We find out many special properties that a graph $G$ which admits $b$-edge consecutive magic labeling for $0 <b <

$ has. In particular, we show that a graph $G$ admitting $b$-edge consecutive magic labeling for $0 <b <

$ is a graceful tree having super edge-magic labeling. Then we provide several ways of obtaining new consecutive edge-magic graphs from consecutive edge-magic graphs through graph operation. Especially, we show that there are infinitely many super edge-magic trees containing arbitrary number of copies of a given super edge-magic tree. Those methods of obtaining new consecutive edge-magic graphs we developed are differentiated from other studies and expected to contribute to settling many open questions related to consecutive edge-magic labeling.

We also study the safe number and the connected safe number of Cartesian product of two complete graphs. For a connected graph $G$, a vertex subset $S$ of $V(G)$ is said to be a safe set if for every component $C$ of the subgraph of $G$ induced by $S$, $

C

\ge

D

$ holds for every component $D$ of $G-S$ such that there exists an edge between $C$ and $D$, and, in particular, if the subgraph induced by $S$ is connected, then $S$ is called a connected safe set. For a connected graph $G$, the safe number and the connected safe number of $G$ are the minimum among sizes of safe sets and the minimum among sizes of connected safe sets, respectively, of $G$. We show that the safe number and the connected safe number of Cartesian product of two complete graphs are equal and present a polynomial-time algorithm to compute the connected safe number of Cartesian product of two complete graphs. We believe that our idea used in the analysis of the structure of the graphs is useful enough to be applied to other graphs.