Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 39 for “"Edge-connectivity"”.
-
Generalized edge connectivity in graphs
The edge-connectivity l of a connected graph is the minimum number of edges whose deletion produces a graph with two components. For an integer l > 1, the l-edge connectivity of a graph with | V| ≥ l, denoted by l l, is the smallest number of edges whose removal results in a graph with l …
-
Colorings of Randomly Augmented Graphs and a Maker-Strategy for the k-Edge-Connectivity Game
In this thesis the behavior of two graph properties on randomly augmented graphs are studied, as well as multiple Maker-Breaker games. It contains tight upper bounds for the chromatic number and the choice number of randomly augmented graphs. Furthermore it gives an upper bound for the number of …
-
Edge-disjoint Linkages in Infinite Graphs
… Ok, Richter, and Thomassen [18]. We show that an edge-connectivity of (k+1) is enough to have a weak k-linkage in infinite graphs in case k is odd, Theorem 3.3.6. Thus proving that Huck's theorem holds for infinite graphs. This is only one step far away from the conjecture, which has an …
-
Integer flow and Petersen minor
… from the Petersen graph by contracting mu edges from a perfect matching. In chapter 1 we prove that every bridgeless P10 3&d1; -minor free graph admits a nowhere-zero 4-flow.;Walton and Welsh [48] proved that if a coloopless regular matroid M does not have a minor in {lcub}M(K 3,3), …
-
Connectivity and spanning trees of graphs
This dissertation focuses on connectivity, edge connectivity and edge-disjoint spanning trees in graphs and hypergraphs from the following aspects.;1. Eigenvalue aspect. Let lambda2(G) and tau( G) denote the second largest eigenvalue and the maximum number of edge-disjoint spanning trees of a graph …
-
Structure and constructions of 3-connected graphs
… to find certifying algorithms that test 3-connectivity; in fact, the currently fastest algorithms need quadratic time. Two classic results in graph theory due to Barnette, Grünbaum and Tutte show that 3-connected graphs can be characterized by the existence of certain inductively defined …
-
Node-weighted prize-collecting survivable network design problems
… undirected graph $G=(V,E)$ and integral connectivity requirements $r(st)$ for each pair of nodes $st$. The goal is to find a minimum node-weighted subgraph $H$ of $G$ such that, for each pair $st$, $H$ contains $r(st)$ \emph{disjoint} paths between $s$ and $t$. PC-SNDP is a generalization …
-
Algorithms for Computing Edge-Connected Subgraphs
… on algorithms for finding all the maximal k-edge-connected components in a given graph G = (V, E) where V and E represent the set of vertices and the set of edges, respectively, which are further used to develop a scale reduction procedure for the maximum clique problem. The proposed …
-
System for Collision Detection Between Deformable Models Built on Axis Aligned Bounding Boxes and GPU Based Culling
… deformations and deformations that preserve edge connectivity. We propose a new system built as a combination of Graphics Processing Unit (GPU) based culling and Axis Aligned Bounding Box (AABB) based culling. Techniques for performing hierarchy-less GPU-based culling are given. We then …
-
Unavoidable Immersions and Topological Minors of k-edge-connected Graphs
… unavoidable structures in large and infinite k-edge-connected graphs. These results are inspired by the classical result of Ramsey, who proved that for every positive integer r, every sufficiently large graph contains as an induced subgraph either Kr or $\overline{Kr}$. We consider different …
-
Weighted Modulo Orientations of Graphs
… 3-Flow Conjecture (1972) states that every 4-edge-connected graph admits a nowhere-zero 3-flow. Extending Tutte's flows conjectures, Jaeger's Circular Flow Conjecture (1981) says every 4k-edge-connected graph admits a modulo (2k+1)-orientation, that is, an orientation such that the indegree is …
-
Densities in graphs and matroids
… can be described by the distribution of the edges in its subgraphs. For example, a cycle C is a graph that satisfies |E(H)| |V (H)| < |E(C)| |V (C)| = 1 for all non-trivial subgraphs of C. Similarly, a tree T is a graph that satisfies |E(H)| |V (H)|−1 ≤ |E(T)| |V (T)|−1 = 1 for all …
-
Algorithm design and engineering for graph connectivity problems
… with topics related to some notions of graph connectivity in directed graphs and mixed graphs. The edge and vertex connectivity of a graph are important measures of its resilience as a network. There is a great variety of real-life relations that can be modeled by graphs. A few of the most …
-
Combinatorially Thin Trees and Spectrally Thin Trees in Structured Graphs
… simpler estimates of $G$ with possibly fewer edges or vertices while capturing some of its specific properties has been used in order to design efficient algorithms. The concept of estimating a graph with a simpler graph is known as graph sparsification. Spanning trees are an important family …
-
Thin Trees in Some Families of Graphs
… maximum over all cuts of the proportion of the edges of 𝑇 in the cut. Thin trees play an important role in some recent papers on the Asymmetric Traveling Salesman Problem (ATSP). Goddyn conjectured that every graph of sufficiently large edge-connectivity has a spanning tree 𝑇 such that 𝜌(𝑇) ≤ 𝜀. …
-
Integer flows and Modulo Orientations
… 3-flow conjecture (1970's) states that every 4-edge-connected graph admits a nowhere-zero 3-flow. A graph G admits a nowhere-zero 3-flow if and only if G has an orientation such that the out-degree equals the in-degree modulo 3 for every vertex. In the 1980ies Jaeger suggested some related …
-
On the independent spanning tree conjectures and related problems
We say that trees with common root are (edge-)independent if, for any vertex in their intersection, the paths to the root induced by each tree are internally (edge-)disjoint. The relationship between graph (edge-)connectivity and the existence of (edge-)independent spanning trees is explored. The …
-
Matchings, Connectivity, and Eigenvalues in Regular Graphs
… $n$-vertex connected regular graphs in terms of edge-connectedness and determine when the matching number is minimized. We also establish the best upper bound for the number of cut-edges over $n$-vertex connected odd regular graphs and determine when the number of cut-edges is maximized. In …
-
Betti Numbers Of Stanley-Reisner Ideals
… in four related areas. • Jump Sequences of Edge Ideals: Given a graph G on n vertices with edge ideal IG , we introduce a new invariant Jump(IG ) which describes the possible Betti tables of IG . We show that the smallest k such that [beta]k,k+3 (IG ) = 0 is bounded below in terms of …
-
Jaeger’s Strong 3-Flow Conjecture for Graphs in Low Genus Surfaces
… Tutte posed the 3-Flow Conjecture: that all 4-edge-connected graphs have a nowhere zero 3-flow. This was extended by Jaeger et al. (1992) to allow vertices to have a prescribed, possibly non-zero difference (modulo 3) between the inflow and outflow. He conjectured that all 5-edge-connected …
Page 1 of 2