| In this paper, we mainly do some research on threshold graphs and quasi-threshold graphs, solving several optimization problems on the basis of their special structure.In the first chapter, we study the structure of threshold graphs firstly, concluding that this class of graph is obtained from some vertices which act as universal vertices or isolated vertices. After mastering its structure, we design a polynomial time algorithm to construct its cent-tree and arborescence representation, which well reflect its structure. On this basis, we solve following optimization problems on threshold graphs successfully: (1) constructing a polynomial time algorithm to recognize a threshold graph; (2) finding out the maximum clique and minimum edge-cut of a threshold graph; (3) constructing the arborescence representation of a threshold graph, finding out the maximum dependent set which is made up by all leaves of its arborescence representation and computing the chromatic number; (4) presenting a sufficient and necessary condition for a threshold graph to be Hamiltonian; (5)calculating the bandwidth of a threshold graph with a polynomial time algorithm.In the second chapter, we construct the arborescence representation of the quasi-threshold graph; meantime, we can recognize a quasi-threshold graph with the same algorithm. Because a graph is a quasi-threshold graph if and only if each connected component of it is the induced graph of some arborescence. Then, we construct the cent-tree of a quasi-threshold graph according to its arborescence, which makes it convenient to solve following optimization problems on quasi-threshold graphs: (1) finding out the chromatic number, the maximum dependent set and the minimum clique coverage of a quasi-threshold graph; (2) calculating the bandwidth of a quasi-threshold graph; (3) presenting a condition for a quasi-threshold graph to be Hamiltonian; (4) designing a polynomial time algorithm to calculate the edge-dominating number. |
PDF Full Text Request