# Strongly Multiplicative Labeling of Diamond Graph, Generalized Petersen Graph, and Some Other Graphs

Authors: Sumiya Nasir; Nazeran Idrees; Afshan Sadiq; Fozia Bashir Farooq; Salma Kanwal; Muhammad Imran
Journal: Journal of Mathematics
 (2022)

---

## Abstract

A finite, simple graph of orderk is said to be a strongly multiplicative graph when all vertices of the graph are labeled by positive integers 1,2,3,…,k such that the induced edge labels of the graph, obtained by the product of labels of end vertices of edges, are distinct. In this paper, we show that the diamond graph Brn for 𝑛 ≥ 3, umbrella graph Um,n, and generalized Petersen graph GPn,k, for n≥3 and 1≤k<n/2, admit strongly multiplicative labeling. Moreover, strongly multiplicative labeling of a double comb graph and sunflower planar graph has also been investigated and elaborated as well with different examples.


---

## Body

## 1. Introduction

Graph labeling is an important technique in discrete mathematics. Applications of graph labeling can be found everywhere in life, from communication networks to possible moves in a board game. In the 18th century, Swiss mathematician Leonhard Euler invented the concept of graph theory. Some applications of graph labeling include network flow, fuzzy graph theory, coding theory, robotics, channel assignment, robotics, and many more. In 1967, a basic idea of graph labeling was presented by Rosa [1]. A comprehensive study of labeling of different graphs is presented by Gallian [2].Strongly multiplicative labeling first appeared in the work of Beineke and Hedge [3]. Adiga et al. [4] computed an upper bound for the maximum number of edges sharper than that provided in [3] in a strongly multiplicative graph of order n. In 2010, Vaidya and Kanani generalized that the graphs constructed by the arbitrary super-subdivision of cycle, path, star, and tadpole graphs are strongly multiplicative [5, 6]. Punitha et al. [7] investigated the strongly multiplicative labeling of circulant graphs. For some interesting results on labeling, we refer the readers to [8–14].In this paper, strongly multiplicative labeling of different types of graphs is investigated. First, we plot the graph of a diamond graph, umbrella graph, generalized Petersen graph, double comb graph, and sunflower planar graph and then label the vertices of these graphs according to the condition of strongly multiplicative labeling.


## 2. Materials and Methods

In the section, we give simple definitions of different standard graphs which are under consideration for strongly multiplicative labeling.Definition 1.
A graphG=V;E contains set of vertices (points or nodes) V and set of edges (links or lines) E. These objects are called lines and points.
We will consider connected, simple, undirected, and finite graphG=VG,EG, where the size of the graph is EG=q and the order is VG=p.Definition 2.
A graphG=VG,EG having p vertices is known as a strongly multiplicative graph when all vertices of graph are labeled by p consecutive numbers of positive integers 1, 2, 3, …, p; then, the edge labels that are induced on by the product of labels of the end vertices are different.Definition 3.
A diamond networkBrn for n≥3 is gained by connection of a single vertex x to all other vertices vi,i=1,2,…,n, of the triangular ladder graph TLn.Definition 4.
The umbrella graphUm,n (where m > 2, n > 1) is the graph found by connecting the pendant edge of path Pn at the essential vertex of the fan graph which is plotted at the center such as Fm=Pm+K1.Definition 5.
The generalized Petersen graphGPn,k also represented by Pn,k for n≥3 and 1≤k<n/2 which is also a connected and cubic graph with a vertex set vi,wi|i=1,2,…,n and the edge set is vivi+1,viwi,wiwi+k|i=1,2,…,n.
These graphs were first presented by Coxeter (1950) and then named by a mathematician Watkins (1969). The generalized Petersen graphGPn,k is isomorphic toGPn,n−k. Due to this isomorphic relation, k<n/2 is defined with no restriction of generality.Definition 6.
A double comb graphDCn is found from a path Pn by connecting two pendant vertices with each vertex of Pn. It is also represented by Pn⊙2K1.Definition 7.
A sunflower planar graph is denoted bySfn which is achieved from a wheel graph having vertices v0,v1,v2,v3,…,vm (v0 is essential vertex whereas v1,v2,v3,…,vm are rim vertices) and other vertices u1,u2,u3,…,um such that uj is joined to vj and vj+1 (modn).


## 3. Main Results

Theorem 1.
The diamond graphBrn admits strongly multiplicative labeling.Proof.
The vertex set ofBrn is V=x,v1,v2,…,vn,u1,u2,…,un−r and the edge set is E=vivi+1|i=1,2,…,n−1∪uiui+1|i=1,2,…,n−2∪uivi,uivi+1|i=1,2,…,n−1∪xvi|i=1,2,…,n.
It is to be noted thatVBrn=2n and EBrn=5n−5.
Letvi,uivi,ui, and x be the vertices of the diamond graph. Here, the vertices ui are adjacent to vi and vi+1. The mapping of vertices is defined as follows:(1)f:VBrn⟶1,2,…,2n,where(2)fvi=2i−1,∀1≤i≤n,fvi=2i+2,∀1≤i≤n−1,and fx=2i.
According to this mapping, the products of label of two end vertices are the induced edge labels, which are also distinct, i.e., no two edges have same labels.
Hence,Brn is a strongly multiplicative graph.
Strongly multiplicative labeling ofBr7 is elaborated in Figure 1.Figure 1
Representation ofBr9 with strongly multiplicative labeling.Theorem 2.
The umbrella graphUm,n admits strongly multiplicative labeling.Proof.
Proof. The vertex set ofUm,nUm,n is V=u1,u2,u3,…,um,u0=v1,v2,v3,…,vn and the edge set is as follows:(3)E=v1us:1≤s≤m∪usus+1∶1≤s≤m−1∪usus+1:1≤s≤n−1.
It is to be noted thatVUm,n=m+n and EUm,n=2m+n−2.
Letv1,v2,v3,…,vn and u1,u2,u3,…,un be the vertices of the graph as specified in Figure 2. The labeling of the graph must be strongly multiplicative. The mapping of the vertices is defined as follows:(4)f:VUm,n⟶1,2,…,m+n,where(5)fui=i,∀1≤i≤m,fvi=i+m,∀1≤i≤n.
According to this mapping, the products of label of two end vertices are the induced edge labels which are also distinct, i.e., no two edges have same labels.
Hence,Um,n is a strongly multiplicative graph.
It is to be noted that the above defined mapping is proved for even and odd values ofn.
In Figure2, strongly multiplicative labeling of U7,4 is shown.Figure 2
Representation ofU7,4 with strongly multiplicative labeling.Theorem 3.
The generalized Petersen graphGPn,k admits strongly multiplicative labeling.Proof.
The generalized Petersen graphGPn,kGPn,k for n≥3 and 1≤k<n/2 is a cubic graph which is also connected.
The vertex set ofGPn,kGPn,k is V=vi,ui:1≤i≤n. Here, v1,v2,…,vn are the vertices of the inner cycle and u1,u2,…,un are the vertices of the outer cycle of the generalized Peterson graph. The set of edges of GPn,kGPn,k is as follows:(6)E=uivi,uiui+1,vivi+k:1≤i≤n.
It is to be noted thatVGPn,k=2n and EGPn,k=3n.
Vertices of the generalized Petersen graph are labeled as follows:(7)f:VGPn,k⟶1,2,…,2n,where(8)fvi=2i−1,∀1≤i≤n,fui=2i,∀1≤i≤n.
According to this mapping, the products of label of two end vertices are the induced edge labels which are also distinct, i.e., no two edges have same labels.
Hence,GPn,k is strongly multiplicative graph.
In Figure3, strongly multiplicative labeling of the Durer graph GP(6, 2) is shown.Figure 3
Representation of GP(6, 2) with strongly multiplicative labeling.Theorem 4.
The double comb graphDCn admits strongly multiplicative labeling.Proof.
The vertex set ofDCn is V=vm,um,wm:1≤m≤n and the edge set is as follows:(9)E=umum+1:1≤m≤n−1∪umvm:1≤m≤n∪umwm:1≤m≤n.
It is to be noted thatVDCn=3n and EDCn=3n−1.
Letu1,u2,u3,…,um,v1,v2,v3,…,vm,andw1,w2,w3,…,wm be the vertices of a path. The mapping of vertices is defined as follows:(10)f:VDCn⟶1,2,…,3n,where(11)fwi=3i,∀1≤i≤n,fui=3i−1,∀1≤i≤n,fvi=3i−2,∀1≤i≤n.
According to this mapping, the products of label of two end vertices are the induced edge labels which are also distinct, i.e., no two edges have same labels.
Hence, the double comb graphDCn is a strongly multiplicative graph.
In Figure4, strongly multiplicative labeling of DC7 is elaborated.Figure 4
Representation ofDC7DC7 with strongly multiplicative labeling.Theorem 5.
The sunflower planar graphSfn admits a strongly multiplicative graph.Proof.
The vertex set of the sunflower planar graph isV=v0,vm,um:1≤m≤n and the edge set is as follows:(12)E=v0vm:1≤m≤n∪vmvm+1,vnv1:1≤m≤n−1∪umvm,umvm+1:1≤m≤n.
It is to be noted thatVSfn=2n+1 and ESfn=4n.
Letv0,v1,v2,v3,…,vm and u1,u2,u3,…,um be the connected vertices of a graph. In order to get strongly multiplicative labeling of the graph, the mapping of vertices is defined as follows:(13)f:VSfn⟶1,2,…,2n+1,where(14)fui=i,∀1≤i≤n,fvi=i+n,∀1≤i≤n,fv0=i+2n.
According to this mapping, the products, of label of two end vertices are the induced edge labels which are also distinct i.e., no two edges have same labels.
Hence,Sfn is a strongly multiplicative graph.
In Figure5, strongly multiplicative labeling of the sunflower planar graph Sf8 is shown.Figure 5
Representation ofSf8Sf8 with strongly multiplicative labeling.


## 4. Conclusion

In this paper, strongly multiplicative labeling of certain well-known families of graphs is analyzed. First, we label families of orderk of the diamond graph, umbrella graph, generalized Petersen graph, double comb graph, and sunflower planar graph. We label the vertices of these graphs according to the condition of strongly multiplicative labeling. By multiplying labels of two adjacent vertices, we get the value of their connected edge. By doing this technique, we generated some important results for any order of different types of graphs which are presented in this work. By using these results, strongly multiplicative labeling of any order n of graph can be calculated. These results give a basic idea to compute strongly multiplicative labeling of the diamond graph, umbrella graph, generalized Petersen graph, double comb graph, and sunflower planar graph.


### 4.1. Open Problems

Problems of finding strongly multiplicative labeling of transformation graphs, Mobius ladder, polygonal chains, stacked prism graph, and many others are open for future research.


## 4.1. Open Problems

Problems of finding strongly multiplicative labeling of transformation graphs, Mobius ladder, polygonal chains, stacked prism graph, and many others are open for future research.



---

*Source: 3203108-2022-07-05.xml*