# Studies in connectivity

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

## Files in this item

File Description Format
9124439.pdf (4MB) (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