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 69 for “"3-connected"”.

  1. Structure and constructions of 3-connected graphs

    The class of 3-connected (i.e., 3-vertex-connected) graphs has been studied intensively for many reasons in the past 50 years. One algorithmic reason is that graph problems can often be reduced to handle only 3-connected graphs; applications include problems in graph drawing, problems related to …

    fu-berlin Repository record for Structure and constructions of 3-connected graphs (opens in a new tab)

  2. Chain Theorems for Different Classes of 3-connected Graphs

    … with new chain theorems for subclasses of 3-connected graphs. These chain theorems provide a systematic approach to characterizing graphs that exclude certain minors, leading to significantly shorter proofs of established results. In Chapter 5, we present a generalization of the block-tree …

    lsu-thes Repository record for Chain Theorems for Different Classes of 3-connected Graphs (opens in a new tab)

  3. Approximating the circumference of 3-connected claw-free graphs

    Jackson and Wormald show that every 3-connected K_1,d-free graph, on n vertices, contains a cycle of length at least 1/2 n^g(d) where g(d) = (log_2 6 + 2 log_2 (2d+1))^-1. For d = 3, g(d) ~ 0.122. Improving this bound, we prove that if G is a 3-connected claw-free graph on at least 6 vertices, then …

    gatech Repository record for Approximating the circumference of 3-connected claw-free graphs (opens in a new tab)

  4. Unavoidable Topological Minors of Large or Infinite 3-connected Rooted Graphs

    … topological minors of large and infinite $ 3 $-connected rooted graphs, where a rooted graph is a graph $ G $ together with a specified subset $ X $ of $ V(G) $ or $ E(G) $. We have two results for finite graphs. First, every $ 3 $-connected finite graph $ G $ with a sufficiently large $ X …

    lsu-thes Repository record for Unavoidable Topological Minors of Large or Infinite 3-connected Rooted Graphs (opens in a new tab)

  5. Chords of longest circuits of graphs

    … Dr. C. Thomassen: Every longest circuit of 3-connected graph has a chord. In 1987, C. Q. Zhang proved that every longest circuit of a 3-connected planar graph G has a chord if G is cubic or if the minimum degree is at least 4. In 1997, Carsten Thomassen proved that every longest circuit of …

    wvu Repository record for Chords of longest circuits of graphs (opens in a new tab)

  6. Circuits and structure in matroids and graphs

    … 1-3, is to produce a unique decomposition of 3-connected matroids into more highly connected pieces. In Chapter 1, we review the definitions and main results from the previous work of Hall, Oxley, Semple, and Whittle. In Chapter 2, we introduce operations that allow us to decompose a 3-connected …

    lsu-thes Repository record for Circuits and structure in matroids and graphs (opens in a new tab)

  7. Extremal Problems in Matroid Connectivity

    … function. We can also say that a matroid is 2-connected if and only if for each pair of elements, there is a circuit containing both elements. Equivalently, a matroid is 2-connected if and only if each pair of elements is in a certain 2-element minor that is 2-connected. Similar results for …

    lsu-thes Repository record for Extremal Problems in Matroid Connectivity (opens in a new tab)

  8. Extremal Connectivity in Graphs and Matroids

    … for cc-minors of sufficiently large loopless $2$-connected graphs. Chapter 3 studies super-minimally $3$-connected graphs, namely $3$-connected graphs that have no proper $3$-connected subgraphs. We establish extremal bounds on structural parameters of these graphs, including the minimum number of …

    lsu-thes Repository record for Extremal Connectivity in Graphs and Matroids (opens in a new tab)

  9. Excluding a Weakly 4-connected Minor

    A 3-connected graph $G$ is called weakly 4-connected if min $(|E(G_1)|, |E(G_2)|) \leq 4$ holds for all 3-separations $(G_1,G_2)$ of $G$. A 3-connected graph $G$ is called quasi 4-connected if min $(|V(G_1)|, |V(G_2)|) \leq 4$. We first discuss how to decompose a 3-connected graph into quasi …

    lsu-thes Repository record for Excluding a Weakly 4-connected Minor (opens in a new tab)

  10. Refining the characterization of projective graphs

    … found the excluded minors for the class of k-connected graphs embeddable on the projective plane for k = 1,2,3. We give a short proof of that result and then determine the excluded minors for the class of internally 4-connected projective graphs. Hall showed that a 3-connected graph …

    lsu-thes Repository record for Refining the characterization of projective graphs (opens in a new tab)

  11. Excluded Structures for Pinch-graphic Matroids and Tournaments

    … M is minimally non-pinch-graphic and M is not 3-connected, then |M| ≤ 20. Furthermore, we characterize all minimally non-pinch-graphic matroids that are not 3-connected. For the 3-connected case, we prove that in a special case, a 3-connected but not internally 4-connected minimally …

    waterloo Repository record for Excluded Structures for Pinch-graphic Matroids and Tournaments (opens in a new tab)

  12. Infinite graphs, graph-like spaces and B-matroids

    … (induced and non-separating) circuits of a $3$-connected graph. He showed that for any two edges of a $3$-connected graph there is a peripheral circuit containing one but not the other, and that the peripheral circuits of a $3$-connected graph generate its cycle space. These theorems were …

    waterloo Repository record for Infinite graphs, graph-like spaces and B-matroids (opens in a new tab)

  13. Claw -free graphs and line graphs

    … by the conjecture of Thomassen that every 4-connected line graph is hamiltonian and by the conjecture of Tutte that every 4-edge-connected graph has a no-where-zero 3-flow. Towards the hamiltonian line graph problem, we proved that every 3-connected N2-locally connected claw-free graph is …

    wvu Repository record for Claw -free graphs and line graphs (opens in a new tab)

  14. Comparing 3-Connectedness and Roundness in Matroid Theory

    … uniform matroids, and various levels of connected matroids. Some of the most important problems in matroid theory involve characterizing classes of matroids so that such characterizations can be used to prove results concerning these matroid classes. This thesis is a study of two …

    csusb Repository record for Comparing 3-Connectedness and Roundness in Matroid Theory (opens in a new tab)

  15. On Properties of Matroid Connectivity

    Highly connected matroids are consistently useful in the analysis of matroid structure. Round matroids, in particular, were instrumental in the proof of Rota's conjecture. Chapter 2 concerns a class of matroids with similar properties to those of round matroids. We provide many useful …

    lsu-thes Repository record for On Properties of Matroid Connectivity (opens in a new tab)

  16. Beta invariant and variations of chain theorems for matroids

    … find the lower bound of the beta invariant of 3-connected matroids with rank r and the matroids which attain the lower bound. Second we characterize the matroids with beta invariant 5 and 6. For binary matroids we characterize matroids with beta invariant 7. These results extend earlier work of …

    mississippi Repository record for Beta invariant and variations of chain theorems for matroids (opens in a new tab)

  17. NON-SEPARATING PATHS IN GRAPHS

    When developing a theory for 3-connected graphs, Tutte showed that for any 3-connected graph G and any three vertices a, b, c of G, G-c has an a-b path P such that G-P is connected. We call paths non-separating if their removal results in a graph satisfying a certain connectivity constraint. There …

    gatech Repository record for NON-SEPARATING PATHS IN GRAPHS (opens in a new tab)

  18. Bounds on Maximum Matchings in 1-Planar Graphs

    … in the class of maximal 1-plane graphs, and 3-connected maximal 1-plane graphs. We find that 3-connected, maximal 1-plane graphs have a maximum matching of size at least (n+4)/3, and that maximal 1-plane graphs have a maximum matching 3 of size at least (n+6)/4. Again, we present examples of …

    waterloo Repository record for Bounds on Maximum Matchings in 1-Planar Graphs (opens in a new tab)

  19. 2-crossing critical graphs with a V8 minor

    … 2-crossing critical graphs are those that are 3-connected with a V8 minor but no V10 minor. This paper seeks to fill some of this gap by defining and completely describing a class of graphs called fully covered. In addition, we examine other ways in which graphs may be 2-crossing critical. This …

    waterloo Repository record for 2-crossing critical graphs with a V8 minor (opens in a new tab)

  20. The Characterization Of Graphs With Small Bicycle Spectrum

    … the same size, called a dual matroid design. The connected bicircular dual matroid designs have been characterized previously. In addition, these results have been extended to connected bicircular matroids with circuits of two sizes in the case that the associated graph is a subdivision of a …

    mississippi Repository record for The Characterization Of Graphs With Small Bicycle Spectrum (opens in a new tab)

Page 1 of 4