Open AccessArticle

The Locating-Chromatic Number of Origami Graphs

Department of Mathematics, Universitas Lampung, Bandar Lampung 35145, Indonesia

Information System, STMIK Pringsewu, Lampung 35373, Indonesia

Department of Computer Science, Universitas Lampung, Bandar Lampung 35145, Indonesia

Author to whom correspondence should be addressed.

Algorithms 2021, 14(6), 167; https://doi.org/10.3390/a14060167

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)

Download

Browse Figures

Versions Notes

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.

Keywords:

locating-chromatic number; origami graphs; subdivision

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, \dots, k}

, and

Π = {C_{1}, C_{2}, \dots, 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}), \dots, d (v, C_{k})))

, where

d (v, C_{i}) =

min

{d (v, x) : x \in C_{i}}

for any

i \in {1, 2, 3, \dots, 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 \geq 3

then the locating-chromatic number is 3; for a cycle

C_{n}

n \geq 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 \leq a \leq b

and

b \geq 2

χ_{L} (S_{a, b}) = b + 1

was obtained. Let

Π = {S_{1}, S_{2}, \dots, S_{k}}

be the partition of

V (G)

induced by c. A vertex

v \in G

is called a dominant vertex if

d (v, S_{i}) = 1

, where

v \notin 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 \geq 3

or five for even

n \geq 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 \in N

with

n \geq 3

. An origami graph

O_{n}

is a graph with

V (O_{n}) = {u_{i}, v_{i}, w_{i} : i \in {1, \dots, n}}

and

E (O_{n}) = {u_{i} w_{i}, u_{i} v_{i}, v_{i} w_{i} : i \in {1, \dots, n}} \cup {u_{i} u_{i + 1}, w_{i} u_{i + 1} : i \in {1, \dots, n - 1}} \cup {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 \in {1, \dots, n}}

and

E (O_{n}^{*}) = {u_{i} w_{i}, u_{i} v_{i}, v_{i} x_{i}, x_{i} w_{i} : i \in {1, \dots, n}} \cup {u_{i} u_{i + 1}, w_{i} u_{i + 1} : i \in {1, \dots, n - 1}} \cup {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 \in V (G) - {p, q}

, then

c (p) \neq c (q)

. In particular, if p and q are non-adjacent vertices such that

N (p) = N (q)

, then

c (p) \neq 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 \geq 3

. Then, the locating-chromatic number of

O_{n}

χ_{L} (O_{n}) = \{\begin{matrix} 4, & f o r n = 3 \\ 5, & o t h e r w i s e . \end{matrix}

Proof.

Let

n \in N

with

n \geq 3

. An origami graph

O_{n}

is a graph with

V (O_{n}) = {u_{i}, v_{i}, w_{i} : i \in {1, \dots, n}}

and

E (O_{n}) = {u_{i} w_{i}, u_{i} v_{i}, v_{i} w_{i} : i \in {1, \dots, n}}

∪

{u_{i} u_{i + 1}, w_{i} u_{i + 1} : i \in {1, \dots, 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 \geq 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}

O_{n}

for

n \geq 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}

O_{n}

for

n \geq 3

. Therefore,

χ_{L} (O_{3}) \geq 4

Next, we determine the upper bound of

χ_{L} (O_{3}) \leq 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}) = \{\begin{matrix} 2, & f o r i = 1, 3 \\ 3, & f o r i = 2 . \end{matrix}$
$c (w_{i}) = 4, i = 1, 2, 3 .$

The coloring c will create the partition

Π

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}) \leq 4

Case 2.

χ_{L} (O_{n}) = 5

, for

n \geq 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 \geq 4

. We assign

{c (u_{i}), c (v_{i}), c (w_{i}), c (u_{i + 1})} = {1, 2, 3, 4}

, where

c (v_{i}) \neq c (u_{i + 1})

because

d (v_{i}, x) = d (u_{i + 1}, x)

x \in {u_{i}, v_{i}}

. Observe that, on

O_{n}

for

n \geq 4

, there are n vertices

u_{i}

whose degree is 5. As a result, at least two vertices

w_{k}, w_{l}

k \neq l

have the same color codes, which is a contradiction. Therefore,

χ_{L} (O_{n}) \geq 5

, for

n \geq 4

To show the upper bound for the locating-chromatic number of origami graphs

O_{n}

for

n \geq 4

, let us differentiate some subcases.

Subcase 1.

(Odd n), for

⌈\frac{n}{2}⌉

odd,

n \geq 5

Let c be a coloring of origami graph

O_{n}

⌈\frac{n}{2}⌉

odd, and

n \geq 5

; we make the partition

Π

V (O_{n})

$C_{1} = {w_{i} | 1 \leq i \leq n}$ ;
$C_{2} = {u_{i} |$ for odd $i, 3 \leq i \leq n}$ ∪ ${v_{i} |$ for even $i, 2 \leq i \leq n - 1}$ ;
$C_{3} = {u_{i} |$ for even $i, 2 \leq i \leq ⌈\frac{n}{2}⌉ - 1}$ ∪ ${u_{i} |$ for even $i, ⌈\frac{n}{2}⌉ + 3 \leq i \leq n - 1}$ ∪ ${v_{i} |$ for odd $i, 1 \leq i \leq n}$ ;
$C_{4} = {u_{1}}$ ;
$C_{5} = {u_{⌈\frac{n}{2}⌉ + 1}}$ .

For

⌈\frac{n}{2}⌉

odd, the color codes of all the vertices of

V (O_{n})

are:

$C_{1} = {w_{i} | 1 \leq i \leq n}$ .

For

i = 1

, we have:

c_{Π} (w_{i}) = (0, 2, 1, i, ⌈\frac{n}{2}⌉ - i + 1) .

For

2 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5

we have:

c_{Π} (w_{i}) = (0, 1, 1, i, ⌈\frac{n}{2}⌉ - i + 1) .

For

i = ⌈\frac{n}{2}⌉ + 1

we have:

c_{Π} (w_{i}) = (0, 1, 2, n - i + 1, i - ⌈\frac{n}{2}⌉) .

For

⌈\frac{n}{2}⌉ + 2 \leq i \leq n, n \geq 5

we have:

c_{Π} (w_{i}) = (0, 1, 1, n - i + 1, i - ⌈\frac{n}{2}⌉) .

C_{2} = {u_{i} |

for odd

i, 3 \leq i \leq n}

∪

{v_{i} |

for even

i, 2 \leq i \leq n - 1}

For i odd,

3 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5

we have:

c_{Π} (u_{i}) = (1, 0, 1, i - 1, ⌈\frac{n}{2}⌉ - i + 1) .

For i odd,

⌈\frac{n}{2}⌉ + 2 \leq i \leq n, n \geq 5

we have:

c_{Π} (u_{i}) = (1, 0, 1, n - i + 1, i - ⌈\frac{n}{2}⌉ - 1) .

For i even,

2 \leq i \leq ⌈\frac{n}{2}⌉ - 1, n \geq 5

we have:

c_{Π} (v_{i}) = (1, 0, 1, i, ⌈\frac{n}{2}⌉ - i + 2) .

For

i = ⌈\frac{n}{2}⌉ + 1

, we have:

c_{Π} (v_{i}) = (1, 0, 3, n - i + 2, 1) .

For i even,

⌈\frac{n}{2}⌉ + 3 \leq i \leq n - 1, n \geq 9

we have:

c_{Π} (v_{i}) = (1, 0, 1, n - i + 2, i - ⌈\frac{n}{2}⌉) .

C_{3} = {u_{i} |

for even

i, 2 \leq i \leq ⌈\frac{n}{2}⌉ - 1}

∪

{u_{i} |

for even

i, ⌈\frac{n}{2}⌉ + 3 \leq i \leq n - 1}

∪

{v_{i} |

for odd

i, 1 \leq i \leq n} .

For

i = 1

, we have:

c_{Π} (v_{i}) = (1, 2, 0, i, ⌈\frac{n}{2}⌉) .

For i odd,

3 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5

we have:

c_{Π} (v_{i}) = (1, 1, 0, i, ⌈\frac{n}{2}⌉ - i + 2) .

For i odd,

⌈\frac{n}{2}⌉ + 2 \leq i \leq n, n \geq 9

we have:

c_{Π} (v_{i}) = (1, 1, 0, n - i + 2, i - ⌈\frac{n}{2}⌉) .

For i even,

2 \leq i \leq ⌈\frac{n}{2}⌉ - 1, n \geq 5

we have:

c_{Π} (u_{i}) = (1, 1, 0, i - 1, ⌈\frac{n}{2}⌉ - i + 1) .

For i even,

⌈\frac{n}{2}⌉ + 3 \leq i \leq n - 1, n \geq 9

we have:

c_{Π} (u_{i}) = (1, 1, 0, n - i + 1, i - ⌈\frac{n}{2}⌉ - 1) .

For

C_{4} = {u_{1}}

, we have:

c_{Π} (u_{1}) = (1, 1, 1, 0, ⌈\frac{n}{2}⌉ - 1) .

For

C_{5} = {u_{⌈\frac{n}{2}⌉ + 1}}

, we have:

c_{Π} (u_{⌈\frac{n}{2}⌉ + 1}) = (1, 1, 2, ⌈\frac{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}) \leq 5

, for

⌈\frac{n}{2}⌉

odd,

n \geq 5

Subcase 2.

(Odd n), for

⌈\frac{n}{2}⌉

even,

n \geq 7

Let c be a coloring of origami graph

O_{n}

⌈\frac{n}{2}⌉

even, and

n \geq 7

; we make the partition

Π

V (O_{n})

as follows:

$C_{1} = {w_{i} | 1 \leq i \leq n}$ ;
$C_{2} = {u_{i} |$ for odd $i, 3 \leq i \leq n}$ ∪ ${v_{i} |$ for even $i, 2 \leq i \leq n - 1}$ ;
$C_{3} = {u_{i} |$ for even $i, 2 \leq i \leq ⌈\frac{n}{2}⌉ - 2}$ ∪ ${u_{i} |$ for even $i, ⌈\frac{n}{2}⌉ + 2 \leq i \leq n - 1}$ ∪ ${v_{i} |$ for odd $i, 1 \leq i \leq n}$ ;
$C_{4} = {u_{1}}$ ;
$C_{5} = {u_{⌈\frac{n}{2}⌉}}$ .

For

⌈\frac{n}{2}⌉

even, the color codes of all the vertices of

V (O_{n})

are:

$C_{1} = {w_{i} | 1 \leq i \leq n} .$

For

i = 1

, we have:

c_{Π} (w_{i}) = (0, 2, 1, i, ⌈\frac{n}{2}⌉ - i) .

For

2 \leq i \leq ⌈\frac{n}{2}⌉ - 1, n \geq 7

we have:

c_{Π} (w_{i}) = (0, 1, 1, i, ⌈\frac{n}{2}⌉ - i) .

For

i = ⌈\frac{n}{2}⌉

, we have:

c_{Π} (w_{i}) = (0, 1, 2, n - i + 1, i - ⌈\frac{n}{2}⌉ + 1) .

For

⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 7

we have:

c_{Π} (w_{i}) = (0, 1, 1, n - i + 1, i - ⌈\frac{n}{2}⌉ + 1) .

C_{2} = {u_{i} |

for odd

i, 3 \leq i \leq n}

∪

{v_{i} |

for even

i, 2 \leq i \leq n - 1}

For i odd,

3 \leq i \leq ⌈\frac{n}{2}⌉ - 1, n \geq 7

we have:

c_{Π} (u_{i}) = (1, 0, 1, i - 1, ⌈\frac{n}{2}⌉ - i) .

For i odd,

⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 7

we have:

c_{Π} (u_{i}) = (1, 0, 1, n - i + 1, i - ⌈\frac{n}{2}⌉) .

For i even,

2 \leq i \leq ⌈\frac{n}{2}⌉ - 2, n \geq 7

we have:

c_{Π} (v_{i}) = (1, 0, 1, i, ⌈\frac{n}{2}⌉ - i + 1) .

For

i = ⌈\frac{n}{2}⌉

, we have:

c_{Π} (v_{i}) = (1, 0, 3, i, i - ⌈\frac{n}{2}⌉ + 1) .

For i even,

⌈\frac{n}{2}⌉ + 3 \leq i \leq n - 1, n \geq 7

we have:

c_{Π} (v_{i}) = (1, 0, 1, n - i + 2, i - ⌈\frac{n}{2}⌉ + 1) .

C_{3} = {u_{i} |

for even

i, 2 \leq i \leq ⌈\frac{n}{2}⌉ - 2}

∪

{u_{i} |

for even

i, ⌈\frac{n}{2}⌉ + 2 \leq i \leq n - 1}

∪

{v_{i} |

for odd

i, 1 \leq i \leq n} .

For

i = 1

we have:

c_{Π} (v_{i}) = (1, 2, 0, i, ⌈\frac{n}{2}⌉ - i + 1) .

For i odd,

3 \leq i \leq ⌈\frac{n}{2}⌉ - 1, n \geq 7

we have:

c_{Π} (v_{i}) = (1, 1, 0, i, ⌈\frac{n}{2}⌉ - i + 1) .

For i odd,

⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 7

we have:

c_{Π} (v_{i}) = (1, 1, 0, n - i + 2, i - ⌈\frac{n}{2}⌉ + 1) .

For i even,

2 \leq i \leq ⌈\frac{n}{2}⌉ - 2, n \geq 7

we have:

c_{Π} (u_{i}) = (1, 1, 0, i - 1, ⌈\frac{n}{2}⌉ - i) .

For i even,

⌈\frac{n}{2}⌉ + 2 \leq i \leq n, n \geq 7

we have:

c_{Π} (u_{i}) = (1, 1, 0, n - i + 1, i - ⌈\frac{n}{2}⌉) .

C_{4} = {u_{1}}

, we have:

c_{Π} (u_{1}) = (1, 1, 1, 0, ⌈\frac{n}{2}⌉ - 1) .

C_{5} = {u_{⌈\frac{n}{2}⌉}}

, we have:

c_{Π} (u_{⌈\frac{n}{2}⌉}) = (1, 1, 2, ⌈\frac{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}) \leq 5

, for

⌈\frac{n}{2}⌉

even,

n \geq 7

Subcase 3.

(even n), for

\frac{n}{2}

odd,

n \geq 6

Let c be a coloring of origami graph

O_{n}

\frac{n}{2}

odd, and

n \geq 6

; we make the partition

Π

V (O_{n})

$C_{1} = {w_{i} | 1 \leq i \leq \frac{n}{2} - 1} \cup {w_{i} | \frac{n}{2} + 1 \leq i \leq n}$ ;
$C_{2} = {u_{i} |$ for odd $i, 3 \leq i \leq n - 1}$ ∪ ${v_{i} |$ for even $i, 2 \leq i \leq n}$ ;
$C_{3} = {u_{i} |$ for even $i, 2 \leq i \leq n}$ ∪ ${v_{i} |$ for odd $i, 1 \leq i \leq n - 1}$ ;
$C_{4} = {u_{1}}$ ;
$C_{5} = {w_{\frac{n}{2}}}$ .

For

\frac{n}{2}

odd, the color codes of all the vertices of

V (O_{n})

are:

C_{1} = {w_{i} | 1 \leq i \leq \frac{n}{2} - 1} \cup {w_{i} | \frac{n}{2} + 1 \leq i \leq n} .

For

i = 1

, we have:

c_{Π} (w_{i}) = (0, 2, 1, i, \frac{n}{2} - i + 1) .

For

2 \leq i \leq \frac{n}{2} - 1, n \geq 6

we have:

c_{Π} (w_{i}) = (0, 1, 1, i, \frac{n}{2} - i + 1) .

For

\frac{n}{2} + 1 \leq i \leq n, n \geq 6

we have:

c_{Π} (w_{i}) = (0, 1, 1, n - i + 1, i - \frac{n}{2} + 1) .

C_{2} = {u_{i} |

for odd

i, 3 \leq i \leq n - 1}

∪

{v_{i} |

for even

i, 2 \leq i \leq n} .

For i odd,

3 \leq i \leq \frac{n}{2}, n \geq 6

we have:

c_{Π} (u_{i}) = (1, 0, 1, i - 1, \frac{n}{2} - i + 1) .

For i odd,

\frac{n}{2} + 2 \leq i \leq n - 1, n \geq 6

we have:

c_{Π} (u_{i}) = (1, 0, 1, n - i + 1, i - \frac{n}{2}) .

For i even,

2 \leq i \leq \frac{n}{2} - 1, n \geq 6

we have:

c_{Π} (v_{i}) = (1, 0, 1, i, \frac{n}{2} - i + 2) .

For i even,

\frac{n}{2} + 1 \leq i \leq n - 1, n \geq 6

we have:

c_{Π} (v_{i}) = (1, 0, 1, n - i + 2, i - \frac{n}{2} + 1) .

C_{3} = {u_{i} |

for even

i, 2 \leq i \leq n}

∪

{v_{i} |

for odd

i, 1 \leq i \leq n - 1} .

For

i = 1

, we have:

c_{Π} (v_{i}) = (1, 3, 0, i, \frac{n}{2} - i + 2) .

For i odd,

3 \leq i \leq \frac{n}{2} - 2, n \geq 10

we have:

c_{Π} (v_{i}) = (1, 1, 0, i, \frac{n}{2} - i + 2)

For

i = \frac{n}{2}

, we have:

c_{Π} (v_{i}) = (2, 1, 0, i, 1) .

For i odd,

\frac{n}{2} + 2 \leq i \leq n - 1, n \geq 6

we have:

c_{Π} (v_{i}) = (1, 1, 0, n - i + 2, i - \frac{n}{2} + 1) .

For i even,

2 \leq i \leq \frac{n}{2} - 1, n \geq 6

we have:

c_{Π} (u_{i}) = (1, 1, 0, i - 1, \frac{n}{2} - i + 1) .

For i even,

\frac{n}{2} + 1 \leq i \leq n, n \geq 6

we have:

c_{Π} (u_{i}) = (1, 1, 0, n - i + 1, i - \frac{n}{2}) .

For

C_{4} = {u_{1}}

, we have:

c_{Π} (u_{1}) = (1, 2, 1, 0, \frac{n}{2} - i + 1) .

For

C_{5} = {w_{\frac{n}{2}}}

, we have:

c_{Π} (w_{\frac{n}{2}}) = (2, 1, 1, \frac{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}) \leq 5

, for

\frac{n}{2}

odd,

n \geq 6

Subcase 4.

(even n), for

\frac{n}{2}

even,

n \geq 4

Let c be a coloring of origami graph

O_{n}

\frac{n}{2}

even, and

n \geq 4

; we make the partition

Π

V (O_{n})

as follows:

$C_{1} = {w_{i} | 1 \leq i \leq \frac{n}{2}} \cup {w_{i} | \frac{n}{2} + 2 \leq i \leq n}$ ;
$C_{2} = {u_{i} |$ for odd $i, 3 \leq i \leq n - 1}$ ∪ ${v_{i} |$ for even $i, 2 \leq i \leq n}$ ;
$C_{3} = {u_{i} |$ for even $i, 2 \leq i \leq n}$ ∪ ${v_{i} |$ for odd $i, 1 \leq i \leq n - 1}$ ;
$C_{4} = {u_{1}}$ ;
$C_{5} = {w_{\frac{n}{2} + 1}}$ .

For

\frac{n}{2}

even, the color codes of all the vertices of

V (O_{n})

are:

C_{1} = {w_{i} | 1 \leq i \leq \frac{n}{2}} \cup {w_{i} | \frac{n}{2} + 2 \leq i \leq n} .

For

i = 1

we have:

c_{Π} (w_{i}) = (0, 2, 1, i, \frac{n}{2} - i + 2) .

For

2 \leq i \leq \frac{n}{2}, n \geq 4

we have:

c_{Π} (w_{i}) = (0, 1, 1, i, \frac{n}{2} - i + 2) .

For

\frac{n}{2} + 2 \leq i \leq n, n \geq 4

we have:

c_{Π} (w_{i}) = (0, 1, 1, n - i + 1, i - \frac{n}{2}) .

C_{2} = {u_{i} |

for odd

i, 3 \leq i \leq n - 1}

∪

{v_{i} |

for even

i, 2 \leq i \leq n} .

For i odd,

3 \leq i \leq \frac{n}{2} + 1, n \geq 8

we have:

c_{Π} (u_{i}) = (1, 0, 1, i - 1, \frac{n}{2} - i + 2) .

For i odd,

\frac{n}{2} + 3 \leq i \leq n - 1, n \geq 8

we have:

c_{Π} (u_{i}) = (1, 0, 1, n - i + 1, i - \frac{n}{2} - 1) .

For i even,

2 \leq i \leq \frac{n}{2}, n \geq 4

we have:

c_{Π} (v_{i}) = (1, 0, 1, i, \frac{n}{2} - i + 3) .

For i even,

\frac{n}{2} + 2 \leq i \leq n, n \geq 8

we have:

c_{Π} (v_{i}) = (1, 0, 1, n - i + 2, i - \frac{n}{2}) .

C_{3} = {u_{i} |

for even

i, 2 \leq i \leq n}

∪

{v_{i} |

for odd

i, 1 \leq i \leq n - 1} .

For

i = 1

, we have:

c_{Π} (v_{i}) = (1, 3, 0, 1, \frac{n}{2} + 1) .

For i odd,

3 \leq i \leq \frac{n}{2} - 1, n \geq 8

we have:

c_{Π} (v_{i}) = (1, 1, 0, i, \frac{n}{2} - i + 3) .

For

i = \frac{n}{2} + 1

, we have:

c_{Π} (v_{i}) = (2, 1, 0, i, 1) .

For i odd,

\frac{n}{2} + 3 \leq i \leq n - 1, n \geq 8

we have:

c_{Π} (v_{i}) = (1, 1, 0, n - i + 2, i - \frac{n}{2}) .

For i even,

2 \leq i \leq \frac{n}{2}, n \geq 4

we have:

c_{Π} (u_{i}) = (1, 1, 0, i - 1, \frac{n}{2}) .

For i even,

\frac{n}{2} + 2 \leq i \leq n, n \geq 8

we have:

c_{Π} (u_{i}) = (1, 1, 0, n - i + 1, i - \frac{n}{2} - 1) .

For

C_{4} = {u_{1}}

, we have:

c_{Π} (u_{1}) = (1, 2, 1, 0, \frac{n}{2}) .

For

C_{5} = {w_{\frac{n}{2}}}

, we have:

c_{Π} (w_{\frac{n}{2}}) = (2, 1, 1, \frac{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}) \leq 5

, for

\frac{n}{2}

even,

n \geq 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 \geq 3

. Then the locating-chromatic number of

O_{n}^{*}

χ_{L} (O_{n}^{*}) = \{\begin{matrix} 4, & f o r n = 3 \\ 5, & o t h e r w i s e . \end{matrix}

Proof.

Let

O_{n}^{*}

n \geq 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 \in {1, \dots, n}}

and

E (O_{n}^{*}) = {u_{i} w_{i}, u_{i} v_{i}, v_{i} x_{i}, x_{i} w_{i} : i \in {1, \dots, n}}

∪

{u_{i} u_{i + 1}, w_{i} u_{i + 1} : i \in {1, \dots, 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}^{*}) \geq 4

Next, we determine the upper bound of

χ_{L} (O_{3}^{*}) \leq 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}) = \{\begin{matrix} 2, & f o r i = 1, 3 \\ 3, & f o r i = 2 . \end{matrix}

c (w_{i}) = 4, i = 1, 2, 3 .

c (x_{i}) = i, i = 1, 2, 3 .

The coloring c will create the partition

Π

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}^{*}) \leq 4

Case B.

χ_{L} (O_{n}^{*}) = 5

for

n \geq 4

Since a subdivision of origami graphs

O_{n}^{*}

for

n \geq 4

is obtained by origami graph

O_{n}

with one added vertex in edge

v_{i} w_{i}

, we have

χ_{L} (O_{n}^{*}) \geq 5

for

n \geq 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 \geq 4

, let us consider different subcases.

Subcase a.

(odd n), for

⌈\frac{n}{2}⌉

odd,

n \geq 5

Let c be a coloring for a subdivision outer edge of origami graph

O_{n}^{*}

, for

⌈\frac{n}{2}⌉

odd, and

n \geq 5

; we make the partition

Π

V (O_{n}^{*})

$C_{1} = {w_{i} | 1 \leq i \leq n}$ ;
$C_{2} = {u_{i} |$ for odd $i, 3 \leq i \leq n}$ ∪ ${v_{i} |$ for even $i, 2 \leq i \leq n - 1}$ ∪ ${x_{i} |$ for odd $i, 1 \leq i \leq n}$ ;
$C_{3} = {u_{i} |$ for even $i, 2 \leq i \leq ⌈\frac{n}{2}⌉ - 1}$ ∪ ${u_{i} |$ for even $i, ⌈\frac{n}{2}⌉ + 3 \leq i \leq n - 1}$ ∪ ${v_{i} |$ for odd $i, 1 \leq i \leq n}$ ∪ ${x_{i} |$ for even $i, 2 \leq i \leq n - 1}$ ;
$C_{4} = {u_{1}}$ ;
$C_{5} = {u_{⌈\frac{n}{2}⌉ + 1}}$ .

For for

⌈\frac{n}{2}⌉

odd the color codes of all the vertices of

V (O_{n}^{*})

are:

c_{Π} (u_{i}) = \{\begin{matrix} 0, & for the second component, odd i, 3 \leq i \leq n, n \geq 5 \\ for the third component, even i, 2 \leq i \leq ⌈\frac{n}{2}⌉ - 1, n \geq 5 \\ for the third component, even i, ⌈\frac{n}{2}⌉ + 3 \leq i \leq n - 1, n \geq 9 \\ for the fourth component, i = 1 \\ for the fifth component, i = ⌈\frac{n}{2}⌉ + 1 \\ 2, & for the third component, i = ⌈\frac{n}{2}⌉ + 1 \\ i - 1, & for the fourth component, 2 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5 \\ n - i + 1 & for the fourth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 5 \\ ⌈\frac{n}{2}⌉ - i, & for the fifth component, i = 1 \\ i - ⌈\frac{n}{2}⌉ - 1, & for the fifth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 5 \\ ⌈\frac{n}{2}⌉ - i + 1, & for the fifth component, 2 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5 \\ 1, & otherwise . \end{matrix}

c_{Π} (v_{i}) = \{\begin{matrix} 2, & for the first component, 1 \leq i \leq n, n \geq 5 \\ 0, & for the second component, odd i, 1 \leq i \leq n, n \geq 5 \\ for the third component, even i, 2 \leq i \leq n - 1, n \geq 5 \\ i, & for the fourth component, 1 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5 \\ n - i + 2, & for the fourth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 5 \\ ⌈\frac{n}{2}⌉, & for the fifth component, i = 1 \\ ⌈\frac{n}{2}⌉ - i + 2, & for the fifth component, 2 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5 \\ i - ⌈\frac{n}{2}⌉, & for the fifth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 5 \\ 1, & otherwise . \end{matrix}

c_{Π} (w_{i}) = \{\begin{matrix} 0, & for the first component, 1 \leq i \leq n, n \geq 5 \\ 2, & for the third component, i = ⌈\frac{n}{2}⌉ and i = n \\ ⌈\frac{n}{2}⌉ - i + 1, & for the fifth component, 1 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5 \\ i - ⌈\frac{n}{2}⌉, & for the fifth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 5 \\ i, & for the fourth component, 1 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5 \\ n - i + 1, & for the fourth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 5 \\ 1, & otherwise . \end{matrix}

c_{Π} (x_{i}) = \{\begin{matrix} 0, & for the second component, odd i, 1 \leq i \leq n, n \geq 5 \\ for the third component, even i, 2 \leq i \leq n - 1, n \geq 5 \\ i + 1, & for the fourth component, 1 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5 \\ n - i + 2, & for the fourth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 5 \\ ⌈\frac{n}{2}⌉ - i + 2, & for the fifth component, 1 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 5 \\ i - ⌈\frac{n}{2}⌉ + 1, & for the fifth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 5 \\ 1, & otherwise . \end{matrix}

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}^{*}) \leq 5

, for

⌈\frac{n}{2}⌉

odd,

n \geq 5

Subcase b.

(odd n), for

⌈\frac{n}{2}⌉

even,

n \geq 7

Let c be a coloring for a subdivision outer edge of origami graph

O_{n}^{*}

, for

⌈\frac{n}{2}⌉

even, and

n \geq 7

; we make the partition

Π

V (O_{n}^{*})

$C_{1} = {w_{i} | 1 \leq i \leq n}$ ;
$C_{2} = {u_{i} |$ for odd $i, 3 \leq i \leq n}$ ∪ ${v_{i} |$ for even $i, 2 \leq i \leq n - 1}$ ∪ ${x_{i} |$ for odd $i, 1 \leq i \leq n}$ ;
$C_{3} = {u_{i} |$ for even $i, 2 \leq i \leq ⌈\frac{n}{2}⌉ - 2}$ ∪ ${u_{i} |$ for even $i, ⌈\frac{n}{2}⌉ + 2 \leq i \leq n - 1}$ ∪ ${v_{i} |$ for odd $i, 1 \leq i \leq n}$ ∪ ${x_{i} |$ for even $i, 2 \leq i \leq n - 1}$ ;
$C_{4} = {u_{1}}$ ;
$C_{5} = {u_{⌈\frac{n}{2}⌉}}$ .

For

⌈\frac{n}{2}⌉

even, the color codes of all the vertices of

V (O_{n}^{*})

are:

c_{Π} (u_{i}) = \{\begin{matrix} 0, & for the second component, odd i, 3 \leq i \leq n, n \geq 7 \\ for the third component, even i, 2 \leq i \leq ⌈\frac{n}{2}⌉ - 2, n \geq 7 \\ for the third component, even i, ⌈\frac{n}{2}⌉ + 2 \leq i \leq n - 1, n \geq 7 \\ for the fourth component, i = 1 \\ for the fifth component, i = ⌈\frac{n}{2}⌉ \\ 2, & for the third component, i = ⌈\frac{n}{2}⌉ \\ i - 1, & for the fourth component, 2 \leq i \leq ⌈\frac{n}{2}⌉ - 1, n \geq 7 \\ n - i + 1, & for the fourth component, odd i, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 7 \\ ⌈\frac{n}{2}⌉ - 1, & for the fourth component, i = ⌈\frac{n}{2}⌉ \\ ⌈\frac{n}{2}⌉ - i, & for the fifth component, 1 \leq i \leq ⌈\frac{n}{2}⌉ - 1, n \geq 7 \\ i - ⌈\frac{n}{2}⌉, & for the fifth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 7 \\ 1, & otherwise . \end{matrix}

c_{Π} (v_{i}) = \{\begin{matrix} 0, & for the second component, even i, 2 \leq i \leq n - 1, n \geq 7 \\ for the third component, odd i, 1 \leq i \leq n, n \geq 7 \\ 2, & for the first component, 1 \leq i \leq n, n \geq 7 \\ i, & for the fourth component, 1 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 7 \\ n - i + 2 & for the fourth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 7 \\ ⌈\frac{n}{2}⌉ - i + 1 & for the fifth component, 1 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 7 \\ i - ⌈\frac{n}{2}⌉ + 1 & for the fifth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 7 \\ 1, & otherwise . \end{matrix}

c_{Π} (w_{i}) = \{\begin{matrix} 0, & for the first component, 1 \leq i \leq n, n \geq 7 \\ 2, & for the third component, i = ⌈\frac{n}{2}⌉ - 1 and i = n \\ i, & for the fourth component, 1 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 7 \\ n - i + 1, & for the fourth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 7 \\ ⌈\frac{n}{2}⌉ - i, & for the fifth component, 1 \leq i \leq ⌈\frac{n}{2}⌉ - 1, n \geq 7 \\ i - ⌈\frac{n}{2}⌉ + 1, & for the fifth component, ⌈\frac{n}{2}⌉ \leq i \leq n, n \geq 7 \\ 1, & otherwise . \end{matrix}

c_{Π} (x_{i}) = \{\begin{matrix} 0, & for the second component, odd i, 1 \leq i \leq n, n \geq 7 \\ for the third component, even i, 2 \leq i \leq n - 1, n \geq 7 \\ i + 1, & for the fourth component, 1 \leq i \leq ⌈\frac{n}{2}⌉ - 1, n \geq 7 \\ n - i + 2, & for the fourth component, ⌈\frac{n}{2}⌉ \leq i \leq n, n \geq 7 \\ ⌈\frac{n}{2}⌉ - i + 2, & for the fifth component, 1 \leq i \leq ⌈\frac{n}{2}⌉, n \geq 7 \\ i - ⌈\frac{n}{2}⌉ + 2, & for the fifth component, ⌈\frac{n}{2}⌉ + 1 \leq i \leq n, n \geq 7 \\ 1, & otherwise . \end{matrix}

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}^{*}) \leq 5

, for

⌈\frac{n}{2}⌉

even,

n \geq 7

Subcase c.

(even n), for

\frac{n}{2}

odd,

n \geq 6

Let c be a coloring for a subdivision outer edge of origami graph

O_{n}^{*}

, for

\frac{n}{2}

odd, and

n \geq 6

; we make the partition

Π

V (O_{n}^{*})

$C_{1} = {w_{i} | 1 \leq i \leq \frac{n}{2} - 1} \cup {w_{i} | \frac{n}{2} + 1 \leq i \leq n}$ ;
$C_{2} = {u_{i} |$ for odd $i, 3 \leq i \leq n - 1}$ ∪ ${v_{i} |$ for even $i, 2 \leq i \leq n}$ ∪ ${x_{i} |$ for odd $i, 1 \leq i \leq n - 1}$ ;
$C_{3} = {u_{i} |$ for even $i, 2 \leq i \leq n}$ ∪ ${v_{i} |$ for odd $i, 1 \leq i \leq n - 1}$ ∪ ${x_{i} |$ for even $i, 2 \leq i \leq n}$ ;
$C_{4} = {u_{1}}$ ;
$C_{5} = {w_{\frac{n}{2}}}$ .

For

\frac{n}{2}

odd, the color codes of all the vertices of

V (O_{n}^{*})

are:

c_{Π} (u_{i}) = \{\begin{matrix} 0, & for the second component, odd i, 3 \leq i \leq n - 1, n \geq 6 \\ for the third component, even i, 2 \leq i \leq n, n \geq 6 \\ for the fourth component, i = 1 \\ 2, & for the second component, i = 1 \\ i - 1, & for the fourth component, 2 \leq i \leq \frac{n}{2}, n \geq 6 \\ n - i + 1, & for the fourth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 6 \\ \frac{n}{2} - i + 1, & for the fifth component, 1 \leq i \leq \frac{n}{2}, n \geq 6 \\ i - \frac{n}{2}, & for the fifth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 6 \\ 1, & otherwise . \end{matrix}

c_{Π} (v_{i}) = \{\begin{matrix} 2, & for the first component, 1 \leq i \leq n, n \geq 6 \\ 0, & for the second component, even i, 2 \leq i \leq n, n \geq 6 \\ for the third component, odd i, 1 \leq i \leq n - 1, n \geq 6 \\ i, & for the fourth component, 1 \leq i \leq \frac{n}{2}, n \geq 6 \\ n - i + 2, & for the fourth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 6 \\ \frac{n}{2} - i + 2, & for the fifth component, 1 \leq i \leq \frac{n}{2}, n \geq 6 \\ i - \frac{n}{2} + 1, & for component, fifth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 6 \\ 1, & otherwise . \end{matrix}

c_{Π} (w_{i}) = \{\begin{matrix} 0, & for the first component, 1 \leq i \leq \frac{n}{2} - 1, n \geq 6 \\ for the first component, \frac{n}{2} + 1 \leq i \leq n, n \geq 6 \\ for the fifth component, i = \frac{n}{2} \\ 2, & for the first component, i = \frac{n}{2} \\ for the second component, i = n \\ i, & for the fourth component, 1 \leq i \leq \frac{n}{2}, n \geq 6 \\ n - i + 1, & for the fourth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 6 \\ \frac{n}{2} - i + 1, & for the fifth component, 1 \leq i \leq \frac{n}{2}, n \geq 6 \\ i - \frac{n}{2} + 1, & for the fifth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 6 \\ 1, & otherwise . \end{matrix}

c_{Π} (x_{i}) = \{\begin{matrix} 0, & for the second component, odd i, 1 \leq i \leq n - 1, n \geq 6 \\ for the third component, even i, 2 \leq i \leq n, n \geq 6 \\ i + 1, & for the fourth component, 1 \leq i \leq \frac{n}{2}, n \geq 6 \\ n - i + 2, & for the fourth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 6 \\ \frac{n}{2} - i + 2, & for the fifth component, 1 \leq i \leq \frac{n}{2} - 1, n \geq 6 \\ i - \frac{n}{2} + 2, & for the fifth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 6 \\ 1, & otherwise . \end{matrix}

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}^{*}) \leq 5

, for

\frac{n}{2}

odd,

n \geq 6

Subcase d.

(even n), for

\frac{n}{2}

even,

n \geq 4

Let c be a coloring of subdivision origami graph

O_{n}^{*}

, for

\frac{n}{2}

even, and

n \geq 4

; we make the partition

Π

V (O_{n}^{*})

$C_{1} = {w_{i} | 1 \leq i \leq \frac{n}{2}} \cup {w_{i} | \frac{n}{2} + 2 \leq i \leq n}$ ;
$C_{2} = {u_{i} |$ for odd $i, 3 \leq i \leq n - 1}$ ∪ ${v_{i} |$ for even $i, 2 \leq i \leq n}$ ∪ ${x_{i} |$ for odd $i, 1 \leq i \leq n - 1}$ ;
$C_{3} = {u_{i} |$ for even $i, 2 \leq i \leq n}$ ∪ ${v_{i} |$ for odd $i, 1 \leq i \leq n - 1}$ ∪ ${x_{i} |$ for even $i, 2 \leq i \leq n}$ ;
$C_{4} = {u_{1}}$ ;
$C_{5} = {w_{\frac{n}{2} + 1}}$ .

For

\frac{n}{2}

even the color codes of all the vertices of

V (O_{n}^{*})

are:

c_{Π} (u_{i}) = \{\begin{matrix} 0, & for the second component, odd i, 3 \leq i \leq n - 1, n \geq 4 \\ for the third component, even i, 2 \leq i \leq n, n \geq 4 \\ for the fourth component, i = 1 \\ 2, & for the second component, i = 1 \\ i - 1, & for the fourth component, 2 \leq i \leq \frac{n}{2} + 1, n \geq 4 \\ n - i + 1, & for the fourth component, \frac{n}{2} + 2 \leq i \leq n, n \geq 4 \\ \frac{n}{2}, & for the fifth component, i = 1 \\ \frac{n}{2} - i + 2, & for the fifth component, 2 \leq i \leq \frac{n}{2} + 1, n \geq 4 \\ i - \frac{n}{2} - 1, & for the fifth component, \frac{n}{2} + 2 \leq i \leq n, n \geq 4 \\ 1, & otherwise . \end{matrix}

c_{Π} (v_{i}) = \{\begin{matrix} 2, & for the first component, 1 \leq i \leq n, n \geq 4 \\ 0, & for the second component, even i, 2 \leq i \leq n, n \geq 4 \\ for the third component, odd i, 1 \leq i \leq n - 1, n \geq 4 \\ i, & for the fourth component, 1 \leq i \leq \frac{n}{2}, n \geq 4 \\ n - i + 2, & for the fourth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 4 \\ \frac{n}{2} + i, & for the fifth component, i = 1 \\ \frac{n}{2} - i + 3, & for the fifth component, 2 \leq i \leq \frac{n}{2} + 1, n \geq 4 \\ i - \frac{n}{2}, & for the fifth component, \frac{n}{2} + 2 \leq i \leq n, n \geq 4 \\ 1, & otherwise . \end{matrix}

c_{Π} (w_{i}) = \{\begin{matrix} 0, & for the first component, 1 \leq i \leq \frac{n}{2}, n \geq 4 \\ for the first component, \frac{n}{2} + 2 \leq i \leq n, n \geq 4 \\ for the fifth component, i = \frac{n}{2} + 1 \\ 2, & for the first component, i = \frac{n}{2} + 1 \\ for the second component, i = n \\ i, & for the fourth component, 1 \leq i \leq \frac{n}{2}, n \geq 4 \\ n - i + 1, & for the fourth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 4 \\ \frac{n}{2} - i + 2, & for the fifth component, 1 \leq i \leq \frac{n}{2}, n \geq 4 \\ i - \frac{n}{2}, & for the fifth component, \frac{n}{2} + 2 \leq i \leq n, n \geq 4 \\ 1, & otherwise . \end{matrix}

c_{Π} (x_{i}) = \{\begin{matrix} 0, & for the second component, odd i, 1 \leq i \leq n - 1, n \geq 4 \\ for the third component, even i, 2 \leq i \leq n, n \geq 4 \\ i + 1, & for the fourth component, 1 \leq i \leq \frac{n}{2}, n \geq 6 \\ n - i + 2, & for the fourth component, \frac{n}{2} + 1 \leq i \leq n, n \geq 4 \\ \frac{n}{2} - i + 3, & for the fifth component, 1 \leq i \leq \frac{n}{2}, n \geq 4 \\ i - \frac{n}{2} + 1, & for the fifth component, \frac{n}{2} + 2 \leq i \leq n, n \geq 4 \\ 1, & otherwise . \end{matrix}

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}^{*}) \leq 5

, for

\frac{n}{2}

even,

n \geq 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 \geq 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

Chartrand, G.; Zhang, P.; Salehi, E. On the partition dimension of a graph. Congr. Numer. 1998, 131, 55–66. [Google Scholar] [CrossRef]
Chartrand, G.; Zhang, P.; Salehi, E. The Partition Dimension of a Graph. Aequ. Math. 2000, 55, 45–54. [Google Scholar] [CrossRef]
Khuller, S.; Raghavachari, B.; Rosenfeld, A. Landmarks in graphs, Discrete Applied Mathematics. DIscrete Appl. Math. 1996, 70, 217–229. [Google Scholar] [CrossRef] [Green Version]
Saenpholphat, V.; Zhang, P. Conditional resolvability: A survey. Int. J. Math. Math. Sci. 2004, 38, 1997–2017. [Google Scholar] [CrossRef] [Green Version]
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]
Chartrand, G.; Zhang, P. The theory and applications of resolvability in graphs: A survey. Congr. Numer. 2003, 160, 47–68. [Google Scholar]
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]
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]
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]
Asmiati, A. The Locating-Chromatic Number of Non-Homogeneous Amalgamation of Stars. Far East J. Math. Sci. 2014, 93, 89–96. [Google Scholar]
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]
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]
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]
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]
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]
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]
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]
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]
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]
Irawan, A.; Asmiati, A. The locating-chromatic number of subdivision firecrackers graphs. Int. Math. Forum 2018, 13, 485–492. [Google Scholar] [CrossRef]
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]
Behtoei, A.; Anbarloei, M. The locating chromatic number of the join of graphs. Bull. Iran. Math. Soc. 2014, 40, 1491–1504. [Google Scholar]
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}

Figure 2. A subdivision of an origami graph

O_{5}^{*}

Figure 2. A subdivision of an origami graph

O_{5}^{*}

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

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://doi.org/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://doi.org/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://doi.org/10.3390/a14060167

APA Style

Irawan, A., Asmiati, A., Zakaria, L., & Muludi, K. (2021). The Locating-Chromatic Number of Origami Graphs. Algorithms, 14(6), 167. https://doi.org/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 Menu

The Locating-Chromatic Number of Origami Graphs

Abstract

1. Introduction

2. Results and Discussions

2.1. Locating-Chromatic Number of Origami Graphs

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

3. Conclusions

Author Contributions

Funding

Data Availability Statement

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI