Goodall, Sarah Jane
(1995)
Problems in combinatorics: Paths in graphs, partial orders of fixed width.
PhD thesis, London School of Economics and Political Science.
Abstract
This thesis contains results in two areas, that is, graph theory and partial orders. (1) We consider graphs G with a specified subset W of vertices of large degree. We look for paths in G containing many vertices of W. The main results of the thesis are as follows. For G a graph on n vertices, and W of size w and minimum degree d, we show that there is always a path through at least vertices of W. We also prove some results for graphs in which only the degree sums of sets of independent vertices in W are known. (2) Let P = (X, ) be a poset on a set {lcub}1, 2,..., N{rcub}. Suppose X1 and X2 are a pair of disjoint chains in P whose union is X. Then P is a partial order of width two. A labelled poset is a partial order on a set {lcub}1, 2,..., N{rcub}. Suppose we have two labelled posets, P1 and P2, that are isomorphic. That is, there is a bijection between P1 and P2 which preserves all the order relations. Each isomorphism class of labelled posets corresponds to an unlabelled poset. (Abstract shortened by UMI.).
Actions (login required)
 |
Record administration - authorised staff only |
Download statistics
Download statistics