In this thesis, we consider two different types of subgraph sequences. The first is a decomposition of a graph (or digraph) where the subgraphs form a sequence where each successive subgraph contains an isomorphic copy of the subgraph which precedes it along with exactly one additional edge (or arc). Such a decomposition is called an ascending subgraph decomposition or ASD. It is conjectured that every graph of positive size has an ASD. Since it was posed in 1987, the Ascending Subgraph Decomposition Conjecture has been proven true for several classes of graphs. We investigate the similar problem for several digraphs. Among other results, we prove that tournaments whose order is congruent to 1, 2, or 3 modulo 6 have ASDs.; The second problem that we consider is a connectivity property. We prove the existence of a certain sequence of path systems in a graph. Let S&ar; = (a1, a2, ... , ak, b1, b2, ..., bk) be the vector of 2k distinct vertices of G. We say that a path system P = {lcub}P1, P2..., Pk{rcub} is an S&ar; -linkage if for all i = 1, 2,..., k, Pi is an [ai, bi]-path. We call |V(P1) ∪ V(P2) ∪ ··· ∪ V (Pk)|, the order of the S&ar; -linkage. A graph G is said to be pan-k-linked if it is k-linked and for all vectors S&ar; of 2k distinct vertices of G, there exists an S&ar; -linkage of order t for all t such that T ≤ t ≤ |V( G)|, where T denotes the minimum possible order of an S&ar; -linkage in G. For k ≥ 2, we show that for a graph G of order n ≥ 5 k - 2, n+k-12 is the minimum degree necessary to ensure that G is pan-k-linked.
展开▼
