Files in this item



application/pdf9124439.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Studies in connectivity
Author(s):Kézdy, André E.
Doctoral Committee Chair(s):West, Douglas B.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
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
Rights Information:Copyright 1991 Kezdy, Andre E.
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9124439
OCLC Identifier:(UMI)AAI9124439

This item appears in the following Collection(s)

Item Statistics