THE STRONG 3-RAINBOW INDEX OF SOME GRAPHS AND CERTAIN GRAPHS FORMED BY GRAPH OPERATIONS

• Main Author: Yumni Awanis, Zata
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/51964
• Institution: Institut Teknologi Bandung

Let G be a simple connected graph of order n with an h-edge coloring c : E(G) ! f1; 2; : : : ; hg, h 2 N, where adjacent edges may be colored the same. Let k be an integer with k 2 f2; 3; : : : ; ng. A tree T in G is a rainbow tree if no two edges of T have the same color. Let S V (G) with jSj = k. An h-edge coloring c of G is called a strong k-rainbow h-edge coloring of G if for every set S of G, there exists a rainbow tree with minimum size containing S. The strong k-rainbow index of G, denoted by srxk(G), is the minimum h such that G admits a strong k-rainbow h-edge coloring. The strong k-rainbow index has an interesting application in the security of information exchange in a communication network. For example, if it is desired to exchange information between k people safely, then each line which connects them must be assigned by some passwords so that no password is repeated. The minimum number of passwords needed in a communication network so that every k people is connected by a secure and short line is represented by the strong k-rainbow index of a graph. Determining the strong k-rainbow index of any graph is NP-Complete. Hence, this dissertation is focused on strong 3-rainbow index. We characterize certain graphs having strong 3-rainbow index which is equal to 2. We also determine the strong 3-rainbow index of some graphs and certain graphs formed by graph operations, such as such as edge-amalgamation, vertex-comb product, edge-comb product, and corona product. Graph operations have an important role in forming a larger and complex communication network.