The Maximum Leaf Spanning Tree And The Maximum Nonseparating Independent Sets Of Cylinder Graphs

This dissertation mainly studies the maximum leaf spanning tree and maximum nonseparating independent sets problem for the cylinder graphs,called cartesian product graphs of path and circle(P_m×C_n).Chapter 1 introduces research status of maximum leaf spanning tree,maximum nonseparating independent sets and minimum connected vertex cover.Chapter 2 studies the maximum leaf spanning tree problem for the Cylin-der graphs.According to the characteristics of spanning trees,the max number of leaves in any spanning trees of the P_m×C_n(m=2,3)is abtained.Then according to the num-bers of the degree 2 and 3 in spanning tree,we get the upper bound of the number of leaves in any spanning trees of P_m×C_n.Finally we show the upper bound of the max number of leaves in any spanning trees of the P₄×C_nby construction.In chapter 3,we use the equivalence relation between the maximum nonseparating independent sets and the independent sets of leaves of spanning trees.By construction and analysis,the exact values of the nonseparating independence numbers for P_m×C_n(m=2,3)are obtained and the independent sets as required are constructed.For m=4,5,6,we get the bound by counstruction.