2026-09-21T08:47:22Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/19100 2023-07-10 col_2142_16340 col_2142_5131 com_2142_16339 com_2142_8903 com_2142_5130

10000-01-01 West, Douglas B. Kézdy, André E. 2011-05-07T11:56:57Z 2011-05-07T11:56:57Z 1991 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. Made available in DSpace on 2011-05-07T11:56:57Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9124439.pdf: 3551566 bytes, checksum: 5b89a5f70737b972395069570b5603ba (MD5) Previous issue date: 1991 Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:34:39Z Item is restricted indefinitely. Restriction data tranferred 2014-07-01T11:13:21-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission ETDs are only available to UIUC Users without author permission U of I Only AAI9124439 (UMI)AAI9124439 http://hdl.handle.net/2142/19100 eng Copyright 1991 Kezdy, Andre E. Mathematics Computer Science Studies in connectivity text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation