IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Studies in connectivity

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/19100

Files in this item

File Description Format
PDF 9124439.pdf (4MB) Restricted to U of Illinois (no description provided) PDF
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
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 0
  • Downloads this Month: 0
  • Downloads Today: 0

Browse

My Account

Information

Access Key