File | Description | Format |
---|---|---|
9124439.pdf (4MB) | (no description provided) |
Title: | Studies in connectivity |
Author(s): | Kezdy, Andre E. |
Doctoral Committee Chair(s): | West, Douglas B. |
Department / Program: | Mathematics |
Discipline: | Mathematics |
Degree Granting Institution: | University of Illinois at Urbana-Champaign |
Genre: | Dissertation |
Subject(s): |
Mathematics
Computer Science |
Abstract: | This thesis investigates several aspects of connectivity, mainly focusing on the structure of highly connected graphs and partially ordered sets. Let G(V, E) be a directed multigraph and r a vertex of G. An r-branching is a directed spanning tree rooted at r. Suppose that every vertex in V $-$ r is k-edge-connected from r. A theorem of Edmonds guarantees the existence of k edge-disjoint r-branchings in G. We provide an algorithm to construct the k edge-disjoint r-branchings in $O(k\sp2\vert V\Vert E\vert)$ time. Let x be an element of a partial order P. A set $S \subseteq P$ is a cutset for x if S $\cup$ x meets every maximal chain of P and x is incomparable to every element of S. The cutset number of P is the minimum m such that every element of P has a cutset of size at most m. Let w(m, h) be the maximum width of a poset with height h and cutset number m. We determine the order of growth of w(m, h) for fixed m and fixed $h\: w(m, h) = O(h\sp{\lfloor m/2\rfloor})$ for fixed m, and $w(m,h) = O(m\sp h)$ for fixed h. A conjecture of Dirac states that any simple graph with n vertices and $3n-5$ edges contains a subdivision of K$\sb5$. By Kuratowski's Theorem, no planar graph contains a subdivision of K$\sb5$; thus, Dirac's conjecture, if true, would be sharp. We prove that a topologically minimal counterexample to the conjecture is 5-connected, that no minor-minimal counterexample contains $K\sb4-e,$ and that Dirac's conjecture is true for all graphs embeddable in a surface with Euler characteristic ${\ge}{-}2.$ An edge-ordered graph consists of a labeled graph and a binary relation R on labels of the edges of the graph. We prove an analogue of the edge-version of Menger's Theorem for edge-ordered graphs, observing that the relation R must be transitive for the natural analogue to hold. We investigate the problem of determining the minimum number of edges in a k-edge-connected edge-ordered graph where R is a linear order. Improving previous lower bounds, we prove that such a graph must have at least $\lceil(k + 3)(n - 1)/2\rceil - \lfloor\log\sb2(n)\rfloor$ edges, for $k \le n - 2.$ Finally we prove a max-flow/min-cut theorem for edge-ordered graphs. The d-girdle of a graph is the cardinality of a smallest vertex induced subgraph with minimum degree d. A simple graph on n vertices is guaranteed to have a d-girdle provided it has at least$$e(n,d) = (d - 1) n - {d\choose 2} + 1$$edges. Answering a question posed by Erdos, we prove that a simple graph on n vertices, e(n,d) edges with no proper d-girdle, has a vertex with degree at least $2d - 1.$ We prove that the maximum 3-girth of a 4-regular graph is $\lfloor(9n + 1)/10\rfloor,$ and conjecture that $\lceil4 n/5\rceil$ is the correct upper bound. |
Issue Date: | 1991 |
Type: | Text |
Language: | English |
URI: | http://hdl.handle.net/2142/19100 |
Rights Information: | Copyright 1991 Kezdy, Andre E. |
Date Available in IDEALS: | 2011-05-07 |
Identifier in Online Catalog: | AAI9124439 |
OCLC Identifier: | (UMI)AAI9124439 |