{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19100"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19100","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Studies in connectivity","abstract":"This thesis investigates several aspects of connectivity, mainly focusing on the structure of highly connected graphs and partially ordered sets.","abstract_html":"This thesis investigates several aspects of connectivity, mainly focusing on the structure of highly connected graphs and partially ordered sets.","abstract_has_math":false,"creators":["Kézdy, André E."],"institution":"University of Illinois at Urbana-Champaign","degree_name":null,"degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["West, Douglas B."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"10000-01-01","date_published":"10000-01-01","updated_at":"2026-07-22T22:25:12Z","subjects":["Mathematics","Computer Science"],"languages":["eng"],"rights":["Copyright 1991 Kezdy, Andre E."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9124439","(UMI)AAI9124439"],"render_values":[{"text":"AAI9124439","href":null,"code":true},{"text":"(UMI)AAI9124439","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19100","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["West, Douglas B."]},{"key":"dc:creator","label":"Author","values":["Kézdy, André E."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["10000-01-01","2011-05-07T11:56:57Z","1991"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1991 Kezdy, Andre E."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9124439","(UMI)AAI9124439","http://hdl.handle.net/2142/19100"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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"]},{"key":"dc:title","label":"Title","values":["Studies in connectivity"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B."],"dc:creator":["Kézdy, André E."],"dc:date":["10000-01-01","2011-05-07T11:56:57Z","1991"],"dc:description":["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"],"dc:identifier":["AAI9124439","(UMI)AAI9124439","http://hdl.handle.net/2142/19100"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Kezdy, Andre E."],"dc:subject":["Mathematics","Computer Science"],"dc:title":["Studies in connectivity"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:12Z"}