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 90 for “"Perfect matching"”.

  1. Perfect Matching and Circuit Cover of Graphs

    … graphs, which has an edge contained by a unique perfect matching. In chapter three, we prove that if a cubic graph G containing a subdivision of a special class of edge-3-colorable cubic graphs, semi-Kotzig graphs, then G has a circuit double cover.;Circuit extension is an approach posted by …

    wvu Repository record for Perfect Matching and Circuit Cover of Graphs (opens in a new tab)

  2. Quantum Algorithms for Memoryless Search and Perfect Matching

    … algorithm decides whether a graph contains a perfect matching. This is the first quantum algorithm based on the algebraic characterization by Tutte, which reduces the problem of detecting perfect matchings to deciding whether a matrix has nonzero determinant. The key part of our algorithm is a …

    calgary Repository record for Quantum Algorithms for Memoryless Search and Perfect Matching (opens in a new tab)

  3. Excluding Two Minors of the Petersen Graph

    … graph created by contracting three edges of a perfect matching of the Petersen Graph. In Chapter 3, we determine the structure of any large internally 4-connected graph which has no P_2 minor, where P_2 is a graph on 8 vertices, 13 edges, and is isomorphic to the graph created by contracting …

    lsu-thes Repository record for Excluding Two Minors of the Petersen Graph (opens in a new tab)

  4. Perfect matchings after vertex deletions in n-dimensional lattice graphs

    … graphs which are readily seen to have many perfect matchings and considers whether if we delete vertices the resulting graphs continue to have perfect matchings. It is clear that one can destroy the property of having a perfect matching by deleting an odd number of vertices, by deleting all …

    ubc Repository record for Perfect matchings after vertex deletions in n-dimensional lattice graphs (opens in a new tab) Download PDF for Perfect matchings after vertex deletions in n-dimensional lattice graphs (opens in a new tab)

  5. Minimum Crossing Problems on Graphs

    … of subsets of vertices S, the minimum crossing perfect matching is a perfect matching where the maximum number of edges crossing any set in S is minimized. A proof will be presented showing that finding a minimum crossing perfect matching is NP-hard, even when the graph is bipartite and the sets …

    waterloo Repository record for Minimum Crossing Problems on Graphs (opens in a new tab)

  6. Unambiguous logarithmic space bounded computations

    … - space complexity of deciding if a graph has a perfect matching. We prove that perfect matching in bipartite bounded genus graphs is in SPL (a class which is a generalization of UL and not known to be comparable with NL). We also show that over bipartite planar graphs, the perfect matching …

    nebraska Repository record for Unambiguous logarithmic space bounded computations (opens in a new tab)

  7. Independent Domination in Complementary Prisms.

    … union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. For example, if G is a 5-cycle, then GG̅ is the Petersen graph. In this paper we investigate independent domination in complementary prisms.

    etsu Repository record for Independent Domination in Complementary Prisms. (opens in a new tab) Download PDF for Independent Domination in Complementary Prisms. (opens in a new tab)

  8. Matchings and Representation Theory

    … we investigate the algebraic properties of matchings via representation theory. We identify three scenarios in different areas of combinatorial mathematics where the algebraic structure of matchings gives keen insight into the combinatorial problem at hand. In particular, we prove tight …

    waterloo Repository record for Matchings and Representation Theory (opens in a new tab)

  9. Matching structure and Pfaffian orientations of graphs

    … it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of a decomposition procedure of Kotzig, and Lovasz and Plummer. We prove that every brick except for the Petersen graph can be generated from K_4 or the …

    gatech Repository record for Matching structure and Pfaffian orientations of graphs (opens in a new tab)

  10. The induced path number of complementary prisms

    … G and its complement G by adding the edges of a perfect matching between the corresponding vertices of G and G. The induced path number, denoted ρ(G), of a graph G is defined as the minimum number of subsets that the vertex set of G can be partitioned into such that each subset induces a path. In …

    utc Repository record for The induced path number of complementary prisms (opens in a new tab)

  11. Double Domination of Complementary Prisms.

    … a copy of G and its complement G̅ by adding a perfect matching between the corresponding vertices of G and G̅. For any graph G, a set D ⊆ V (G) is a double dominating set (DDS) if that set dominates every vertex of G twice. The double domination number, denoted γ×2(G), is the cardinality of a …

    etsu Repository record for Double Domination of Complementary Prisms. (opens in a new tab) Download PDF for Double Domination of Complementary Prisms. (opens in a new tab)

  12. Design of Tubular Network Systems Using Circle Packing and Discrete Optimization

    … system. This problem can be reduced to a perfect matching (PM) problem at each end. We apply similar integer programming algorithms to both perfect matching problem and TSP. However, the design of complete tubular network system in a container exhibiting longitudinal symmetry remains an …

    waterloo Repository record for Design of Tubular Network Systems Using Circle Packing and Discrete Optimization (opens in a new tab)

  13. Matching problems in hypergraphs

    … choose 2} - {2n/3 choose 2}, then H contains a perfect matching. We show that for sufficiently large n divisible by 3, if F_1, ..., F_{n/3} are 3-uniform hypergraphs with a common vertex set and the minimum vertex degree in each F_i is greater than {(n-1) choose 2} - {2n/3 choose 2} for i = 1, …

    gatech Repository record for Matching problems in hypergraphs (opens in a new tab)

  14. Εφαρμογές της FDTD μεθόδου στην ανάλυση και σχεδιασμό συζευκτών για οπτικές διασυνδέσεις και οπτικές επικοινωνίες

    … formalism (TF-SF) in conjunction with perfect matching absorbing layers (PML). In the same framework the spatially higher order FDTD (HO-FDTD) is developed and techniques (permittivity smoothing) for improving the accuracy of the FDTD and HO-FDTD are applied. The scattering problem of …

    greece Repository record for Εφαρμογές της FDTD μεθόδου στην ανάλυση και σχεδιασμό συζευκτών για οπτικές διασυνδέσεις και οπτικές επικοινωνίες (opens in a new tab)

  15. Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks

    … algorithm, with modifications that exploit perfect matching to a greater extent. Hamilton cycles are expressed as specially constructed block permutation matrices. The algorithm attempts to decide a graph's non-Hamiltonicity by checking for the non-existence of these permutation matrices …

    guelph Repository record for Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks (opens in a new tab)

  16. Graph-theoretic and chemical properties of anionic fullerenes

    … whose vertices results in a graph that admits a perfect matching. This definition is motivated by the chemical observation that pentagonal rings can accommodate an extra electron, so that the pentagons of a fullerene p-anion compete with the hexagons to host ‘Clar sextets’ of six electrons, and …

    uvic Repository record for Graph-theoretic and chemical properties of anionic fullerenes (opens in a new tab)

Page 1 of 5