Cookies?
Library Header Image
LSE Theses Online London School of Economics web site

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

[img]
Preview
PDF
Download (4MB) | Preview

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)
Uncontrolled Keywords: Mathematics
Sets: Collections > ProQuest Etheses
URI: http://etheses.lse.ac.uk/id/eprint/2447

Actions (login required)

Record administration - authorised staff only Record administration - authorised staff only

Downloads

Downloads per month over past year

View more statistics