RAINBOW CONNECTION NUMBERS OF SOME GRAPHS OF FINITE GROUPS

• Main Author: Febrian Umbara, Rian
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/84337
• Institution: Institut Teknologi Bandung

Consider a connected graph G with edge coloring, where adjacent edges may have the same color. A path in G is called a rainbow path if no two edges on the path share the same color. The rainbow connection number of G, denoted as rc(G), is the minimum number of colors required to color the edges of G so that every two distinct vertices in G are connected by a rainbow path. The rainbow connection number of a graph can be used to model secure communication between agents in a communication network represented by the graph. In every communication path between two agents in the network, there may be several intermediary agents. To ensure the security of information transmission along the path, different ciphers are required for each direct link between two agents in the path. These different ciphers are represented as edge colors in the graph. For the purpose of efficient data storage, the number of ciphers used must be minimized while still guaranteeing the confidentiality of communication. Besides modeling the security of information transmission in a communication network, some studies have shown that the rainbow connection number is related to the algebraic properties of finite groups. The relationship between the rainbow connection number and the algebraic properties of finite groups is examined in research on the rainbow connection numbers of graphs derived from finite groups. In recent years, several researchers have investigated the rainbow connection numbers of various graphs from finite groups, including Cayley graphs, noncommuting graphs, undirected power graphs, and enhanced power graphs. However, all the research conducted so far has not examined the relationship between the rainbow connection number of a graph of a finite group and the noninvolution elements, maximal abelian subgroups, and cyclic subgroups within the group. In this dissertation research, the rainbow connection numbers of three other graphs from finite groups are examined: the commuting graph, the inverse graph, and the reduced power graph of a finite group. Additionally, the relationship between the rainbow connection numbers of these three graphs and the algebraic properties of the finite group is studied. The rainbow connection number of the inverse graph of a finite group is related to the noninvolution elements other than the identity element within the group. The rainbow connection number of the commuting graph of a finite group is related to the maximal abelian subgroups of the group. Meanwhile, the rainbow connection number of the reduced power graph of a finite group is related to the cyclic subgroups of the group. Noninvolution elements (if any), abelian subgroups, and cyclic subgroups are important aspects in the structure of a finite group. The research has yielded several results. If the inverse graph of a finite group ? is a connected graph, then ? has a minimal generating set whose members are all noninvolution elements other than the identity element. If the rainbow connection number of the inverse graph of a finite group ? is k, with k ? 2, then every element in ? is the product of r noninvolution elements other than the identity element, with r ? k. If the group ? has a maximal abelian subgroup of order 2, the rainbow connection number of the commuting graph of ? is closely related to the number of maximal abelian subgroups of order 2 in ?. If the group ? does not have a maximal abelian subgroup? of order 2, the rainbow connection number of the commuting graph of ? is closely related to the number of maximal abelian subgroups in ?. Furthermore, it is found that the rainbow connection number of the reduced power graph of a finite group ? is closely related to the number of elements in ? that generate cyclic subgroups of prime order.