Next Article in Journal
Guaranteed Diversity and Optimality in Cost Function Network Based Computational Protein Design Methods
Previous Article in Journal
Efficient and Scalable Initialization of Partitioned Coupled Simulations with preCICE
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

The Locating-Chromatic Number of Origami Graphs

1
Department of Mathematics, Universitas Lampung, Bandar Lampung 35145, Indonesia
2
Information System, STMIK Pringsewu, Lampung 35373, Indonesia
3
Department of Computer Science, Universitas Lampung, Bandar Lampung 35145, Indonesia
*
Author to whom correspondence should be addressed.
Submission received: 26 April 2021 / Revised: 20 May 2021 / Accepted: 26 May 2021 / Published: 27 May 2021
(This article belongs to the Section Combinatorial Optimization, Graph, and Network Algorithms)

Abstract

:
The locating-chromatic number of a graph combines two graph concepts, namely coloring vertices and partition dimension of a graph. The locating-chromatic number is the smallest k such that G has a locating k-coloring, denoted by χ L ( G ) . This article proposes a procedure for obtaining a locating-chromatic number for an origami graph and its subdivision (one vertex on an outer edge) through two theorems with proofs.
MSC:
05C12; 05C15

1. Introduction

The study of the partition dimension of connected graphs was introduced by Chartrand et al. [1,2] with the aim of finding a new method for attacking the problem of determining the metric dimension in graphs. The application of these metric dimensions can be seen in the navigation of a robot modeled by a graph [3,4], solving the problem of chemical data classification, and determining how to represent a set of chemical compounds in such a way that different compounds have different representations [5,6]. The concept of the locating-chromatic number was first introduced by Chartrand et al. in 2002, with two obtained graph concepts, namely coloring vertices and partition dimensions of a graph [7]. Finding the locating-chromatic number of a graph is one of the interesting (and un-completely solved) problems of graph theory. Let G = ( V , E ) be a connected graph; the distance d ( x , y ) between two of its vertices x and y is the length of the shortest path between them. Let c be a proper k-coloring of G with color { 1 , 2 , , k } , and Π = { C 1 , C 2 , , C k } be a partition of V ( G ) that is induced by the coloring c. The color code c Π ( v ) of v is the ordered k-tuple ( d ( v , C 1 ) , d ( v , C 2 ) , , d ( v , C k ) ) ) , where d ( v , C i ) = min { d ( v , x ) : x C i } for any i { 1 , 2 , 3 , , k } . If all distinct vertices of G have distinct color codes, then c is called a k-locating coloring of G. The locating-chromatic number denoted by χ L ( G ) is the smallest k such that G has a locating k-coloring. Let c be a locating k-coloring on graph G ( V , E ) . Furthermore, the locating-chromatic number has been determined for a few graph classes; for example, if P n is a path of order n 3 then the locating-chromatic number is 3; for a cycle C n if n 3 is odd, χ L ( C n ) = 3 was obtained, and if n is even, χ L ( C n ) = 4 was obtained; for a double star graph ( S a , b ) , 1 a b and b 2 , χ L ( S a , b ) = b + 1 was obtained. Let Π = { S 1 , S 2 , , S k } be the partition of V ( G ) induced by c. A vertex v G is called a dominant vertex if d ( v , S i ) = 1 , where v S i . Chartrand et al. characterized all graphs of order n with the locating-chromatic number n 1 [8].
The problem of determining the locating-chromatic number of any general graph is an NP-hard problem [9]. This means that to determine the locating-chromatic number of any given graph, we need a specific algorithm. In 2012, Baskoro and Purwasih proposed a procedure to obtain the locating-chromatic number of corona products of two graphs [9]. In 2014, Asmiati obtained the locating-chromatic number of a non-homogeneous amalgamation of stars [10]. Moreover, to determine the locating-chromatic number of disconnected graphs, graphs with dominant vertices and graphs of two components have been discussed in [11,12,13]. In 2019, the characterization of the locating chromatic number of powers of paths and a condition (sharp upper and lower bounds) for the locating chromatic number of powers of cycles were discussed [14] (see [15] for a discussion of the necessary and sufficient conditions for a pair of two specific start graphs to be an odd mean graph). Asmiati et al. determined the locating-chromatic number of some Petersen graphs; P ( n , 1 ) four for odd n 3 or five for even n 4 were obtained [16], and in [17] results were obtained for certain barbell graphs. Syofyan et al. have succeed in determined the locating-chromatic number of homogeneous lobsters [18]. In [19], Asmiati obtained the locating-chromatic number for non-homogeneous caterpillar graphs and non-homogeneous firecracker graphs. Next, Irawan and Asmiati in 2018 determined the locating-chromatic number of subdivision firecrackers graphs [20] and in [21] obtained the certain operation of generalized Petersen graphs s P ( n , 1 ) . In 2014, Behtoei and Anbarloei determined the locating-chromatic number of the joining of two arbitrary graphs [22]. In addition to that, in this article we propose a procedure for obtaining the locating-chromatic number for an origami graph and its subdivision (one vertex on an outer edge). The following definition of an origami graph is taken from [23]. Let n N with n 3 . An origami graph O n is a graph with V ( O n ) = { u i , v i , w i : i { 1 , , n } } and E ( O n ) = { u i w i , u i v i , v i w i : i { 1 , , n } } { u i u i + 1 , w i u i + 1 : i { 1 , , n 1 } } { u n u 1 , w n u 1 } (see Figure 1 for an example). Meanwhile, a subdivision of an origami graph O n is a graph with V ( O n ) = { u i , v i , x i , w i : i { 1 , , n } } and E ( O n ) = { u i w i , u i v i , v i x i , x i w i : i { 1 , , n } } { u i u i + 1 , w i u i + 1 : i { 1 , , n 1 } } { u n u 1 , w n u 1 } } (see Figure 2 for an example).

2. Results and Discussions

Let c be a locating coloring in a connected graph G and N ( q ) denote the set of neighbor of a vertex q in G. If p and q are distinct vertices of G such that d ( p , w ) = d ( q , w ) for all w V ( G ) { p , q } , then c ( p ) c ( q ) . In particular, if p and q are non-adjacent vertices such that N ( p ) = N ( q ) , then c ( p ) c ( q ) [7].
In the following subsection, the locating-chromatic number of origami graphs O n and their subdivisions called O n is described.

2.1. Locating-Chromatic Number of Origami Graphs

Theorem 1.
Let O n be an origami graph for n 3 . Then, the locating-chromatic number of O n ,
χ L ( O n ) = 4 , f o r n = 3 5 , o t h e r w i s e .
Proof. 
Let n N with n 3 . An origami graph O n is a graph with V ( O n ) = { u i , v i , w i : i { 1 , , n } } and E ( O n ) = { u i w i , u i v i , v i w i : i { 1 , , n } } { u i u i + 1 , w i u i + 1 : i { 1 , , n 1 } } { u n u 1 , w n u 1 } . Next, to prove the theorem, we consider the following two cases:
Case 1. 
χ L ( O 3 ) = 4
First, we determine the lower bound of χ L ( O 3 ) . In the origami graphs O n for n 3 , there are three adjacent vertices (complete graph with three vertices, denoted by K 3 ); we then need at least 3-locating coloring. Without loss of generality, we assign three colors for any K 3 in O n for n 3 , and then the three vertices are dominant vertices. As a result, if we use three colors it is not enough because there are more than one K 3 in O n for n 3 . Therefore, χ L ( O 3 ) 4 .
Next, we determine the upper bound of χ L ( O 3 ) 4 . To show that 4 is an upper bound for the locating-chromatic number for the origami graph O 3 we describe a locating coloring c using four colors as follows:
  • c ( u i ) = i , i = 1 , 2 , 3 .
  • c ( v i ) = 2 , f o r i = 1 , 3 3 , f o r i = 2 .
  • c ( w i ) = 4 , i = 1 , 2 , 3 .
The coloring c will create the partition Π on V ( O 3 ) . We shall show that the color codes of all vertices in O 3 are different. We have: c Π ( u 1 ) = ( 0 , 1 , 1 , 1 ) ; c Π ( u 2 ) = ( 1 , 0 , 1 , 1 ) ; c Π ( u 3 ) = ( 1 , 1 , 0 , 1 ) ; c Π ( v 1 ) = ( 1 , 0 , 2 , 1 ) ; c Π ( v 2 ) = ( 2 , 1 , 0 , 1 ) ; c Π ( v 3 ) = ( 2 , 0 , 1 , 1 ) ; c Π ( w 1 ) = ( 1 , 1 , 2 , 0 ) ; c Π ( w 2 ) = ( 2 , 1 , 1 , 0 ) ; c Π ( w 3 ) = ( 1 , 1 , 1 , 0 ) . Since the color codes of all vertices O 3 are different, c is a locating-chromatic coloring. Thus, χ L ( O 3 ) 4 .
Case 2. 
χ L ( O n ) = 5 , for n 4
To determine the lower bound, we will show that four colors are not enough. For a contradiction, assume that there exists a 4-locating coloring c on O n for n 4 . We assign { c ( u i ) , c ( v i ) , c ( w i ) , c ( u i + 1 ) } = { 1 , 2 , 3 , 4 } , where c ( v i ) c ( u i + 1 ) because d ( v i , x ) = d ( u i + 1 , x ) , x { u i , v i } . Observe that, on O n for n 4 , there are n vertices u i whose degree is 5. As a result, at least two vertices w k , w l , k l have the same color codes, which is a contradiction. Therefore, χ L ( O n ) 5 , for n 4 .
To show the upper bound for the locating-chromatic number of origami graphs O n for n 4 , let us differentiate some subcases.
Subcase 1. 
(Odd n), for n 2 odd, n 5
Let c be a coloring of origami graph O n , n 2 odd, and n 5 ; we make the partition Π of V ( O n ) :
  • C 1 = { w i | 1 i n } ;
  • C 2 = { u i | for odd i , 3 i n } { v i | for even i , 2 i n 1 } ;
  • C 3 = { u i | for even i , 2 i n 2 1 } { u i | for even i , n 2 + 3 i n 1 } { v i | for odd i , 1 i n } ;
  • C 4 = { u 1 } ;
  • C 5 = { u n 2 + 1 } .
For n 2 odd, the color codes of all the vertices of V ( O n ) are:
  • C 1 = { w i | 1 i n } .
For i = 1 , we have:
c Π ( w i ) = ( 0 , 2 , 1 , i , n 2 i + 1 ) .
For 2 i n 2 , n 5 we have:
c Π ( w i ) = ( 0 , 1 , 1 , i , n 2 i + 1 ) .
For i = n 2 + 1 we have:
c Π ( w i ) = ( 0 , 1 , 2 , n i + 1 , i n 2 ) .
For n 2 + 2 i n , n 5 we have:
c Π ( w i ) = ( 0 , 1 , 1 , n i + 1 , i n 2 ) .
C 2 = { u i | for odd i , 3 i n } { v i | for even i , 2 i n 1 } .
For i odd, 3 i n 2 , n 5 we have:
c Π ( u i ) = ( 1 , 0 , 1 , i 1 , n 2 i + 1 ) .
For i odd, n 2 + 2 i n , n 5 we have:
c Π ( u i ) = ( 1 , 0 , 1 , n i + 1 , i n 2 1 ) .
For i even, 2 i n 2 1 , n 5 we have:
c Π ( v i ) = ( 1 , 0 , 1 , i , n 2 i + 2 ) .
For i = n 2 + 1 , we have:
c Π ( v i ) = ( 1 , 0 , 3 , n i + 2 , 1 ) .
For i even, n 2 + 3 i n 1 , n 9 we have:
c Π ( v i ) = ( 1 , 0 , 1 , n i + 2 , i n 2 ) .
C 3 = { u i | for even i , 2 i n 2 1 } { u i | for even i , n 2 + 3 i n 1 } { v i | for odd i , 1 i n } .
For i = 1 , we have:
c Π ( v i ) = ( 1 , 2 , 0 , i , n 2 ) .
For i odd, 3 i n 2 , n 5 we have:
c Π ( v i ) = ( 1 , 1 , 0 , i , n 2 i + 2 ) .
For i odd, n 2 + 2 i n , n 9 we have:
c Π ( v i ) = ( 1 , 1 , 0 , n i + 2 , i n 2 ) .
For i even, 2 i n 2 1 , n 5 we have:
c Π ( u i ) = ( 1 , 1 , 0 , i 1 , n 2 i + 1 ) .
For i even, n 2 + 3 i n 1 , n 9 we have:
c Π ( u i ) = ( 1 , 1 , 0 , n i + 1 , i n 2 1 ) .
For C 4 = { u 1 } , we have:
c Π ( u 1 ) = ( 1 , 1 , 1 , 0 , n 2 1 ) .
For C 5 = { u n 2 + 1 } , we have:
c Π ( u n 2 + 1 ) = ( 1 , 1 , 2 , n 2 1 , 0 ) .
Since for n odd all vertices have different color codes, c is a locating coloring of origami graphs O n , so that χ L ( O n ) 5 , for n 2 odd, n 5 .
Subcase 2. 
(Odd n), for n 2 even, n 7 .
Let c be a coloring of origami graph O n , n 2 even, and n 7 ; we make the partition Π of V ( O n ) as follows:
  • C 1 = { w i | 1 i n } ;
  • C 2 = { u i | for odd i , 3 i n } { v i | for even i , 2 i n 1 } ;
  • C 3 = { u i | for even i , 2 i n 2 2 } { u i | for even i , n 2 + 2 i n 1 } { v i | for odd i , 1 i n } ;
  • C 4 = { u 1 } ;
  • C 5 = { u n 2 } .
For n 2 even, the color codes of all the vertices of V ( O n ) are:
  • C 1 = { w i | 1 i n } .
For i = 1 , we have:
c Π ( w i ) = ( 0 , 2 , 1 , i , n 2 i ) .
For 2 i n 2 1 , n 7 we have:
c Π ( w i ) = ( 0 , 1 , 1 , i , n 2 i ) .
For i = n 2 , we have:
c Π ( w i ) = ( 0 , 1 , 2 , n i + 1 , i n 2 + 1 ) .
For n 2 + 1 i n , n 7 we have:
c Π ( w i ) = ( 0 , 1 , 1 , n i + 1 , i n 2 + 1 ) .
C 2 = { u i | for odd i , 3 i n } { v i | for even i , 2 i n 1 } .
For i odd, 3 i n 2 1 , n 7 we have:
c Π ( u i ) = ( 1 , 0 , 1 , i 1 , n 2 i ) .
For i odd, n 2 + 1 i n , n 7 we have:
c Π ( u i ) = ( 1 , 0 , 1 , n i + 1 , i n 2 ) .
For i even, 2 i n 2 2 , n 7 we have:
c Π ( v i ) = ( 1 , 0 , 1 , i , n 2 i + 1 ) .
For i = n 2 , we have:
c Π ( v i ) = ( 1 , 0 , 3 , i , i n 2 + 1 ) .
For i even, n 2 + 3 i n 1 , n 7 we have:
c Π ( v i ) = ( 1 , 0 , 1 , n i + 2 , i n 2 + 1 ) .
C 3 = { u i | for even i , 2 i n 2 2 } { u i | for even i , n 2 + 2 i n 1 } { v i | for odd i , 1 i n } .
For i = 1 we have:
c Π ( v i ) = ( 1 , 2 , 0 , i , n 2 i + 1 ) .
For i odd, 3 i n 2 1 , n 7 we have:
c Π ( v i ) = ( 1 , 1 , 0 , i , n 2 i + 1 ) .
For i odd, n 2 + 1 i n , n 7 we have:
c Π ( v i ) = ( 1 , 1 , 0 , n i + 2 , i n 2 + 1 ) .
For i even, 2 i n 2 2 , n 7 we have:
c Π ( u i ) = ( 1 , 1 , 0 , i 1 , n 2 i ) .
For i even, n 2 + 2 i n , n 7 we have:
c Π ( u i ) = ( 1 , 1 , 0 , n i + 1 , i n 2 ) .
C 4 = { u 1 } , we have:
c Π ( u 1 ) = ( 1 , 1 , 1 , 0 , n 2 1 ) .
C 5 = { u n 2 } , we have:
c Π ( u n 2 ) = ( 1 , 1 , 2 , n 2 1 , 0 ) .
Since for n odd all vertices have different color codes, c is a locating coloring of origami graphs O n , so that χ L ( O n ) 5 , for n 2 even, n 7 .
Subcase 3. 
(even n), for n 2 odd, n 6 .
Let c be a coloring of origami graph O n , n 2 odd, and n 6 ; we make the partition Π of V ( O n ) :
  • C 1 = { w i | 1 i n 2 1 } { w i | n 2 + 1 i n } ;
  • C 2 = { u i | for odd i , 3 i n 1 } { v i | for even i , 2 i n } ;
  • C 3 = { u i | for even i , 2 i n } { v i | for odd i , 1 i n 1 } ;
  • C 4 = { u 1 } ;
  • C 5 = { w n 2 } .
For n 2 odd, the color codes of all the vertices of V ( O n ) are:
C 1 = { w i | 1 i n 2 1 } { w i | n 2 + 1 i n } .
For i = 1 , we have:
c Π ( w i ) = ( 0 , 2 , 1 , i , n 2 i + 1 ) .
For 2 i n 2 1 , n 6 we have:
c Π ( w i ) = ( 0 , 1 , 1 , i , n 2 i + 1 ) .
For n 2 + 1 i n , n 6 we have:
c Π ( w i ) = ( 0 , 1 , 1 , n i + 1 , i n 2 + 1 ) .
C 2 = { u i | for odd i , 3 i n 1 } { v i | for even i , 2 i n } .
For i odd, 3 i n 2 , n 6 we have:
c Π ( u i ) = ( 1 , 0 , 1 , i 1 , n 2 i + 1 ) .
For i odd, n 2 + 2 i n 1 , n 6 we have:
c Π ( u i ) = ( 1 , 0 , 1 , n i + 1 , i n 2 ) .
For i even, 2 i n 2 1 , n 6 we have:
c Π ( v i ) = ( 1 , 0 , 1 , i , n 2 i + 2 ) .
For i even, n 2 + 1 i n 1 , n 6 we have:
c Π ( v i ) = ( 1 , 0 , 1 , n i + 2 , i n 2 + 1 ) .
C 3 = { u i | for even i , 2 i n } { v i | for odd i , 1 i n 1 } .
For i = 1 , we have:
c Π ( v i ) = ( 1 , 3 , 0 , i , n 2 i + 2 ) .
For i odd, 3 i n 2 2 , n 10 we have:
c Π ( v i ) = ( 1 , 1 , 0 , i , n 2 i + 2 )
For i = n 2 , we have:
c Π ( v i ) = ( 2 , 1 , 0 , i , 1 ) .
For i odd, n 2 + 2 i n 1 , n 6 we have:
c Π ( v i ) = ( 1 , 1 , 0 , n i + 2 , i n 2 + 1 ) .
For i even, 2 i n 2 1 , n 6 we have:
c Π ( u i ) = ( 1 , 1 , 0 , i 1 , n 2 i + 1 ) .
For i even, n 2 + 1 i n , n 6 we have:
c Π ( u i ) = ( 1 , 1 , 0 , n i + 1 , i n 2 ) .
For C 4 = { u 1 } , we have:
c Π ( u 1 ) = ( 1 , 2 , 1 , 0 , n 2 i + 1 ) .
For C 5 = { w n 2 } , we have:
c Π ( w n 2 ) = ( 2 , 1 , 1 , n 2 , 0 ) .
Since for n even all vertices have different color codes, c is a locating coloring of origami graphs O n , so that χ L ( O n ) 5 , for n 2 odd, n 6 .
Subcase 4. 
(even n), for n 2 even, n 4 .
Let c be a coloring of origami graph O n , n 2 even, and n 4 ; we make the partition Π of V ( O n ) as follows:
  • C 1 = { w i | 1 i n 2 } { w i | n 2 + 2 i n } ;
  • C 2 = { u i | for odd i , 3 i n 1 } { v i | for even i , 2 i n } ;
  • C 3 = { u i | for even i , 2 i n } { v i | for odd i , 1 i n 1 } ;
  • C 4 = { u 1 } ;
  • C 5 = { w n 2 + 1 } .
For n 2 even, the color codes of all the vertices of V ( O n ) are:
C 1 = { w i | 1 i n 2 } { w i | n 2 + 2 i n } .
For i = 1 we have:
c Π ( w i ) = ( 0 , 2 , 1 , i , n 2 i + 2 ) .
For 2 i n 2 , n 4 we have:
c Π ( w i ) = ( 0 , 1 , 1 , i , n 2 i + 2 ) .
For n 2 + 2 i n , n 4 we have:
c Π ( w i ) = ( 0 , 1 , 1 , n i + 1 , i n 2 ) .
C 2 = { u i | for odd i , 3 i n 1 } { v i | for even i , 2 i n } .
For i odd, 3 i n 2 + 1 , n 8 we have:
c Π ( u i ) = ( 1 , 0 , 1 , i 1 , n 2 i + 2 ) .
For i odd, n 2 + 3 i n 1 , n 8 we have:
c Π ( u i ) = ( 1 , 0 , 1 , n i + 1 , i n 2 1 ) .
For i even, 2 i n 2 , n 4 we have:
c Π ( v i ) = ( 1 , 0 , 1 , i , n 2 i + 3 ) .
For i even, n 2 + 2 i n , n 8 we have:
c Π ( v i ) = ( 1 , 0 , 1 , n i + 2 , i n 2 ) .
C 3 = { u i | for even i , 2 i n } { v i | for odd i , 1 i n 1 } .
For i = 1 , we have:
c Π ( v i ) = ( 1 , 3 , 0 , 1 , n 2 + 1 ) .
For i odd, 3 i n 2 1 , n 8 we have:
c Π ( v i ) = ( 1 , 1 , 0 , i , n 2 i + 3 ) .
For i = n 2 + 1 , we have:
c Π ( v i ) = ( 2 , 1 , 0 , i , 1 ) .
For i odd, n 2 + 3 i n 1 , n 8 we have:
c Π ( v i ) = ( 1 , 1 , 0 , n i + 2 , i n 2 ) .
For i even, 2 i n 2 , n 4 we have:
c Π ( u i ) = ( 1 , 1 , 0 , i 1 , n 2 ) .
For i even, n 2 + 2 i n , n 8 we have:
c Π ( u i ) = ( 1 , 1 , 0 , n i + 1 , i n 2 1 ) .
For C 4 = { u 1 } , we have:
c Π ( u 1 ) = ( 1 , 2 , 1 , 0 , n 2 ) .
For C 5 = { w n 2 } , we have:
c Π ( w n 2 ) = ( 2 , 1 , 1 , n 2 , 0 ) .
Since for n even all vertices have different color codes, c is a locating coloring of origami graphs O n , so that χ L ( O n ) 5 , for n 2 even, n 4 . this completes the proof of Theorem 1. □
Note that Figure 1 is an example locating coloring for origami graph O 5 .

2.2. Locating-Chromatic Number for Subdivision Outer Edge of Origami Graphs

Theorem 2.
Let O n be a subdivision outer edge of origami graphs for n 3 . Then the locating-chromatic number of O n , χ L ( O n ) = 4 , f o r n = 3 5 , o t h e r w i s e .
Proof. 
Let O n , n 3 be a subdivision of an origami graph; O n is a graph with V ( O n ) = { u i , v i , x i , w i : i { 1 , , n } } and E ( O n ) = { u i w i , u i v i , v i x i , x i w i : i { 1 , , n } } { u i u i + 1 , w i u i + 1 : i { 1 , , n 1 } } { u n u 1 , w n u 1 } }. Next, to prove the theorem, we consider the following two cases:
Case A. 
χ L ( O 3 ) = 4
First, we determine the lower bound of χ L ( O 3 ) .
Without loss of generality, we assign A = { c ( u i ) , c ( v i ) , c ( x i ) , c ( w i ) , c ( u i + 1 ) } = { 1 , 2 , 3 } . Then, there are three dominant vertices in A, while we still have vertices on other A that must be colored. As a result, there will be two vertices with the same color codes. Thus, χ L ( O 3 ) 4 .
Next, we determine the upper bound of χ L ( O 3 ) 4 . To show that 4 is an upper bound for the locating-chromatic number for a subdivision outer edge of origami graph O 3 , we describe a locating coloring c using four colors as follows:
c ( u i ) = i , i = 1 , 2 , 3 .
c ( v i ) = 2 , f o r i = 1 , 3 3 , f o r i = 2 .
c ( w i ) = 4 , i = 1 , 2 , 3 .
c ( x i ) = i , i = 1 , 2 , 3 .
The coloring c will create the partition Π on V ( O 3 ) . We shall show that the color codes of all vertices in O 3 are different. We have: c Π ( u 1 ) = ( 0 , 1 , 1 , 1 ) ; c Π ( u 2 ) = ( 1 , 0 , 1 , 1 ) ; c Π ( u 3 ) = ( 1 , 1 , 0 , 1 ) ; c Π ( v 1 ) = ( 1 , 0 , 2 , 2 ) ; c Π ( v 2 ) = ( 2 , 1 , 0 , 2 ) ; c Π ( v 3 ) = ( 2 , 0 , 1 , 2 ) ; c Π ( w 1 ) = ( 1 , 1 , 2 , 0 ) ; c Π ( w 2 ) = ( 2 , 1 , 1 , 0 ) ; c Π ( w 3 ) = ( 1 , 2 , 1 , 0 ) . c Π ( x 1 ) = ( 0 , 1 , 3 , 1 ) ; c Π ( x 2 ) = ( 3 , 0 , 1 , 1 ) ; c Π ( x 3 ) = ( 2 , 1 , 0 , 1 ) . Since the color codes of all vertices O 3 are different, c is a locating-chromatic coloring. Thus, χ L ( O 3 ) 4 .
Case B. 
χ L ( O n ) = 5 for n 4
Since a subdivision of origami graphs O n for n 4 is obtained by origami graph O n with one added vertex in edge v i w i , we have χ L ( O n ) 5 for n 4 . The addition of one vertex on the outside does not reduce the number of colors needed because the number of the sets B = { c ( u i ) , c ( v i ) , c ( w i ) , c ( u i + 1 ) } is the same.
To show the upper bound for the locating-chromatic number for a subdivision outer edge of origami graph O n for n 4 , let us consider different subcases.
Subcase a. 
(odd n), for n 2 odd, n 5 .
Let c be a coloring for a subdivision outer edge of origami graph O n , for n 2 odd, and n 5 ; we make the partition Π of V ( O n ) :
  • C 1 = { w i | 1 i n } ;
  • C 2 = { u i | for odd i , 3 i n } { v i | for even i , 2 i n 1 } { x i | for odd i , 1 i n } ;
  • C 3 = { u i | for even i , 2 i n 2 1 } { u i | for even i , n 2 + 3 i n 1 } { v i | for odd i , 1 i n } { x i | for even i , 2 i n 1 } ;
  • C 4 = { u 1 } ;
  • C 5 = { u n 2 + 1 } .
For for n 2 odd the color codes of all the vertices of V ( O n ) are:
c Π ( u i ) = 0 , for the second component , odd   i , 3 i n , n 5 for the third component , even   i , 2 i n 2 1 , n 5 for the third component , even   i , n 2 + 3 i n 1 , n 9 for the fourth component , i = 1 for the fifth component , i = n 2 + 1 2 , for the third component , i = n 2 + 1 i 1 , for the fourth component , 2 i n 2 , n 5 n i + 1 for the fourth component , n 2 + 1 i n , n 5 n 2 i , for the fifth component , i = 1 i n 2 1 , for the fifth component , n 2 + 1 i n , n 5 n 2 i + 1 , for the fifth component , 2 i n 2 , n 5 1 , otherwise .
c Π ( v i ) = 2 , for the first component , 1 i n , n 5 0 , for the second component , odd   i , 1 i n , n 5 for the third component , even   i , 2 i n 1 , n 5 i , for the fourth component , 1 i n 2 , n 5 n i + 2 , for the fourth component , n 2 + 1 i n , n 5 n 2 , for the fifth component , i = 1 n 2 i + 2 , for the fifth component , 2 i n 2 , n 5 i n 2 , for the fifth component , n 2 + 1 i n , n 5 1 , otherwise .
c Π ( w i ) = 0 , for the first component , 1 i n , n 5 2 , for the third component , i = n 2 and   i   = n n 2 i + 1 , for the fifth component , 1 i n 2 , n 5 i n 2 , for the fifth component , n 2 + 1 i n , n 5 i , for the fourth component , 1 i n 2 , n 5 n i + 1 , for the fourth component , n 2 + 1 i n , n 5 1 , otherwise .
c Π ( x i ) = 0 , for the second component , odd   i , 1 i n , n 5 for the third component , even   i , 2 i n 1 , n 5 i + 1 , for the fourth component , 1 i n 2 , n 5 n i + 2 , for the fourth component , n 2 + 1 i n , n 5 n 2 i + 2 , for the fifth component , 1 i n 2 , n 5 i n 2 + 1 , for the fifth component , n 2 + 1 i n , n 5 1 , otherwise .
Since for n odd all vertices have different color codes, c is a locating coloring for subdivision of origami graph O n , so that χ L ( O n ) 5 , for n 2 odd, n 5 .
Subcase b. 
(odd n), for n 2 even, n 7 .
Let c be a coloring for a subdivision outer edge of origami graph O n , for n 2 even, and n 7 ; we make the partition Π of V ( O n ) :
  • C 1 = { w i | 1 i n } ;
  • C 2 = { u i | for odd i , 3 i n } { v i | for even i , 2 i n 1 } { x i | for odd i , 1 i n } ;
  • C 3 = { u i | for even i , 2 i n 2 2 } { u i | for even i , n 2 + 2 i n 1 } { v i | for odd i , 1 i n } { x i | for even i , 2 i n 1 } ;
  • C 4 = { u 1 } ;
  • C 5 = { u n 2 } .
For n 2 even, the color codes of all the vertices of V ( O n ) are:
c Π ( u i ) = 0 , for the second component , odd   i , 3 i n , n 7 for the third component , even   i , 2 i n 2 2 , n 7 for the third component , even   i , n 2 + 2 i n 1 , n 7 for the fourth component , i = 1 for the fifth component , i = n 2 2 , for the third component , i = n 2 i 1 , for the fourth component , 2 i n 2 1 , n 7 n i + 1 , for the fourth component , odd   i , n 2 + 1 i n , n 7 n 2 1 , for the fourth component , i = n 2 n 2 i , for the fifth component , 1 i n 2 1 , n 7 i n 2 , for the fifth component , n 2 + 1 i n , n 7 1 , otherwise .
c Π ( v i ) = 0 , for the second component , even   i , 2 i n 1 , n 7 for the third component , odd   i , 1 i n , n 7 2 , for the first component , 1 i n , n 7 i , for the fourth component , 1 i n 2 , n 7 n i + 2 for the fourth component , n 2 + 1 i n , n 7 n 2 i + 1 for the fifth component , 1 i n 2 , n 7 i n 2 + 1 for the fifth component , n 2 + 1 i n , n 7 1 , otherwise .
c Π ( w i ) = 0 , for the first component , 1 i n , n 7 2 , for the third component , i = n 2 1   and   i = n i , for the fourth component , 1 i n 2 , n 7 n i + 1 , for the fourth component , n 2 + 1 i n , n 7 n 2 i , for the fifth component , 1 i n 2 1 , n 7 i n 2 + 1 , for the fifth component , n 2 i n , n 7 1 , otherwise .
c Π ( x i ) = 0 , for the second component , odd   i , 1 i n , n 7 for the third component , even   i , 2 i n 1 , n 7 i + 1 , for the fourth component , 1 i n 2 1 , n 7 n i + 2 , for the fourth component , n 2 i n , n 7 n 2 i + 2 , for the fifth component , 1 i n 2 , n 7 i n 2 + 2 , for the fifth component , n 2 + 1 i n , n 7 1 , otherwise .
Since for n odd all vertices have different color codes, c is a locating coloring for a subdivision of the outer edge of origami graph O n , so that χ L ( O n ) 5 , for n 2 even, n 7 .
Subcase c. 
(even n), for n 2 odd, n 6 .
Let c be a coloring for a subdivision outer edge of origami graph O n , for n 2 odd, and n 6 ; we make the partition Π of V ( O n ) :
  • C 1 = { w i | 1 i n 2 1 } { w i | n 2 + 1 i n } ;
  • C 2 = { u i | for odd i , 3 i n 1 } { v i | for even i , 2 i n } { x i | for odd i , 1 i n 1 } ;
  • C 3 = { u i | for even i , 2 i n } { v i | for odd i , 1 i n 1 } { x i | for even i , 2 i n } ;
  • C 4 = { u 1 } ;
  • C 5 = { w n 2 } .
For n 2 odd, the color codes of all the vertices of V ( O n ) are:
c Π ( u i ) = 0 , for the second component , odd   i , 3 i n 1 , n 6 for the third component , even   i , 2 i n , n 6 for the fourth component , i = 1 2 , for the second component , i = 1 i 1 , for the fourth component , 2 i n 2 , n 6 n i + 1 , for the fourth component , n 2 + 1 i n , n 6 n 2 i + 1 , for the fifth component , 1 i n 2 , n 6 i n 2 , for the fifth component , n 2 + 1 i n , n 6 1 , otherwise .
c Π ( v i ) = 2 , for the first component , 1 i n , n 6 0 , for the second component , even   i , 2 i n , n 6 for the third component , odd   i , 1 i n 1 , n 6 i , for the fourth component , 1 i n 2 , n 6 n i + 2 , for the fourth component , n 2 + 1 i n , n 6 n 2 i + 2 , for the fifth component , 1 i n 2 , n 6 i n 2 + 1 , for component , fifth component , n 2 + 1 i n , n 6 1 , otherwise .
c Π ( w i ) = 0 , for the first component , 1 i n 2 1 , n 6 for the first component , n 2 + 1 i n , n 6 for the fifth component , i = n 2 2 , for the first component , i = n 2 for the second component , i = n i , for the fourth component , 1 i n 2 , n 6 n i + 1 , for the fourth component , n 2 + 1 i n , n 6 n 2 i + 1 , for the fifth component , 1 i n 2 , n 6 i n 2 + 1 , for the fifth component , n 2 + 1 i n , n 6 1 , otherwise .
c Π ( x i ) = 0 , for the second component , odd   i , 1 i n 1 , n 6 for the third component , even   i , 2 i n , n 6 i + 1 , for the fourth component , 1 i n 2 , n 6 n i + 2 , for the fourth component , n 2 + 1 i n , n 6 n 2 i + 2 , for the fifth component , 1 i n 2 1 , n 6 i n 2 + 2 , for the fifth component , n 2 + 1 i n , n 6 1 , otherwise .
Since for n even all vertices have different color codes, c is a locating coloring for a subdivision of the outer edge of origami graph O n , so that χ L ( O n ) 5 , for n 2 odd, n 6 .
Subcase d. 
(even n), for n 2 even, n 4 .
Let c be a coloring of subdivision origami graph O n , for n 2 even, and n 4 ; we make the partition Π of V ( O n ) :
  • C 1 = { w i | 1 i n 2 } { w i | n 2 + 2 i n } ;
  • C 2 = { u i | for odd i , 3 i n 1 } { v i | for even i , 2 i n } { x i | for odd i , 1 i n 1 } ;
  • C 3 = { u i | for even i , 2 i n } { v i | for odd i , 1 i n 1 } { x i | for even i , 2 i n } ;
  • C 4 = { u 1 } ;
  • C 5 = { w n 2 + 1 } .
For n 2 even the color codes of all the vertices of V ( O n ) are:
c Π ( u i ) = 0 , for the second component , odd   i , 3 i n 1 , n 4 for the third component , even   i , 2 i n , n 4 for the fourth component , i = 1 2 , for the second component , i = 1 i 1 , for the fourth component , 2 i n 2 + 1 , n 4 n i + 1 , for the fourth component , n 2 + 2 i n , n 4 n 2 , for the fifth component , i = 1 n 2 i + 2 , for the fifth component , 2 i n 2 + 1 , n 4 i n 2 1 , for the fifth component , n 2 + 2 i n , n 4 1 , otherwise .
c Π ( v i ) = 2 , for the first component , 1 i n , n 4 0 , for the second component , even   i , 2 i n , n 4 for the third component , odd   i , 1 i n 1 , n 4 i , for the fourth component , 1 i n 2 , n 4 n i + 2 , for the fourth component , n 2 + 1 i n , n 4 n 2 + i , for the fifth component , i = 1 n 2 i + 3 , for the fifth component , 2 i n 2 + 1 , n 4 i n 2 , for the fifth component , n 2 + 2 i n , n 4 1 , otherwise .
c Π ( w i ) = 0 , for the first component , 1 i n 2 , n 4 for the first component , n 2 + 2 i n , n 4 for the fifth component , i = n 2 + 1 2 , for the first component , i = n 2 + 1 for the second component , i = n i , for the fourth component , 1 i n 2 , n 4 n i + 1 , for the fourth component , n 2 + 1 i n , n 4 n 2 i + 2 , for the fifth component , 1 i n 2 , n 4 i n 2 , for the fifth component , n 2 + 2 i n , n 4 1 , otherwise .
c Π ( x i ) = 0 , for the second component , odd   i , 1 i n 1 , n 4 for the third component , even   i , 2 i n , n 4 i + 1 , for the fourth component , 1 i n 2 , n 6 n i + 2 , for the fourth component , n 2 + 1 i n , n 4 n 2 i + 3 , for the fifth component , 1 i n 2 , n 4 i n 2 + 1 , for the fifth component , n 2 + 2 i n , n 4 1 , otherwise .
Since for n even all vertices have different color codes, c is a locating coloring for a subdivision outer edge of origami graph O n , so that χ L ( O n ) 5 , for n 2 even, n 4 . This completes the proof of Theorem 2. □
Note that Figure 2 is an example locating coloring for a subdivision of the outer edge of origami graph O 5 .

3. Conclusions

The proving steps of the two theorems we gave earlier show that the locating-chromatic number of origami graphs O n , χ L ( O n ) is 4 for n = 3 and 5 for n 4 ; the same result holds for a subdivision of the outer edge of origami graph O n . This research can be continued so as to determine the locating-chromatic number for some certain operations of origami graphs.

Author Contributions

Conceptualization, A.I. and A.A.; methodology, L.Z. and A.A.; software, A.I. and K.M.; validation, L.Z., A.A. and A.I.; formal analysis, L.Z.; investigation, A.I. and A.A.; resources, A.I. and A.A.; data curation, A.A. and L.Z.; writing—original draft preparation, A.I. and A.A.; writing—review and editing, A.I., A.A., L.Z. and K.M.; visualization, A.I. and K.M.; supervision, A.A. and L.Z.; project administration, A.A.; funding acquisition, A.A. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Data Availability Statement

Not applicable.

Acknowledgments

The authors would like to thank the Directorate of Research and Community Services at Kemendikbud RI for funding this research and the Head of the Institute of Research and Community Services of Lampung University, who supported this research.

Conflicts of Interest

The authors confirm that they have no conflict of interest to declare for this publication.

References

  1. Chartrand, G.; Zhang, P.; Salehi, E. On the partition dimension of a graph. Congr. Numer. 1998, 131, 55–66. [Google Scholar] [CrossRef]
  2. Chartrand, G.; Zhang, P.; Salehi, E. The Partition Dimension of a Graph. Aequ. Math. 2000, 55, 45–54. [Google Scholar] [CrossRef]
  3. Khuller, S.; Raghavachari, B.; Rosenfeld, A. Landmarks in graphs, Discrete Applied Mathematics. DIscrete Appl. Math. 1996, 70, 217–229. [Google Scholar] [CrossRef] [Green Version]
  4. Saenpholphat, V.; Zhang, P. Conditional resolvability: A survey. Int. J. Math. Math. Sci. 2004, 38, 1997–2017. [Google Scholar] [CrossRef] [Green Version]
  5. Johnson, M.M. Structure activity maps for visualizing the graph variables arising in drug design. J. Biopharm. Stat. 1993, 3, 203–236. [Google Scholar] [CrossRef]
  6. Chartrand, G.; Zhang, P. The theory and applications of resolvability in graphs: A survey. Congr. Numer. 2003, 160, 47–68. [Google Scholar]
  7. Chartrand, G.; Erwin, D.; Henning, M.A.; Slater, P.J.; Zhang, P. The locating-chromatic number of a graph. Bull. Inst. Comb. Appl. 2002, 36, 89–101. [Google Scholar]
  8. Chartrand, G.; Erwin, D.; Henning, M.A.; Slater, P.J.; Zhang, P. Graf of order n with locating-chromatic number n — 1. Discret. Math. 2003, 269, 65–79. [Google Scholar] [CrossRef] [Green Version]
  9. Baskoro, E.T.; Purwasih, I.A. The locating-chromatic number for corona product of graphs. Shoutheast Asian J. Sci. 2012, 1, 124–134. [Google Scholar]
  10. Asmiati, A. The Locating-Chromatic Number of Non-Homogeneous Amalgamation of Stars. Far East J. Math. Sci. 2014, 93, 89–96. [Google Scholar]
  11. Welyyanti, D.; Simanjuntak, R.; Uttunggadewa, R.S.; Baskoro, E.T. The locating-chromatic number of disconnected graphs. Far East J. Math. Sci. 2014, 94, 169–182. [Google Scholar]
  12. Welyyanti, D.; Simanjuntak, R.; Uttunggadewa, R.S.; Baskoro, E.T. On locating-chromatic number for graphs with dominant vertices. Procedia Comput. Sci. 2015, 74, 89–92. [Google Scholar] [CrossRef] [Green Version]
  13. Welyyanti, D.; Simanjuntak, R.; Uttunggadewa, R.S.; Baskoro, E.T. Locating-chromatic number for a graph of two components. AIP Conf. Proc. 2017, 1707, 20–24. [Google Scholar]
  14. Ghanem, M.; Al-Ezeh, H.; Dabbour, A. Locating Chromatic Number of Powers of Paths and Cycles. Symmetry 2019, 11, 389. [Google Scholar] [CrossRef] [Green Version]
  15. Sudhakar, S.; Francis, S.; Balaji, V. Odd mean labeling for two star graph. Appl. Math. Nonlinear Sci. 2017, 2, 195–200. [Google Scholar] [CrossRef] [Green Version]
  16. Asmiati; Wamilliana, W.; Defriadi; Yulianti, L. On some petersen graphs having locating chromatic number four or five. Far East J. Math. Sci. 2017, 102, 769–778. [Google Scholar] [CrossRef]
  17. Asmiati, A.; Yana, I.K.S.G.; Yulianti, L. On the locating-chromatic number of certain barbell graphs. Int. J. Math. Math. Sci. 2018, 5. [Google Scholar] [CrossRef] [Green Version]
  18. Syofyan, D.K.; Baskoro, E.T.; Assiyatun, H. On the locating-chromatic number of homogeneous lobsters. AKCE Int. J. Graphs Comb. 2013, 10, 245–252. [Google Scholar]
  19. Asmiati, A. On the locating-chromatic numbers of non-homogeneous caterpillars and firecracker graphs. Far East J. Math. Sci. 2016, 100, 1305–1316. [Google Scholar] [CrossRef]
  20. Irawan, A.; Asmiati, A. The locating-chromatic number of subdivision firecrackers graphs. Int. Math. Forum 2018, 13, 485–492. [Google Scholar] [CrossRef]
  21. Irawan, A.; Asmiati, A.; Suharsono, S.; Muludi, K.; Zakaria, L. Certain operation of generalized petersen graphs having locating-chromatic number five. Adv. Appl. Discret. Math. 2020, 22, 83–97. [Google Scholar] [CrossRef]
  22. Behtoei, A.; Anbarloei, M. The locating chromatic number of the join of graphs. Bull. Iran. Math. Soc. 2014, 40, 1491–1504. [Google Scholar]
  23. Nabila, S.; Salman, A.N.M. The rainbow conection number of origami graphs and pizza graphs. Procedia Comput. Sci. 2014, 74, 162–167. [Google Scholar] [CrossRef] [Green Version]
Figure 1. An origami graph O 5 .
Figure 1. An origami graph O 5 .
Algorithms 14 00167 g001
Figure 2. A subdivision of an origami graph O 5 .
Figure 2. A subdivision of an origami graph O 5 .
Algorithms 14 00167 g002
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Irawan, A.; Asmiati, A.; Zakaria, L.; Muludi, K. The Locating-Chromatic Number of Origami Graphs. Algorithms 2021, 14, 167. https://0-doi-org.brum.beds.ac.uk/10.3390/a14060167

AMA Style

Irawan A, Asmiati A, Zakaria L, Muludi K. The Locating-Chromatic Number of Origami Graphs. Algorithms. 2021; 14(6):167. https://0-doi-org.brum.beds.ac.uk/10.3390/a14060167

Chicago/Turabian Style

Irawan, Agus, Asmiati Asmiati, La Zakaria, and Kurnia Muludi. 2021. "The Locating-Chromatic Number of Origami Graphs" Algorithms 14, no. 6: 167. https://0-doi-org.brum.beds.ac.uk/10.3390/a14060167

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop