THE LOCATING RAINBOW EDGE CONNECTION NUMBERS OF SOME GRAPH CLASSES
Let k be a positive integer and G = (V (G),E(G)) be a finite and connected graph. A rainbow-edge-k-coloring of G is a function c : E(G) ? {1, 2, ..., k} such that for every u and v in V (G) there exists a rainbow edge path that connects them. Let e = uv and f = xy are element of edges in G, denot...
Saved in:
| Main Author: | |
|---|---|
| Format: | Theses |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/87978 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | Let k be a positive integer and G = (V (G),E(G)) be a finite and connected graph.
A rainbow-edge-k-coloring of G is a function c : E(G) ? {1, 2, ..., k} such that
for every u and v in V (G) there exists a rainbow edge path that connects them. Let
e = uv and f = xy are element of edges in G, denoted by d(e, f), defined as
d(e, f) =
(
min{d(u, x), d(u, y), d(v, x), d(v, y)} + 1, if e ?= f;
0, if e = f.
For i ? {1, 2, ..., k}, let Ri be a set of edge with color i and ? = {R1,R2, ...,Rk}
be an ordered partition of E(G). The rainbow code of a edge e ? E(G) with
respect to ? is defined as the k?tuple rc?(e) = (d(e,R1), d(e,R2), ..., d(e,Rk))
with d(e,Ri) = min{d(e, y)|y ? Ri} for each i ? {1, 2, ..., k}. If every edge of
G has distinct rainbow codes, then c is called a locating rainbow edge k?coloring
of G. The locating rainbow edge connection number of G, denoted by recl(G), is
defined as the smallest positive integer k such that G has a locating rainbow edge
k-coloring, denoted by recl(G).
In this thesis, we provide a lower bound and upper bound for the locating rainbow
edge connection numbers of a graph. Furthermore, we determine the locating
rainbow connection number of some classes graph such as a tree graphs, a cycle
graphs, a tadpole graphs, a dumbbell graphs, a triangular snake graphs, and a
slanting ladder graphs. |
|---|