Files in this item
Files  Description  Format 

application/pdf 9124439.pdf (4MB)  (no description provided) 
Description
Title:  Studies in connectivity 
Author(s):  Kézdy, André E. 
Doctoral Committee Chair(s):  West, Douglas B. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
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 rbranching is a directed spanning tree rooted at r. Suppose that every vertex in V $$ r is kedgeconnected from r. A theorem of Edmonds guarantees the existence of k edgedisjoint rbranchings in G. We provide an algorithm to construct the k edgedisjoint rbranchings 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 $3n5$ 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 5connected, that no minorminimal counterexample contains $K\sb4e,$ and that Dirac's conjecture is true for all graphs embeddable in a surface with Euler characteristic ${\ge}{}2.$ An edgeordered 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 edgeversion of Menger's Theorem for edgeordered 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 kedgeconnected edgeordered 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 maxflow/mincut theorem for edgeordered graphs. The dgirdle 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 dgirdle 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 dgirdle, has a vertex with degree at least $2d  1.$ We prove that the maximum 3girth of a 4regular 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:  20110507 
Identifier in Online Catalog:  AAI9124439 
OCLC Identifier:  (UMI)AAI9124439 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois