Edge-Magic Total Labeling on Vertex Amalgamation Graphs of a Star Graph with a Path Graph

Selfa Suwandi^1*, Nurdin², Muh. Nur³

Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Hasanuddin, Indonesia¹²³

Email: [email protected]¹, [email protected]²

ABSTRACT

One of the topic graph theories is graph labeling. Let ï¿½be a finite simple connected graph, a bijection ï¿½from ï¿½to ï¿½where ï¿½and ï¿½is called an edge-magic total labeling of ï¿½if there exists a contant ï¿½(called the magic sum of ) such that ï¿½for any edge ï¿½of . The super edge-magic total labeling on a graph ï¿½is the edge-magic total labeling which maps ï¿½into the set . Let ï¿½be a connected graph with a fixed vertex . The vertex amalgamation of graph ï¿½onto a fixed vertex ï¿½called terminal denoted by ï¿½is a graph formed by taking all elements (vertices and edges) in ï¿½with . In this study, we will show that vertex amalgamation graphs of a star graph with a path graph are edge-magic total and super edge-magic total labeling, with constructed vertex labelings and edge labelings to obtain intervals of the magic sums .

Keywords: Graph Theory, Broom Graphs, Graph Labeling

INTRODUCTION

The development of graph theory has been due in big measure to its essential role in the applied sciences (Aytaï¿½, 2020). The link between graph theory and other branches of mathematics are becoming progressively strong (Mallik & Ghosh, 2018).

According to historical records, graph theory originated from the solution to the Konigsberg bridge problem introduced by Leonhard Euler, a famous Swiss mathematician in 1736, in his writings entitled "Solutio Problematis and Geometrian Pertinentist Sites". Thanks to Euler's work, which was inspired through the Konigsberg bridge problem, a fairly important branch of mathematics was created known as graph theory (Mondal & De, 2017).

In forming a new graph, one way that can be done is by using the amalgamation operation (Chatterjee et al., 2020). In this study, the authors will use vertex amalgamation operations. A vertex amalgamation of pairs of graph vertices ï¿½together is the resulting graph ï¿½by joining the vertices and becoming one fixed vertex ï¿½(Abu-Khzam et al., 2018).

In the development of graph theory there are several fields of study, one of which is graph labeling (Chartrand et al., 2019). Graph labeling is a topic of combinatoric mathematics research that has developed rapidly in recent years. An edge-magic total labeling is one of the most important types of labeling (Lï¿½pez et al., 2017; Mohan, 2019). A graph that fulfills edge-magic total labeling is a graph that is labeled with a positive integer, where each vertex and the associated edge (incident) when added together produce the same positive integer (Chartrand et al., 2019). The edge-magic total labeling is called super edge-magic total labeling if each vertex is labeled with the smallest positive integer (Bača et al., 2019; Farahmand Asil, 2018; Maowa, 2016; Marimuthu & Kumar, 2015; Slater, 2016; Yao & Wang, 2021).

As far as we know, for the family of graphs , there have not been any traditional manual method that can obtain its edge-magic total and super edge-magic total labeling with intervals of the magic sums. Now, we design a new edge-magic total and super edge-magic total labeling manual method with intervals of magic sums for the family of graphs ï¿½based on the graph labeling method.

RESEARCH METHODE

This research uses a literature review method to collect, evaluate, and synthesize relevant information from related literature. This approach allows us to understand the development of graph theory from a variety of sources, including the contributions of leading figures in the field throughout history. Any sector of mathematics about any scientific activity, we feel that appreciation of graph theory is enhanced by being familiar with most of the people, present and in the past, who were or are responsible for its growth (Chartrand et al., 2019). General graph theory principles are used in various fields for research and different application models. This includes studying biodiversity, conservation and even to quantify actor popularity or to investigate diffusion prosesses (Andriollo et al., 2023).

Definition 1. A graph ï¿½consists of a finite nonempty set ï¿½of objects called vertices (a vertex for the singular) and a set ï¿½of 2-element subsets ofï¿½ ï¿½called edges. The sets ï¿½is vertex set and the sets ï¿½is edge set of . Thus, a graph ï¿½is an ordered pair of two sets ï¿½and ï¿½[9].

Thus, the literature review method in this research plays a key role in presenting a comprehensive understanding of the development of graph theory and its broad applications in various fields of science.

A. Types of Graphs

In this study, we provide two types of broom graphs that will be used in this study.

Definitions 2. A broom graph ï¿½is a connected graph of order ï¿½which has ï¿½vertices of degree 1, ï¿½vertices of degree 2, and 1 vertex of degree . A broom graph can be constructed through a vertex amalgamation between a path graph and a star graph [1].

Definitions 3. A broom graph can also be defined through an operation of vertex amalgamation between a path graph and a star graph. Suppose ï¿½is a path graph of order ï¿½and ï¿½is a star graph of order at a fixed vertex

A broom graph of order ï¿½denoted ï¿½is ï¿½is a graph that consists of all vertices and edges of ï¿½and ï¿½where vertices ï¿½[1].

B. The Vertex Amalgamation

In this section, we present a definition of a vertex amalgamation of graph.

Definition 4. Let ï¿½graph is connected with a fixed vertex . The amalgamation of graph ï¿½at a fixed vertex called a terminal denoted by ï¿½is a graph formed by taking all the elements (vertices and edges) of ï¿½with . The graph ï¿½can also be written as . If ï¿½for each ï¿½then ï¿½can be written as ï¿½for all ï¿½[1].

C. ï¿½ï¿½Edge-Magic Total Labeling and Super Edge-Magic Total Labeling

In this section, we present some definitions of edge-magic total and super edge-magic total labeling.

Definition 5. Let ï¿½be a finite simple connected graph, a bijection ï¿½from ï¿½to ï¿½is called an edge-magic total labeling (EMTL for short) of ï¿½if there exists a constant ï¿½(called the magic sum of ) such that ï¿½for any edge ï¿½of ï¿½[11].

Definition 6. An edge-magic total labeling ï¿½of a ï¿½graph ï¿½is called super edge-magic total (super EMTL) if ï¿½[10.

According to the definiton of super edge-magic total labeling, we know that the sum of all labels assigned to vertices and edges of a graph ï¿½is denoted by , the formula

(2.1)

Where ï¿½and ï¿½stand for the sum of labels assigned to the vertices and the sum of labels assigned to the edges, respectively. On the other hand, ï¿½is the degree of vertex ï¿½[11], we get the formula (2.2).

RESULTS AND DISCUSSION

A. Vertex Amalgamations of a Star Graph with a Path Graph

The following definition of a vertex amalgamation of graph is taken from [1]. Suppose ï¿½and ï¿½are subgraphs of a graph ï¿½and . The graph ï¿½is called the vertex amalgamation of ï¿½and ï¿½at a fixed vertex , denoted by , if ï¿½and . So, the amalgamation ï¿½is a graph formed by taking all the elements (vertices and edges) of .

B. Intervals of Magic Sums on Vertex Amalgamation Graphs of a Star Graph with a Path Graph

In this section, we present intervals of magic sum of four new graphs on vertex amalgamation graphs of a star graph ï¿½with a path graph .

a. Magic Sums of a Graph

Suppose ï¿½obtains a set of vertices and a set of edges

Suppose ï¿½is the sum of all labels assigned to vertices and edges of a graph , thus the vertex sets and edge sets are labeled from number 1 to . Furthermore, by substituting the value ï¿½and into Eq. (2.1) we get

(3.1)

Theorem 3.1. ï¿½Let ï¿½is a graph of a vertex amalgamation of a star graph with a path graph ï¿½at a fixed vertex ï¿½and ï¿½is the magic sums of , then the magic sums are in closed interval

Proof. Based on Eq. (2.2), the magic sums ï¿½have a minimum number when the vertices with the highest degree are labeled with the smallest labels. Furthermore, by substituting Eq. (3.1) to Eq. (2.2) we get

Based on Eq. (2.2), the magic sums ï¿½have a minimum number when the vertices with the highest degree are labeled with the highest labels. Furthermore, by substituting Eq. (3.1) to Eq. (2.2) we get

Therefore, it is proved that ï¿½has magic sums in closed interval

b. Magic Sums of Broom Graph

Suppose ï¿½obtains a set of vertices and a set of edges

(3.2)

Theorem 3.2. Let ï¿½is a vertex amalgamation of a star graph with a path graph ï¿½and ï¿½is the magic sums of , then magic sums are in closed interval

Based on Eq. (2.2), the magic sums ï¿½have a minimum number when the vertices with the highest degree are labeled with the highest labels. Furthermore, by substituting Eq. (3.2) to Eq. (2.2) we get

Therefore, it is proved that ï¿½has magic sums in closed interval

c. Magic Sums of a Broom Graph

Suppose ï¿½obtains a set of vertices and a set of edges

(3.3)

Theorem 3.3. Let ï¿½is a vertex amalgamation of a star graph with a path graph ï¿½and ï¿½is the magic sums of , then magic sums are in closed interval

Proof. Based on Eq. (2.2), the magic sums ï¿½have a minimum number when the vertices with the highest degrees are labeled with the smallest labels. Furthermore, by substituting Eq. (3.3) to Eq. (2.2) we get

Furthermore, Based on Eq. (2.2), the magic sums ï¿½have a minimum number when the vertices with the highest degrees are labeled with the highest labels. Furthermore, by substituting Eq. (3.3) to Eq. (2.2) we get

Therefore, it is proved that ï¿½has magic sums in closed interval

d. Magic Sums of

Suppose ï¿½obtains a set of vertices and a set of edges

(3.4)

Theorem 3.4. Let ï¿½is a vertex amalgamation of a star graph with a path graph ï¿½at a fixed vertex ï¿½and ï¿½is the magic sums of , then the magic sums are in closed interval

Based on Eq. (2.2), the magic sums ï¿½have a minimum number when the vertices with the highest degree are labeled with the highest labels. Furthermore, by substituting Eq. (3.4) to Eq. (2.2) we get

Therefore, it is proved that ï¿½has magic sums in closed interval

3.3. ï¿½Edge-Magic Total Labelings on Vertex Amalgamation Graphs of a Star Graph with a Path ï¿½ï¿½ï¿½ï¿½Graph

In this section, the study will discuss about edge-magic total and super edge-magic total labelings on vertex amalgamation graphs of star graphs with path graphs .

a. Edges-Magic Total Labelings of a graph

There are two types of the edges-magic total labeling on a graph ï¿½as follows:

i. Edge-Magic Total Labeling of a Graph

Theorem 3.5. If , then the graph ï¿½has an edge-magic total labeling with .

Proof. Suppose ï¿½obtains a set of vertices and a set of edges

The cardinality of the vertex set and edge set are respectively and . Define a bijection ï¿½from ï¿½to ï¿½with the labelings as follows.

Because each edge holds . So, it is proved that for , then the graph ï¿½has an edge-magic total labeling with .

Figure 1. An EMTL of Amal (S_7;P_4,x_2 ) with the magic sum k=34.

ii. Super Edge-Magic Labeling of a graph

Theorem 3.6. If , then the graph ï¿½has an edge-magic total labeling with .

Proof. Suppose ï¿½obtains a set of vertices and a set of edges

The cardinality of the vertex set and edge set are respectively and . Define a bijection ï¿½from ï¿½to ï¿½with the labeling as follows.

10

3

9

1

4

7

6

5

8

2

Figure 2. A super EMTL of ï¿½with the magic sum .

11

12

13

14

17

18

19

15

16

Because ï¿½and each edge holds . So, it is proved that for , then the graph ï¿½has a super edge-magic total labeling with .

b. Edges-Magic Total Labelings of a Broom

There are two types of the edges-magic total labeling on a broom graph ï¿½as follows:

1. Edge-Magic Total Labeling of a Broom Graph ï¿½

Theorem 7: If , then the broom graph ï¿½has an edge-magic total labeling with .

Proof. Suppose ï¿½obtains a set of vertices and a set of edges

The cardinality of the vertex set and edge set are respectively and . Define a bijection ï¿½from ï¿½to ï¿½with the labeling as follows.

Because each edge holds . So, it is proved that for , then the broom graph ï¿½has an edge-magic total labeling with .

2. Super Edge-Magic Total Labeling of a broom Graph ï¿½

Theorem 3.8. If , then the broom graph ï¿½has a super edge-magic total labeling with .

Proof. Suppose the broom ï¿½obtains a set of vertices and a set of edges

The cardinality of the vertex set and edge set are respectively and . Define a bijection ï¿½from ï¿½to ï¿½with the labeling as follows.

Because ï¿½and each edge holds . So, it is proved that for , then the broom graph ï¿½has a super edge-magic total labeling with .

c. Edges-Magic Total Labelings of a Broom Graph

There are two types of the edges-magic total labeling on a broom graph ï¿½as follows:

1. Edge-Magic Total Labeling of a Broom Graph

Theorem 3.9. If , then the broom graph ï¿½has an edge-magic total labeling with .

Proof. Suppose the broom ï¿½obtains a set of vertices and a set of edges

The cardinality of the vertex set and edge set are respectively and . Define a bijection ï¿½from ï¿½to ï¿½with the labeling as follows.

Because each edge holds . So, it is proved that for , then the broom graph ï¿½has an edge-magic total labeling with .

2. Super Edge-Magic Total Labeling of a Broom Graph

Theorem 3.10. If , then the broom graph ï¿½has a super edge-magic total labeling with .

Proof. Suppose ï¿½obtains a set of vertices and a set of edges

The cardinality of the vertex set and edge set are respectively and . Define a bijection ï¿½from ï¿½to ï¿½with the labeling as follows.

Because ï¿½and each edge holds . So, it is proved that for , then the broom graph ï¿½has a super edge-magic total labeling with .

d. Edge-Magic Total Labeling of a Graph

There are two types of the edges-magic total labeling on a graph ï¿½as follows:

1. Edge-Magic Total Labeling of a Graph

Theorem 3.11. If , then the graph ï¿½has an edge-magic total labeling with .

Proof. Suppose the graph ï¿½obtains a set of vertices and a set of edges

The cardinality of the vertex set and edge set are respectively and . Define a bijection ï¿½from ï¿½to ï¿½with the labeling as follows.

Because each edge holds . So, it is proved that for , then the graph ï¿½has an edge-magic total labeling with .

2. Super Edge-Magic Total Labeling of a Graph

Theorem 3.12. If , then the graph ï¿½has a super edge-magic total labeling with .

Proof. Suppose the graph ï¿½obtains a set of vertices and a set of edges

The cardinality of the vertex set and edge set are respectively and . Define a bijection ï¿½from ï¿½to ï¿½with the labeling as follows.

Because ï¿½and each edge holds . So, it is proved that for , then the graph ï¿½has a super edge-magic total labeling with .

CONCLUSION

In this paper, we have given some solutions, to solve the edge-magic total and super edge-magic total labeling including intervals of the magic sums on vertex amalgamation graphs of a star graph ï¿½of order ï¿½with a path graph . However, it is very difficult to solve the labeling problem using traditional manual problem. Finally, we conclude that manual method to solve the labeling problem in this case proved to be totally effective. The authors would like to thank to the reviewers for helping comments and suggestions, which have improved the presentation. I personally would also like to show my deep appreciation to my supervisors who helped me finalize our study.

REFERENCES

Abu-Khzam, F. N., Egan, J., Gaspers, S., Shaw, A., & Shaw, P. (2018). Cluster editing with vertex splitting. International Symposium on Combinatorial Optimization, 1ï¿½13.

Andriollo, E., Secco, L., Caimo, A., & Pisani, E. (2023). Probabilistic network analysis of social-ecological relationships emerging from EU LIFE projects for nature and biodiversity: An application of ERGM models in the case study of the Veneto region (Italy). Environmental Science & Policy, 148, 103550.

Aytaï¿½, A. (2020). Relevant graph concepts for big data. Journal of Modern Technology and Engineering, 5(3), 255ï¿½263.

Bača, M., Miller, M., Ryan, J., & Semaničovï¿½-Feňovčï¿½kovï¿½, A. (2019). Magic and Antimagic Graphs. Attributes, Observations, and Challenges in Graph Labelings, Springer Nature Switzerland AG, Cham.

Chartrand, G., Egan, C., & Zhang, P. (2019). How to Label a Graph. Springer.

Chatterjee, A., Ghosal, S. K., & Sarkar, R. (2020). LSB based steganography with OCR: an intelligent amalgamation. Multimedia Tools and Applications, 79(17), 11747ï¿½11765.

Farahmand Asil, M. (2018). The Arithmetic of Graph Polynomials. UC Berkeley.

Lï¿½pez, S. C., Muntaner-Batle, F. A., Lï¿½pez, S. C., & Muntaner-Batle, F. A. (2017). Graphs Labelings. Graceful, Harmonious and Magic Type Labelings: Relations and Techniques, 15ï¿½31.

Mallik, A., & Ghosh, B. (2018). Scientometric analysis of research advancement in graph theory and its applications. COLLNET Journal of Scientometrics and Information Management, 12(2), 243ï¿½261.

Maowa, J. (2016). Study on graceful labeling of trees.

Marimuthu, G. T., & Kumar, G. (2015). Solution to some open problems on E-super vertex magic labeling of disconnected graphs. Applied Mathematics and Computation, 268, 657ï¿½663.

Mohan, P. (2019). Product of digraphs,(super) edge-magic valences and related problems.

Mondal, B., & De, K. (2017). An overview applications of graph theory in real field. International Journal of Scientific Research in Computer Science, Engineering and Information Technology, 2(5), 751ï¿½759.

Slater, P. J. (2016). It Is All Labeling. Graph Theory: Favorite Conjectures and Open Problems-1, 231ï¿½252.

Yao, B., & Wang, H. (2021). Recent Colorings And Labelings In Topological Coding. ArXiv Preprint ArXiv:2106.15254.

Copyright holder:

Selfa Suwandi, Nurdin, Muh. Nur (2024)

First publication right:

Journal of Social Science

This article is licensed under: