Nowadays, the problem of finding families of graphs for which one may ensure the existence of a vertex-labeling and/or an edge-labeling based on a certain class of integers, constitutes a challenge for researchers in both number and graph theory. In this paper, we focus on those vertex-labelings whose induced multiplicative edge-labeling assigns hyper totient numbers to the edges of the graph. In this way, we introduce and characterize the notions of hyper totient graph and restricted hyper totient graph. In particular, we prove that every finite graph is a hyper totient graph and we determine 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.
Citation: Shahbaz Ali, Muhammad Khalid Mahmmod, Raúl M. Falcón. A paradigmatic approach to investigate restricted hyper totient graphs[J]. AIMS Mathematics, 2021, 6(4): 3761-3771. doi: 10.3934/math.2021223
Nowadays, the problem of finding families of graphs for which one may ensure the existence of a vertex-labeling and/or an edge-labeling based on a certain class of integers, constitutes a challenge for researchers in both number and graph theory. In this paper, we focus on those vertex-labelings whose induced multiplicative edge-labeling assigns hyper totient numbers to the edges of the graph. In this way, we introduce and characterize the notions of hyper totient graph and restricted hyper totient graph. In particular, we prove that every finite graph is a hyper totient graph and we determine 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.
| [1] | M. Khalid, A. Shahbaz, A novel labeling algorithm on several classes of graphs, Punjab Univ. J. Math., 49 (2017), 23-35. |
| [2] | A. Shahbaz, M. Khalid, New numbers on Euler's totient function with application, J. Math. Extension, 14 (2019), 61-83. |
| [3] | A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs: Int. Symp., Rome, 1966, (1967), 349-355. |
| [4] |
G. S. Bloom, S. W. Golomb, Application of numbered undirected graphs, P. IEEE, 65 (1977), 562-570. doi: 10.1109/PROC.1977.10517
|
| [5] | J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Comb., 6 (2009), 1-219. |
| [6] | H. V. Dinh, M. Rosenfeld, A new labeling of $C_2n$ proves that $K_{4} + M_6n$ decomposes $K_6n+4$, Ars Comb., 4 (2018), 255-267. |
| [7] |
M. Hussain, A. Tabraiz, Super $d$-anti-magic labeling of subdivided $kC_ {5}$, Turk. J. Math., 39 (2015), 773-783. doi: 10.3906/mat-1501-45
|
| [8] |
M. Seoud, S. Salman, Some results and examples on difference cordial graphs, Turk. J. Math., 40 (2016), 417-427. doi: 10.3906/mat-1504-95
|
| [9] |
M. Seoud, M. Salim, Further results on edge-odd graceful graphs, Turk. J. Math., 40 (2016), 647-656. doi: 10.3906/mat-1505-67
|
| [10] | M. Khalid, A. Shahbaz, On super totient numbers with applications and algorithms to graph labeling, Ars Comb., 143 (2019), 29-37. |
| [11] |
H. Joshua, W. H. T. Wong, On super totient numbers and super totient labelings of graphs, Discrete Math., 343 (2020), 111670. doi: 10.1016/j.disc.2019.111670
|
| [12] | F. Harary, Graph Theory, Reading, Massachusetts: Addison Wesley, 1969. |
| [13] |
L. W. Beineke, S. M. Hegde, Strongly multiplicative graphs, Discuss. Math. Graph T., 21 (2001), 63-75. doi: 10.7151/dmgt.1133
|
Figures(10)
Shahbaz Ali, Muhammad Khalid Mahmmod, Raúl M. Falcón. A paradigmatic approach to investigate restricted hyper totient graphs[J]. AIMS Mathematics, 2021, 6(4): 3761-3771. doi: 10.3934/math.2021223
DownLoad: