 # Problems in combinatorics: Paths in graphs, partial orders of fixed width.

Goodall, Sarah Jane (1995) Problems in combinatorics: Paths in graphs, partial orders of fixed width. PhD thesis, London School of Economics and Political Science (United Kingdom).  Preview
PDF

## 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.).

Item Type: Thesis (PhD) Mathematics Collections > ProQuest Etheses http://etheses.lse.ac.uk/id/eprint/2447 Record administration - authorised staff only