On super totient numbers and super totient labelings of graphs

Autor: Tony W. H. Wong, Joshua Harrington
Rok vydání: 2020
Předmět:
Zdroj: Discrete Mathematics. 343:111670
ISSN: 0012-365X
DOI: 10.1016/j.disc.2019.111670
Popis: A positive integer n is a super totient number if the set of positive integers less than n and relatively prime to n can be partitioned into two sets of equal sum. In this article, we give a complete classification of super totient numbers. We also utilize super totient numbers to consider graph labelings. Let G be a graph with vertex set V and edge set E . For every injective vertex labeling f : V → N , define f ∗ : E → N and f + : E → N such that f ∗ ( u v ) = f ( u ) f ( v ) and f + ( u v ) = f ( u ) + f ( v ) . We say f is a super totient labeling if f ∗ ( u v ) is a super totient number for every u v ∈ E . Moreover, if the range of a super totient labeling f is { 1 , 2 , … , | V | } , then f is said to be a restricted super totient labeling. The concept of super totient numbers was first introduced in 2017 by Mahmood and Ali, and they showed that every graph admits a super totient labeling. We classify all restricted super totient complete bipartite graphs, trees, wheel graphs, and friendship graphs. Furthermore, we introduce the sum index of a graph G , which is the minimum positive integer k such that there exists an injective vertex labeling f of G with the cardinality of the range of f + being k . We show that the sum index is related to the concept of super totient labelings, and we determine the sum index of complete graphs, complete bipartite graphs, and certain families of trees such as caterpillar graphs.
Databáze: OpenAIRE