Research On The Strong Chromatic Index Of Subdivisions Of Graphs

A strong edge coloring of a graph is an assignment of some colors to the edges of the graph such that for every color,the set of edges that given that color froms an induced matching in the graph;The strong chromatic index of a graph G,denoted by ?s'(G),is the minimum number of colors needed in a strong edge coloring of G.To subdivide an edge e is to delete e,add a new vertex x,and join x to the ends of e.A k-subdivision of a graph G,denoted by G(k),is a graph in which each edge of G is subdivided exactly k times.Suppose that Pm and Pn are two paths on rn vertices and on n vertices,respectively.The planar(m,n)-grid graph is defined to be the product graph Pm?Pn.We use Kn,to denote the complete graph on n vertices.In this thesis,we study the strong chromatic indexes of the k-subdivisions of planar grid graphs Pm?Pn and the the strong chromatic indexes of the k-subdivisions of complete graphs Kn.The main results of this thesis are as follows:(1)For planar grid graphs G = Pm?Pn,when m=1 or n = 1,if e(G)<3,then?s'(G)= e(G),and if e(G)? 3.then ?s'(G)=3;when m = 2,n = 2,we have ?s'(G)= 4;when m = 2,n? 3 or m?3,n= 2,we have ?s'(G)= 6;when m ?3,n?3,we have?s'(G)= 8.(2)Let G(k)be the k-subdivision graph of planar grid graph G = Pm?Pn.When m= 1,or n=1,if e(G(k))<3,then ?s'(G(k))?e(G(k)),and if e(G(k))?3,then?s'(G(k))=3;when m=2,n = 2.if k+ 1 is divisible by 3,then ?s'(G(k))?3,and if k + 1 is not divisible by 3,then x's(G(k))= 4;when m = 2,n?3 or m?3,n = 2,we have?s'(G(k))4;when m ? 3,n ? 3,we have ?s'(G(k))=5.(3)For complete graph H = Kn(n ? 2),we have ?s'(H)=(2n).(4)Let H(k)be the k-subdivision graph of complete graph Kn,When k= 1,we have?s'(H(k))=n;when k ? 2,we have ?s'(H(k))=3 if n= 2,and ?s'(H(k))=n if n ? 3.