11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 k-LCM Cordial Labelling Kate Pauline B. Facto1*, Abraham P. Racca2 Adventist University of the Philippines kpbfacto@aup.edu.ph ABSTRACT This paper introduces the concept of -LCM cordial labelling, a graph labelling method evolving from cordial labelling, for connected and undirected simple , . 1,2,3, … , , each edge is Utilizing a function : → ℤ , where ∈ ℤ and ℤ assigned a label , mod , when and are adjacent vertices. A -LCM Cordial Labelling is defined by two conditions: ! maintaining an absolute difference of at most one in the count of vertices labelled with any ! and ",and !! likewise, providing an absolute difference of at most one in the count of edges labelled with ! and ",for all !, " ∈ ℤ# . A graph is said to be % LCM cordial graph if such a function exists. In our investigation of -LCM cordiality, we delve into various types and specific examples of graphs. Notably, we found that cyclic graphs # do not exhibit -LCM cordiality, whereas star graphs &# do. Furthermore, we examine the -LCM cordiality of lantern star graphs and connected copies of star graphs. Moreover, we investigated the influence of pendant vertices on -LCM cordiality. Keywords: Cordial Labelling, -Cordial Labelling, -LCM Cordial Labelling. INTRODUCTION In graph theory, a graph refers to a set of vertices and edges. These edges come in two distinct types: directed (weighted) and undirected (unweighted). In a directed graph, edges have direction, signifying a one-way relationship. Conversely, in an undirected graph, the edges denote a bidirectional relationship, allowing movement between vertices in both directions. In addition, there is a type of graph known as a “simple graph”. A simple graph has at most one edge between any pair of vertices and no loops, meaning no vertex connects to itself. The vertices can have varying orders. The concept of cordial labelling, introduced by Cahit in 1987, has been subject to substantial expansion over the years. Initially focused on assigning harmonious labels to graph vertices and edges, this concept evolved with Hovey’s (1991) introduction of -cordial graphs in 1991, providing a more generalized structure. The key findings that you expect to present in the article, giving the reader a preview of what to anticipate. A subsequent study by Maged Z. Youssef in 2009 expanded these ideas, introducing necessary conditions and new families of 4-cordial graphs. In this paper, we introduce the -LCM cordial labelling. Additionally, we note that hereℤ# 1,2,3, … , . 1412 11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 GRAPH PRELIMINARIES Within this chapter, we are going to define the structural characteristics inherent in the graphs underpinning this paper. Cycle Graph A cycle graph, denoted as ' , is defined as a graph comprising ( vertices embodying a closed loop. Formally, ' consists of a set of vertices ) , * , . . . , ' , where each vertex + is connected to its adjacent vertices in a circular sequence, thus establishing a cycle. Conventionally, vertex + is connected to both + , 1 and + % 1 for ! 1,2, . . . , ( , with indices taken modulo ( to ensure the closure of the cycle. It is worth noting that cycle graphs are defined for ( - 3, a minimum of three vertices is necessary to form a cycle. Additionally, each vertex in a cycle graph has a degree of two, signifying that it is connected to precisely two edges. Wheel Graph A wheel graph, denoted as .' , emerges from the combination of a central vertex with a cycle graph '/) , followed by connecting the central vertex to all the vertices in '/) . Consequently,.' consists of ( vertices and 2 ( % 1 edges. It is worth noting that the central vertex has a degree of (, reflecting its connection to the remaining vertices, while each of the vertices within '/) maintains a degree of three due to their connection to the central vertex and the two adjacent vertices. Complete Graph A complete graph, denoted as 0' , is a graph where every pair of distinct vertices is connected by a single edge, achieving maximal connectivity with a degree of ( % 1, it does not necessarily ' '/) arise from a cycle graph. With ( vertices, it contains * edges. Notably, 0' is also a planar graph for ( 1 4, meaning it can be represented on a plane without any edge intersecting. Below are some of graphs depicting a complete graph, providing a clearer understanding. Figure 1. Examples of 0' Path Graph 1413 11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 A path graph, denoted as 3' , is a linear sequence of vertices connected by edges. With a core principle of simplicity, each vertex is connected to the next vertex by a single edge. The path length corresponds directly to the size of the edges, while the endpoints signify its discontinuity. Star Graph A star graph, denoted as &' , is a distinctive type of a tree graph characterizing a central vertex connected to ( peripheral vertices. With ( , 1 vertices and ( edges, the central vertex has a degree of (,while the peripheral vertices each have a degree of one. Tadpole Graph The tadpole graph, denoted as 4',5 , emerges by amalgamating a path graph 35 with a cycle graph ' , where one end of the path connects to the cycle, forming a distinctive “tadpole” shape. With ( , 6 vertices and edges. Below are some examples of tadpole graph, providing a clearer understanding. Figure 2. Examples of Tadpole Graph Bridge A bridge is defined as an edge that upholds the connectivity of the distinct components of a graph. Its removal would result in a disconnection in the graph, partitioning into two or more disjoint subgraphs. However, it is noteworthy that the addition of a bridge nullifies the effect of the first bridge. Consequently, the presence or absence of bridges affects the structural coherence and connectivity within a graph. K-LCM C789:;< <;=><<:?@ 1414 11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 We now present the -LCM cordial labelling and classify - LCM cordiality of some graphs. Definition 1 Let , be a graph and : → 1,2,3, … , . The induced % ∗ ∗ LCM edge labelling : → 1,2,3, . . . , is given by E /) , 6FG for an edge E . Here, ! refers to the set of vertices ∗ /) labelled with !, and ! refers to the set of edges with induced labelling !. The counts of vertices and edges with labels ! HℎEJE ! 1,2,3, . . . , are denoted as K ! and EK ! , respectively. A % LCM labelling of a graph G is said to be % LCM cordial if the following conditions are met: ! For any !, ", 1 1 !, " 1 L K ! % K " L 1 1, and !! For any !, ", 1 1 !, " 1 LEK ! % EK " L 1 1. To discuss examples, let us take a look at some connected graphs on four vertices. Figure 3. Connected graphs with 4 vertices On the next page, our objective is to investigate the -LCM Cordiality of the graphs is presented in Figure 4. Recall that 3M and &M are path and star graphs, respectively. We assert that they are 4-LCM cordial graphs. We will mention some insights into why 4N,) , .M , being -LCM Cordial graph. M, M , and 0M failed to meet the criteria for Proposition 1 The tadpole graph 4N,) is not a 4-LCM cordial graph. 1415 11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 3JFF . Consider the Tadpole graph 4N,) which consists of a cycle with 3 vertices (the “body”) and one pendant vertex (the “tail”). In this graph, L 4N,) L 4 and L 4N,) L 4. Hence, to be 4-LCM Cordial, there must exist a function : 4N,) → ℤM such that | /) 4 | 1. However, finding such labelling within 4N,) is impossible. Considering the function : 4N,) → 1,2,3,4 , placing M as a pendant vertex, it emerges as the sole option to be labeled as 4 to prevent the formation of two edges with induced labeling 4. Let us proceed to evaluate the labelling below if we choose * to be adjacent to M . Let us shift our focus to the remaining vertices, denoted by Figure 4. 4N,) with label 4 ) and N , as shown in Figure 6. Figure 5. 4N,) with label 4 & 2 Note that * will inevitably be adjacent to both ) and N ,which will be labeled l or 3, thereby resulting in ∗ /) 2 2. Similarly, regardless of whether ) and N come from 1 or 2, it is Figure 6. Illustrated labelled vertices inevitably a consequence that ∗ /) 2 equals 2. This observation strengthens the argument against 4N,) being a 4-LCM Cordial Graph. Proposition 2 The cyclic graph cordial graph. M is not a 4-LCM 3JFF . Notice that in any case of labeling, the vertex labeled with 4 will always be adjacent to the other two vertices. Hence there will be two edges with induce labeling 4. See for example the labelling in Figure 7. Proposition 3 The graphs GM , 0M , P(G .M are not 4LCM cordial graphs. Figure 7. M with labelled vertices 1416 11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 Cycle Spanning Subgraph 3JFF . As previously proven, aFigure cycle 8.graph of a pendant vertex cannot be 4-LCM M devoid Cordial. Consequently, considering the inclusion of M as a subgraph, hence, M , 0M ,and .M do not possess the property of being 4-LCM cordial graphs. We shall now look at more general results. Theorem 1 Cycle # is not a k-LCM cordial graph. 3JFF . Since every vertex of ∃ ! such that ∗ /) ! ∅. # is of order 2 then | ∗ /) | 2. Since | |1| | and suppose that : Theorem 2 Let G be a graph with | | |. If is a k-LCM cordial labelling of G then the sole element of pendant of G. # | then → ℤ# with must be a /) | 3JFF . Assume that constitutes a -LCM cordial labelling of . Since | and /) : → ℤ# , is a one-to-one mapping. If, in case, is not a pendant, then there will be at least two edges with induced labeling . This is not possible, since is -LCM cordial |1| | and | ,a contradiction. Theorem 3 Star Graph &# is a k-LCM Cordial Graph. 3JFF . Consider the following labelling in Figure 9. Notice that a star graph has a central vertex connected to a peripheral vertex, creating a star-like pattern with % 1 pendant vertices. The labelling of the vertices and edges in this figure exemplifies a %LCM cordial labelling. Figure 9. Graph &# 1417 11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 Theorem 4 The Lantern Star graph denoted by & # is a k-LCM Cordial Graph. Figure 10. Graph & # 3JFF . Let the Lantern Star graph & # , defined by amalgamating a star graph &' to a path graph 3* with a bridge. Here, 3* formed by #/) and # , with the bridge being the edge connecting the central vertex and #/) . | - . If 6 , 1 is a prime Theorem 5. Let be a connected graph on vertices with | number for 1 1 6 1 % 1, then is not a -LCM Cordial Graph. 3JFF . Consider the scenario where 6 ⋅ , 1 is prime for 1 1 6 1 % 1. Let : → ℤ# be a labelling function. For !, " ∈ ℤ# with ! T ", assume 6 satisfies 1 1 6 1 % 1 and that 6 ⋅ , 1 is prime. This implies that no edge in can have an induced label of 1. The reasoning behind this is that is not a prime number, and 6 ⋅ , 1 is always a prime number due to the assumed conditions. Additionally, adding 1 to 6 ⋅ ensures that the resulting number is not divisible by . If 6 ⋅ , 1 is prime, it implies that LCM , T 1 mod does not exist !, " ∈ ℤ# such that LCM + , U ≡ 1 mod . . Consequently, there The contradiction arises from the existence of two edges in with the same induced labelling, violating the requirements of -LCM Cordial labelling, which mandates distinct labels for each edge. This contradiction leads to the conclusion that the conditions for a -LCM Cordial labelling is not satisfied, establishing that is not a -LCM Cordial Graph. 1418 11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 We will now consider -LCM cordial labeling where 1| |. Theorem 6. A connected 6 % WFX!EY star graph &5,' is an 6-LCM Cordial graph. 3JFF . Considering the labeling of the figure on the next page, observe that | /) ! | Figure 11. Graph & # 6 % 1 1 | ∗ /) ! | 1 6 for any !, 1 1 ! 1 6. 6 and Theorem 7. An 6-connected Star-cycle graph & 5,' is an 6-LCM Cordial graph. Figureabove, 12. m-connected Graph ! | 3JFF . Considering the labeling observeStar-cycle that | /) !, 1 1 ! 1 6. | ∗ /) ! | 6 for any CONCLUSION AND RESEARCH DIRECTION In conclusion, the concept of -LCM cordial labelling for connected undirected simple graphs have successfully been explored and has been introduced. We have defined the method 1419 11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 and established conditions for -LCM cordial labelling, elucidating its properties through comprehensive examples including cyclic graphs, star graphs, a lantern star graph, and configuration of connected copies of star graphs. The particular significance of our discovery is the consistency of star graphs as -LCM cordial, underlining their relevance within the structure. Additionally, we have uncovered the impact of pendant vertices in determining a graph’s -LCM cordiality, exemplified by the absence of such vertices in cyclic graphs leads to their insufficiency to the conditions. Numerous future research directions could include:  Structural Patterns and Dynamics: Examine structural patterns of cordial graphs, including vertex labels, degree distribution, and connectivity, to uncover connections between the graph structure and -LCM cordiality. Study how -LCM cordial labelling evolves under graph operations like edge additions, deletions, or vertex contractions.  Algorithm Development and Uncertainty Analysis: Enhancing algorithms and assessing the computational complexity of determining -LCM cordial labelling across diverse graph classes could facilitate applications in graph theory and related domains. Additionally, expanding the algorithmic structure through conducting probabilistic analysis explores the uncertainty of randomly generated graphs in exhibiting -LCM cordiality. In generating graphs, verify -LCM cordiality, and analyze probabilities with structural properties to understand when this property occurs and its implications for graph theory and applications.  Complementary Graphs: Explore the conditions under which the complement of a kLCM cordial graph also exhibits k-LCM cordiality.  Graph Fusion  Bridge Addition and -LCM graphs: Exploring how adding a bridge between % copies or different types) graphs affect their -LCM cordiality. Explore under what conditions the resulting graph maintains - LCM cordiality, and how this fusion influences this property.  Amalgamation of Non-cordial Graphs: Explore whether a fusion of non-cordial graphs via a bridge produces a -LCM graph. Investigate the necessary conditions for this and develop algorithms to identify suitable bridge configurations.  Extension to Weighted Graphs: Extend the amalgamation to directed or weighted graphs. Investigate how edge weights influence the preservation of -LCM cordiality properties during amalgamation. In summary, by pursuing these research directions, we aim to enrich our understanding of k-LCM cordial labelling, exploring its complexity, properties, and connections. 1420 11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 1421 11th ISC 2024 (Universitas Advent Indonesia, Indonesia) “Research and Education Sustainability: Unlocking Opportunities in Shaping Today's Generation Decision Making and Building Connections” October 22-23, 2024 REFERENCES Cahit, I. (1987). Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs. Ars Combinatoria - Waterloo then Winnipeg-, 23, 201-208. Harary, F., & Palmer, E. M. (1973). Graphical Enumeration. Academic Press, INC. West, D. B. (2001). Introduction to Graph Theory, 2'Z G![!F(. Pear Education, Inc. Harary, F. (1996). JPXℎ Theory. Addison- Wesley Publishing Company, Inc. Chartrand, G., & Lesniak, L. (1996). Graphs & Digraphs, 3\Z G![!F(. Champman & Hall/CRC. Youssef, M. Z. (2009). On -cordial labelling. Australasian Journal of Combinatorics, 43, 31- 37. Hovey, M. (1991). A-cordial graphs. Discrete Mathematics, 93(2-3), 183-194. ISSN 0012-365X. doi=10.1016/0012-365X(91)90254-Y 1422