TOTAL VERTEX IRREGULARITY STRENGTH OF CUBIC GRAPHS

• Main Author: Rikayanti
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/79460
• Institution: Institut Teknologi Bandung

The concept of irregularity strength of a graph was introduced by Chartrand dkk. (1988). The idea became an inspiration for Ba?ca dkk. (2007) to propose the concept of irregular total labeling. Baca et al. defined the total irregular vertex k-labeling of a graph G(V,E) as a mapping ! : V [ E ! {1, 2, 3, · · · , k} such that the weights of all vertices in G are different. The weight of a vertex x is defined as wt(x) = !(x)+ P xy inE(G) !(xy). The total vertex irregularity strength of a graph G, denoted by tvs(G), is the smallest positive integer k such that G has a total irregular vertex k-labeling. Nurdin et.al.(2010) gave a lower bound of the total vertex irregularity strength of any graph G of minimum degree " and maximum degree ! as follows: tvs(G) # max (? " + n! " + 1 ? , ? " + n! + n!+1 " + 2 ? , · · · , & " + P where nk denotes the number of vertices of degree k in G. The total vertex irregularity strength of various classes of graphs that have been known so far are all equal to the above lower bound. In fact, until now there is no total vertex irregularity strength of a graph whose value is higher than the lower bound above. In particular for regular graphs, several results have been obtained. Among them, Ba?ca dkk. (2007) obtains the total vertex irregularity strength for the prism graph. Rajasingh dkk. (2012) and Haque (2012) derived the value of tvs for certain cubic graphs (cycle related graphs) and generalized Petersen. Ahmad dkk. (2013) determined the total vertex irregularity strength for some cubic graphs such as a convex polytope graph that has a pair of n-side faces, 2n 5-side faces and nm 6-side faces in the plane, Goldberg snarks, necklace graphs, certain planar graphs and crossed prisms. Indriati dkk. (2016) gives the result for the total vertex irregularity strength of the generalized helm graph and the prism graph with outer pendant edges. However, determining the total vertex irregularity strength for some cubic graphs, in general, is still an open problem. The focus of this research is to examine how to calculcate the total vertex irregu larity strength of cubic graphs. The labeling technique to obtain the total vertex irregular k-labeling in this research is given in some algorithms. Most of the previous methods to calculate the total vertex irregularity strength worked based on the characteristics of the class of graph being studied. The proposed algorithms works based on how to order the vertices and and assigns vertex weights to a graph. The method used in vertex ordering is (Bread-First Search/BFS). In addition, the mechanism for labeling edges and vertices is an important part of this research. The graph that is used as the object of research is included in the cubic graph, namely prism graphs, some platonic graphs (tetrahedron, cubical, dodecahedron), symmetric cubic graphs as a result of Foster’s census, and permutation graphs (family of fench graphs and burger graphs). The algorithm used on that cubic graph produces the total vertex irregular k-labeling. Furthermore, the largest labels (edges and vertices) resulting from this labeling have the same value as the lower bound given by Nurdin dkk. (2010). This means that the largest labels (edges and vertices) are the same as the total vertex irregular k-labeling of some cubic graphs. The results of this research also prove the truth of the conjecture given by Nurdin dkk. (2010). Therefore, this research produces a uniform technique in determining the total vertex irregular k-labeling on cubic graphs.