This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/19100
Description
Title
Studies in connectivity
Author(s)
Kézdy, André E.
Issue Date
1991
Doctoral Committee Chair(s)
West, Douglas B.
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Level
Dissertation
Keyword(s)
Mathematics
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
