A paradigmatic approach to investigate restricted hyper totient graphs

1.   Introduction

In 2017, Khalid and Shahbaz ^[1] introduced the notions of totient, super totient and hyper totient numbers (see also ^[2]). Recall in this regard that a positive integer $t$ is said to be totient if the sum of its co-prime residues is $2^{k}t$, with $k\geq 1$. Further, a positive integer $s$ is called super totient if its set of co-prime residues can be divided into two nonempty disjoint subsets with equal sum. Finally, a positive integer $h$ is said to be hyper totient if its set of co-prime residues including $h$ can be divided into two nonempty disjoint subsets with equal sum. This paper focuses on the use of hyper totient numbers in graph labeling.

The assignment of positive integers as labels of vertices and/or edges of a graph is a classic problem in graph theory (see, for instance, ^[3,4,5]), with a broad range of applications in real daily life problems as networking, coding theory, digital design, database or management, amongst other areas. Nowadays, the problem of finding and characterizing new classes of integers satisfying certain given conditions, together with the problem of finding illustrative families of graphs for which a labeling based on such classes exists, constitutes a challenge for researchers in both number and graph theory. In the recent literature, one can find a wide amount of examples in this regard ^[6,7,8,9]. Of particular interest for the topic of this paper, it is remarkable the recent studies of Shahbaz and Khalid ^[1,10] on graph labelings based on super totient numbers, and the introduction of both concepts of restricted super totient labeling and super totient index of graphs by Joshua and Wong ^[11].

The paper is organized as follows. In Section 2, we describe some preliminary concepts and results on graph theory and hyper totient numbers that are used throughout the paper. Then, we introduce in Section 3 the concept of (restricted) hyper totient graph labeling. In particular, we prove that every finite graph is hyper totient. Finally, we investigate in Section 4 under which assumptions the following families of graphs constitute restricted hyper totient graphs: complete graphs, star graphs, complete bipartite graphs, wheel graphs, cycles, paths, fan graphs and friendship graphs.

2.   Preliminaries

This section deals with some preliminary concepts, notations and results on graph theory and hyper totient numbers that are used throughout the paper. For more details about these topics, we refer the reader to the manuscripts ^[1,10,12].

A graph is any pair $G = (V, E)$ formed by a set $V$ of vertices and a set $E$ of edges so that each edge joins two vertices, which are then said to be adjacent. The number of vertices and the number of edges of $G$ constitute, respectively, the order and size of $G$. A graph is said to be finite if both its order and size are finite. A subetaaph of $G$ is any graph $H = (W, F)$ such that $W\subseteq V$ and $F\subseteq E$. The set of vertices that are adjacent to a given vertex $v\in V$ constitutes its neighborhood $N_G(v)$. The number of such vertices constitutes the degree $d_G(v)$ of such a vertex $v$. The minimum vertex degree of the graph $G$ is denoted $\delta(G)$.

From now on, let $vw$ be the edge formed by two vertices $v, w\in V$. If $v = w$, then it is a loop. A graph is called simple if it does not contain loops. Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are said to be isomorphic if there exists a bijection $f:V_1\rightarrow V_2$ such that $uv\in E_1$ if and only if $f(u)f(v)\in E_2$.

A finite graph is called complete if all its vertices are pairwise adjacent. The complete graph of order $n$ is denoted $K_n$. Further, the complete bipartite graph $K_{m, n}$ is the finite graph of order $m+n$ whose set of vertices may be partitioned into two subsets of respective sizes $m$ and $n$ so that every edge of the graph contains a vertex of each one of these two sets. The complete bipartite graph $K_{1, n}$, with $n > 2$, is called a star graph. Its center is the unique vertex that is contained in all the edges.

A path between two distinct vertices $v$ and $w$ of a given finite graph $G$ is any ordered sequence of adjacent and pairwise distinct vertices $\langle\, v_0 = v, v_1, \ldots, v_{n-2}, v_{n-1} = w\, \rangle$ in $G$, with $n > 2$. If $v = w$, then it constitutes a cycle. As such, paths and cycles are also finite graphs. From here on, let $P_n$ and $C_n$ respectively denote the path and the cycle of order $n$. A graph is connected if there always exists a path between any pair of vertices. If no subetaaph of a connected graph $G$ is a cycle, then $G$ is called a tree.

Further, the wheel graph $W_n$ results after joining all the vertices of the cycle $C_n$ to a new vertex, which is called the center of the wheel graph. The fan graph $F_{m, n}$ is the graph that results after joining each vertex of a set of $m$ isolated vertices with all the vertices of the path $P_n$. Finally, the friendship graph $F_n$ is the graph that results after joining $n$ copies of the cycle $C_3$ with a common vertex. Figure 1 illustrates the different families of graphs that we have enumerated until now.

A vertex-labeling of a graph $G$ is any map $f:V\rightarrow \mathbb{N}$ assigning $|V|$ positive integers or labels to the set of vertices $V$. It gives rise to the induced multiplicative edge-labeling $f^*:E\rightarrow \mathbb{N}$ so that $f^*(vw) = f(v)f(w)$, for all $vw\in E$. In 2017, Khalid and Shahbaz ^[1] defined a super totient graph as any finite graph $G$ for which there exists an injective vertex-labeling $f$ (which is called super totient labeling of $G$) whose induced multiplicative edge-labeling $f^*$ assigns a super totient number to each one of its edges. In particular, they proved that every finite graph is super totient. Much more recently, Joshua and Wong ^[11] defined the super totient index of a finite graph $G$ as the minimum cardinality of the image of $f^*$, for every super totient labeling $f$ of $G$. In this paper, we focus on those injective vertex-labelings $f$ so that the image of the induced map $f^*$ is only formed by hyper totient numbers. To this end, the following result characterizing this type of numbers is of particular interest. It gathers together the different results on this subject that are enumerated in ^[2].

Theorem 2.1. Every hyper totient number is a positive integer $n > 2$ satisfying exactly one of the following two assertions.

a) It is an even integer distinct from $10$ and $30$.

b) It is a prime power $p^k$, with $k\geq 1$, where $p$ is a prime such that $p\equiv 3\, (\mathrm{mod}\, 4)$.

Proof. If $n < 32$, then the result follows readily from a simple computational check (see, for instance, [2,Table 1]). Further, according to [2,Theorem 3.6], a positive integer $n\geq 32$ is hyper totient if and only if $n(\varphi(n)+2)$ is divisible by $4$. Here, $\varphi(n)$ denote the Euler's totient number associated to $n$. That is, the number of co-prime residues of $n$. The result holds from the following study of cases.

● If $n$ is even, then $n(\varphi(n)+2)$ is divisible by $4$, because $\varphi(m)$ is also even, whatever the positive integer $m$ is. Hence, $n$ is hyper totient.

● If $n$ is odd, then $n$ is hyper totient if and only if $\varphi(n)+2$ is divisible by $4$. Equivalently, if $n = \prod_{i = 1}^m p_i^{k_i}$ is the prime factorization of $n$, then $\varphi(n) = \prod_{i = 1}^mp_i^{k_i-1}(p_i-1)\equiv 2\, (\mathrm{mod}\, 4)$. Since $n$ is an odd integer, we have that $p_i$ is also odd, for all $i\leq m$. Thus, $\varphi(n)\equiv 2\, (\mathrm{mod}\, 4)$ if and only if $m = 1$ in the previous prime factorization. (Otherwise, if $m > 1$, then $\varphi(n)$ would be divisible by $4$.) Hence, $n = p^k$, for some prime $p\equiv 3\, (\mathrm{mod}\, 4)$. (Notice to this last end that it would be $\varphi(n) = p^{k-1}(p-1)\equiv 2\, (\mathrm{mod}\, 4)$, where $p$ is odd.)

3.   Hyper totient graphs

In this section, we show how hyper totient numbers may be implemented in graph labeling. In this regard, we say that a finite graph $G = (V, E)$ is an hyper totient graph if there exists an injective vertex-labeling $f$ of $G$ whose induced multiplicative edge-labeling $f^*$ assigns a hyper totient number to each edge in $E$. In such a case, we say that the map $f$ is an hyper totient labeling (HTL) and that the graph $G$ is an hyper totient graph (HTG). In order to illustrate these concepts, Figure 2 shows an HTG of order five and size ten, whose vertices are uniquely labeled by the positive integers of the subset $\{2, 3, 4, 6, 7\}\subset\mathbb{N}$ and whose set of edges is then labeled by the set of totient numbers $\{4, 6, 8, 9, 12, 14, 16, 36, 49\}$. In order to distinguish both vertex- and edge-labelings, they are respectively colored in blue and black. Notice the fact that this graph is not simple.

Similarly to the concept of super totient index, which was introduced by Joshua and Wong in ^[11], we define the hyper totient index of the graph $G$ as

Then, we say that an HTL $f$ of the graph $G$ is optimal if $|f^*(V)| = \mathfrak{h}_*(G)$. In an analogous way to the result obtained by the mentioned authors in [11,Lemma 4.3], the following lemma holds.

Lemma 3.1. Let $G$ be an HTG. There always exists an optimal HTL of $G$ whose image is contained in the set $\{3^{i}: i\in \mathbb{N}\}$.

Proof. Let $f$ be an optimal HTL of the graph $G$ and let $V = \{v_1, \ldots, v_n\}$ be its set of vertices. Then, let $\{p_1, \ldots, p_t\}$ be a set of primes such that $f^{*}(v_i) = \prod_{j = 1}^t p_j^{a_{ij}}$, for all positive integers $i\leq n$, where each $a_{ij}$ is a non-negative integer. Let $m = 1 + \max \{ a_{ij}: 1\leq i\leq n, 1\leq j\leq t\}$. Then, Theorem 2.1 implies that the map $g: V\rightarrow \{3^{i}: i\in \mathbb{N}\}$ that is described so that $g(v_i) = 3^{\sum_{k = 1}^t a_{ik}m^{k-1}}$ constitutes an optimal HTL of the graph $G$.

The previous result enables us to ensure the equivalence of super totient and hyper totient indices, and the subsequent result concerning the fact that every finite graph is an HTG.

Theorem 3.2. Both the hyper totient index and the super totient index of any given finite graph coincide.

Proof. Let $f$ be an injective vertex-labeling of a graph $G = (V, E)$. This map induces the additive edge-labeling $f^+:E\rightarrow \mathbb{N}$ so that $f^{+}(vw) = f(v)+f(w)$, for all $vw\in E$. In addition, it is defined the sum index of the graph $G$ as

As a simple consequence of Lemma 3.1, the hyper totient index of the graph $G$ coincides with the sum index of such a graph. The result follows simply from the fact that, according to [11,Theorem 4.5], this last index also coincides with the super totient index of the graph $G$.

Corollary 3.3. Every finite graph constitutes an HTG.

Proof. The result follows straighforwardly from Theorem 3.2 and the fact that every finite graph is a super totient graph (see [1,Theorem 5.5]).

4.   Characterization of families of restricted hyper totient graphs

We say that a finite graph $G = (V, E)$ is a restricted hyper totient graph (RHTG) if it is a simple HTG whose set of vertices may be labeled by the subset of positive integers $\{1, \ldots, |V|\}$. The corresponding vertex-labeling is termed a restricted hyper totient labeling (RHTL) of $G$. Thus, for instance, Figure 3 illustrates a RHTL of order and size six, whose set of edges is labeled by the set of totient numbers $\{3, 4, 6, 12\}$. Again, the vertex-labeling is colored in blue and the edge-labeling is colored in black.

Of particular interest for the development of our work is the RHTG having maximum size for each given order. It is described as follows. Let $\Re_n$ be the RHTG of order $n$ that is defined so that there is an edge between the vertices labeled as $i$ and $j$, with $1\leq i\neq j\leq n$, if and only if the product $ij$ is a hyper totient number. Figure 4 illustrates this graph $\Re_n$, for all positive integers $n\leq 9$. In order to avoid a tangled mess of labels, we remove from now on the edge-labeling of the corresponding graphs.

The following result follows straightforwardly from the previous definitions.

Lemma 4.1. For $n > 3$, every spanning subetaaph of $\Re_n$ is an RHTG.

Lemma 4.1 enables us to ensure that the finding of RHTGs is completely solved once one may construct the graph $\Re_n$, for every positive integer $n$. In this regard, and based on Theorem 2.1, Algorithm 1 describes a simple computational method of time complexity $\mathcal{O}(n^2)$ for determining this graph $\Re_n$.

In this section, we study under which assumptions the following types of graphs constitute RHTGs: a complete graph $K_n$, a star graph $K_{1, n}$, a complete bipartite graph $K_{m, n}$, a wheel graph $W_n$, a cycle $C_n$, a path $P_n$, a fan graph $F_{1, n}$ and a friendship graph $F_n$. Notice that, according to Lemma 4.1, any subetaaph of any of these types of graphs satisfying the mentioned assumptions constitutes also an RHTG. Firstly, we focus on the complete graph $K_n$.

Proposition 4.2. Let $n$ be a positive integer. Then, the complete graph $K_n$ is an RHTG if and only if $n = 1$.

Proof. The case $n = 1$ is trivial. Further, the case $n\geq 2$ follows straightforwardly from the fact that the vertices labeled as $1$ and $2$ must be adjacent, but the induced edge label $2$ is not a hyper totient number.

Proposition 4.3. Let $n > 2$ be a positive integer. Then, the star graph $K_{1, n}$ is a spanning subetaaph of $\Re_{n+1}$. As a consequence, every star graph constitutes an RHTG.

Proof. According to Theorem 2.1, every multiple of $4$ is a hyper totient number. Hence, the spanning subetaaph of $\Re_{n+1}$ having as edges those ones containing the vertex labeled as $4$ constitutes a star graph $K_{1, n}$. This vertex corresponds indeed to the center of the star graph. The consequence follows readily from Lemma 4.1.

Theorem 4.4. Let $m$ and $n$ be two positive integers such that $2\leq m\leq n$. The complete bipartite graph $K_{m, n}$ is an RHTG if and only one of the following assertions hold.

a) $m = n = 2$.

b) $m = 2$ and $n\geq 6$.

c) $3\leq m\leq 11$ and $n\geq m+6$.

d) $m\geq 12$ and $n\geq m+8$.

Proof. Figure 5 illustrates the case $m = n = 2$. Thus, let us suppose the existence of two positive integers $m\geq 2$ and $n\geq 2$ such that $m+n > 4$ and $K_{m, n}$ is an RHTG. Let $v_i$ denote the vertex that is labeled as $i\in\{1, \ldots, m+n\}$ in the graph $\Re_{m+n}$. Since $10$ is not a hyper totient number, the two vertices $v_2$ and $v_5$ must belong to the same part of $K_{m, n}$. Let $P$ denote such a part. Then,

From Theorem 2.1, we have that

In particular, since $2\leq m\leq n$, it must be $m+n\geq 8$ and $n = |P|$. Moreover, Theorem 2.1 enables us to ensure that every vertex in the set $N_{\Re_{m+n}}(v_5)$, except for $v_{10}$ (if $m+n\geq 10$) and $v_{30}$ (if $m+n\geq 30$), is adjacent to any other vertex in the set $\Re_{m+n}$. Notice to this end that all the indices of such vertices are even integers and that both vertices $v_{10}$ and $v_{30}$ are not adjacent to $v_1\in P$. Due to this last aspect, it must be $\{v_{10}, \, v_{30}\}\subset P$. As a consequence,

Let $\alpha_{m, n}$ denote the previous lower bound, for the positive integers $m$ and $n$ under consideration. Then, in order to get an RHTL of the graph $K_{m, n}$, it is enough to take

Figure 6 illustrates an RHTL for the complete bipartite graph $K_{4, 13}$.

Theorem 4.5. Every tree containing at least $32$ vertices is an RHTG.

Proof. The result follows straightforwardly from Lemma 4.1, Proposition 4.3 and Theorem 4.4 once it is noticed that every tree is a bipartite graph.

Theorem 4.6. The wheel graph $W_n$ is an RHTG if and only if $n\geq 9$.

Proof. Throughout this proof, let $v_i$ denote the vertex labeled as $i\in\mathbb{N}$ in the graph under consideration. Notice in Figure 4 that $\delta(\Re_n)\leq 2$, for all positive integer $n\leq 9$. To this end, observe in the mentioned figure the vertex $v_1$, if $1\leq n\leq 5$, and the vertex $v_5$, if $6\leq n\leq 9$. Then, since $\delta(W_n) = 3$, for all positive integers $n$, we have from Lemma 4.1 that the wheel graph $W_n$ is not an RHTG, if $n < 9$.

Now, Figure 7 illustrates an RHTL of the wheel graph $W_9$. If we replace the edge $v_{10}v_6$ in that figure by the path $\langle\, v_{10}, v_{11}, \ldots, v_{n+1}, v_6\, \rangle$, so that all the vertices are joined with the center $v_4$ by an edge, then Theorem 2.1 implies that the resulting vertex-labeling is an RHTL of the wheel graph $W_n$.

Theorem 4.7. Let $n > 2$ be a positive integer. Then, the cycle graph $C_n$ is an RHTG if and only if $n = 4$ or $n\geq 8$.

Proof. Again, let $v_i$ denote the vertex labeled as $i\in\mathbb{N}$ in the graph under consideration. Notice in Figure 4 that $\delta(\Re_n)\leq 1$, for all positive integer $n\leq 7$, except for $n = 4$. To this end, observe in the mentioned figure the vertex $v_1$, if $1\leq n\leq 3$, and the vertex $v_5$, if $5\leq n\leq 7$. Then, since $\delta(C_n) = 2$, for all positive integers $n$, we have from Lemma 4.1 that the cycle $C_n$ is not an RHTG, if $n\in\{3, 5, 6, 7\}$.

Now, Figures 5 and 8 illustrate, respectively, RHTLs of the cycles $C_4$, which is isomorphic to the complete bipartite graph $K_{2, 2}$, and $C_8$. Finally, if $n\geq 9$, then the result follows simply from Lemma 4.1 and Theorem 4.6, once it is noticed that the cycle $C_n$ is a subetaaph of the wheel graph $W_{n+1}$.

Theorem 4.8. Every path is an RHTG.

Proof. Firstly, notice that the path $P_3$ is isomorphic to the graph $\Re_3$, and hence, it constitutes an RHTG. In addition, if $n = 4$ or $n\geq 8$, then the result follows simply from Lemma 4.1 and Theorem 4.7, once it is noticed that the path $P_n$ is a subetaaph of the cycle $C_n$. Finally, the case $n\in\{5, 6, 7\}$ is illustrated by the RHTL of the path $P_7$ in Figure 9, which contains implicitly the RHTLs of both paths $P_5$ and $P_6$ as subetaaphs.

Theorem 4.9. Let $n > 2$ be a positive integer. Then, the fan graph $F_{1, n}$ is an RHTG if and only if $n\geq 9$.

Proof. Since $\delta(F_{1, n}) = 2$, for all positive integers $n > 2$, Lemma 4.1 enables us to ensure that the fan graph $F_{1, n}$ is not an RHTG, for all $n\in\{4, 5, 6\}$, because $\delta(\Re_{n+1}) = 1$ in such cases. Further, the case $n\geq 9$ follows simply from Lemma 4.1 and Theorem 4.6, once it is noticed that the fan graph $F_{1, n}$ is a subetaaph of the wheel graph $W_n$. Finally, the case $n\in\{3, 7, 8\}$ is illustrated by the RHTLs of the fan graphs $F_{1, 3}$ and $F_{1, 8}$ in Figure 10. Notice to this end that the RHTL of the fan graph $F_{1, 7}$ is implicitly indicated in that one of the fan graph $F_{1, 8}$, of which the former constitutes a subetaaph.

Theorem 4.10. The friendship graph $F_n$ is an RHTG if and only if $n\geq 4$.

Proof. Since the order of the friendship graph $F_n$ is $2n+1$ and $\delta(\Re_n) = 1$, for all $n\in\{3, 5, 7\}$, then Lemma 4.1 implies that the friendship graph $F_n$ is not an RHTG, for all $n\leq 3$. Further, the case $n\geq 4$ follows simply from Lemma 4.1 and Theorem 4.6, once it is noticed that the friendship graph $F_n$ is a subetaaph of the wheel graph $W_m$, for all $m\geq 2n$.

5.   Conclusion

In this paper, we have introduced the notion of hyper totient graph as any finite graph $G = (V, E)$ admitting an injective vertex-labeling $f:V\rightarrow \mathbb{N}$ so that its induced multiplicative edge-labeling assigns a hyper totient number to each edge. We have proved in particular that every finite graph is hyper totient. Furthermore, we have introduced the concept of restricted hyper totient graph as a hyper totient graph of order $n$ whose vertices are labeled by the elements of the set $\{1, \ldots, n\}$. Then, we have determined under which assumptions some well-known families of graphs are restricted hyper totient.

Of course, the current manuscript constitutes a starting point for the study of hyper totient graphs, but a much deeper study is required in order to characterize all the structural properties of this type of graphs. In this regard, we propose as further work the study of locating, dominating and independent sets within a given RHTG, together with their corresponding locating, dominating and independent numbers. We also propose the following open questions for further work on this subject.

Problem 5.1. In Theorem 4.5, we have determined a lower bound for the number of vertices of a tree in order to ensure that the latter is an RHTG. But, what about trees of smaller orders? A similar reasoning to that one developed by Joshua and Wong in [11,Theorem 3.9] may be done in this regard.

Problem 5.2. In 2001, Beineke and Hedge ^[13] defined a strongly multiplicative graph as a finite graph of order $n$ for which there exists an injective vertex-labeling $f:V\rightarrow \{1, \ldots, n\}$ so that the induced multiplicative edge-coloring $f^*$ is injective. In a similar way, we may introduce here the notion of strongly hyper totient graph (SHTG) as an RHTG having distinct all the hyper totient numbers that are used for labeling its edges. Notice in this regard that the majority of RHTGs appearing in the figures of this paper are not SHTGs. The study of this type of RHTGs is established as further work.

Problem 5.3. Under which assumptions is the condition of being RHTG preserved by the different graph products existing in the literature? A similar question may be dealt with concerning the just introduced notion of SHTG.

Acknowledgments

Falcón's work is partially supported by the research project FQM-016 from Junta de Andalucía. In addition, the authors want to express their gratitude to the anonymous referees for the comprehensive reading of the paper and their pertinent comments and suggestions, which helped improve the manuscript.

Conflict of interest

All authors are here with confirm that there are no competing interests between them.