Wide, Filling And Tree Of Some Graph

The problem of graph labeling and embedding is an active topoic in combinatorial and optimization. It includes a series of rich theory and strong application. This thesis studys two of these problems. They are as follows:1. Fill-in problem of some special graphs.In practice, we often deal with solving a system of linear equations AX=b, where A is an nXn symmetric sparse matrix, which contains many zero elements and little nonzero elements. In the course of solving a system of linear equations with the Gauss elimination or Cholesky decomposition, some elements which changes from zero to nonzero are called fill-in of matrix. If the order of elimintion is not approprate, the nonzero elements will in crease, that will affect the efficiency and speed of work, So it is necenssary to choose the order of elimination. Because a graph is corresponded with a symmetric matrix, the fill-in problem of graph is caused.The NP-completeness of fill-in problem on general graph is proved by literature[12-14]. So it is impossible to have a good Algorithm, and the researchers concentrate on the graph which has special structure, and build some reduction rules to get the fill-in number of special graph, including dimensional reduction and decomposition theorems. Moreover, we can use of the different presentation of fill-in and some boundary inequality to get the fill-in of special graph. This paper gets some results on special graphs, which includes the complement graph of trees and forests, and grid graphs. The main results on the fill-in of graphs are as follows:be a non-empty forest, then>e a non-empty tree , thendenote the join of n graphs ,thenbe a grid graph on a fan , then2. The treewidth of some special graphsThe treewidth was presented at first when Robertson and Seymour build the theory of graph minors. The other parameter "nuclear density"was raised form the algorithmic complexity evaluation by [8]. The equivalence of these two concepts was proved by [9],corresponding to the wavefront of matrix A. The problem was studied in these following aspects: the algorithmic theory and the computational complexity, the results of special graphs et. The NP-completeness for the treewidth of general graph was proved by literature [15J in 1987, but the treewidth of chordal graph can be solved polynomial time. So the researchers have begun to study the results of special graphs, the results on treewidth are still fewer than that other labeling problem. It has reduction rules and decomposition theorems too. Moreover, if the lower bounds of the treewidth of a graph is known, the treewidth can be obtained by constructed a reaching labeling, the main results on the treewidth of graphs are as follows:...