On The Structure Of Twisted Hypercubes And Planar Graphs

With the rapid development of digital communication technology and computer tech-nology,a large amount of information needs to be encoded and transmitted in computer networks.The reliability,validity,adaptability and efficiency of coding method and sig-nal transmission on the channel are important topics in the study of conputer networks.This thesis studies the structure of some special classes of graphs that are motivated by these problems in computer networks.The first part of the thesis studies fault-diameter and wide-diameter of twisted hy-percubes.Fault-diameter and wide-diameter are parameters that measure the reliability and efficiency of a network.Assume G is l-connected.The l-fault-diameter of a graph G is the minimum d such that the diameter of G-X is at most d for any subset X of V(G)of size |X|?l-1.The l-wide-diameter of G is the minimum integer d for which there exists at least l internally vertex disjoint paths of length at most d between any two distinct vertices in G.Given the number of vertices and the maximum degree of G,hypercubes and twisted hypercubes have small diameter and have good extensibility.Therefore,hypercubes and twisted hypercubes are widely used in network design.In this thesis,we introduce the concept of random twisted hypercube(RQn)and study the fault-diameter and wide-diameter of three special twisted hypercubes Zn and Hn,and RQn,and prove the following results:(1)For any integers n ? 3,for any Gn ? Qn,dnf(Gn)?3n-5 and dn(Gn)?3n-6.(2)Assume H is a closed family of twisted hypercube and Hn denotes the family of n-dimension twisted hypercubes in H.If f(n)is a non-decreasing function such that for any n ? 1 and Gn?Hn,d(Gn)? f(n),then for all n,Gn ? Hn and for all 1 ? l ?n,dlf(Gn)? f(n)+2[log2l].(3)For any integers k and n?k+2?k+ 2 ? 3,the n-fault-diameter of Zn,k is at most n/k+1+2[log2 n];the k-wide-diameter of Zn,k is at most[n/k+1]+ 2k + k+4.In particular,if k=[log2n-2log2log2n],then the n-fault-diameter and k-wide-diameter of Zn,k are(1 + o(1)))n/log2n,which are asymptotically optimal;(4)For any positive integer n and ?(n)=[log2 n-2 log2 log2 n].the n-fault-diameter of Hn is(1+o(1))n/log2n;the ?(n)-wide-diameter of Hn is(1+o(1))n/log2n,which are asymptotically optimal.(5)For any positive integer n,asymptotically almost surely,RQn has n-wide-diameter(1+o(1))n/log2n.The second part of this thesis studies induced d-degenerate subgraph of planar graph-s.The problem of induced 1-degenerate subgraph is equivalent to the problem of foodback set.The feedback set of graphs has wide application in operating systems,database sys-tems,and VLSI chip design.Planar graph is a very important graph family in network design.In this thesis we study the maximum induced 3-degenerate subgraph and 2-degenerate subgraph of a planar graph,and prove the following two results:(6)Every n-vertex planar graph has an induced 3-degenerate subgraph of order at least 5n/7.(7)Every n-vertex planar graph without 3-face adjacent to 4--face has an induced 2-degenerate subgraph of order at least 2n/3.