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 19 of 19 for “"Disjoint cycles"”.

  1. Extremal problems in disjoint cycles and graph saturation

    … for the existence of a given number of disjoint cycles in a graph. Further, our refined theorem leads to an answer for a question posed by G. Dirac in 1963 regarding the existence of disjoint cycles in graphs with a certain connectivity. This answer comprises Chapter 3. In Chapter 4 we …

    uiuc Repository record for Extremal problems in disjoint cycles and graph saturation (opens in a new tab)

  2. Sufficient degree conditions for graph embeddings

    … 3, we discuss the problem of finding k vertex-disjoint cycles in a multigraph. This problem originated from a conjecture of Erdos and has led to many different results. Corradi and Hajnal looked at a minimum degree condition. Enomoto and Wang independently looked at a minimum degree-sum …

    uiuc Repository record for Sufficient degree conditions for graph embeddings (opens in a new tab)

  3. The Element Spectrum Of A Graph

    … of graphs and matroids that have cycles or circuits of specified cardinality have been given by authors including Edmonds, Junior, Lemos, Murty, Reid, Young, and Wu. In particular, a matroid with circuits of a single cardinality is called a Matroid Design. We consider a …

    mississippi Repository record for The Element Spectrum Of A Graph (opens in a new tab)

  4. Restricted 2-factors in bipartite graphs

    … of finding a spanning subgraph consisting of disjoint cycles with no cycle of length less than or equal to k. It is a generalization of the well known Hamilton cycle problem and is equivalent to this problem when n2≤k≤n-1 . This paper considers necessary and sufficient conditions, …

    rice Repository record for Restricted 2-factors in bipartite graphs (opens in a new tab)

  5. Sufficient conditions for the existence of specified subgraphs in graphs

    … 1963 that considers when a graph contains many disjoint cycles. Generalizing the seminal result of Corrádi and Hajnal, they prove that if a graph G contains many more vertices of degree at least 2k than vertices of degree at most 2k-2, then G contains k vertex-disjoint cycles. We strengthen …

    uiuc Repository record for Sufficient conditions for the existence of specified subgraphs in graphs (opens in a new tab)

  6. On 2-crossing-critical graphs with a V8-minor

    … at least 2 if and only if for each pair of disjoint edges there are two disjoint cycles containing them. Using a generalization of this result we found limitations for the 2-crossing-critical graphs remaining to classify. We showed that peripherally 4-connected 2-crossing-critical graphs …

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

  7. On two models of random graphs /

    … classes in the case when the excluded minors are disjoint. The class of graphs without k+1 (vertex-)disjoint cycles and more general classes of graphs without k+1 disjoint excluded minors (satisfying a condition related to fans) are considered. Typical graphs in such classes are shown to have a …

    vilnius Repository record for On two models of random graphs / (opens in a new tab)

  8. Probabilistic analysis of euclidean multi depot vehicle routing and related problems

    … A multi depot vehicle routing tour is a set of disjoint cycles such that all customers are covered and each cycle contains exactly one depot. The goal is to find a tour of minimum length. $L(D,P)$ denotes the length of an optimal MDVRP tour for depot set $D$ and customer set $P$. It is evident …

    cau-kiel Repository record for Probabilistic analysis of euclidean multi depot vehicle routing and related problems (opens in a new tab)

  9. Discrepancy Inequalities in Graphs and Their Applications

    … of similar questions about the number of vertex-disjoint subgraphs of a certain class that a graph with some degree condition must contain. While this problem is well-studied for dense graphs, many results give significantly worse bounds for less dense graphs. Using spectral graph theory, we show …

    denver Repository record for Discrepancy Inequalities in Graphs and Their Applications (opens in a new tab)

  10. Síntese de circuitos para computação reversível usando Portas Toffoli Generalizadas

    … of the representation of permutations in disjoint cycles, we apply generalized Toffoli gates with controls on all lines except for the target line. Therefore, new in the method is the fact that the obtained circuits use first low cost gates and consider increasing costs towards the end of …

    brazil-uerj Repository record for Síntese de circuitos para computação reversível usando Portas Toffoli Generalizadas (opens in a new tab)

  11. Pseudometrics, The Complex of Ultrametrics, and Iterated Cycle Structures

    … on a set X can be written as a product of disjoint cycles that cover X. In this way, a permutation generalizes a partition. An iterated cycle structure (ICS) will then be the associated generalization of a partition chain. Analogously, we will compute the “Euler-characteristic” of the set …

    unh-thes Repository record for Pseudometrics, The Complex of Ultrametrics, and Iterated Cycle Structures (opens in a new tab)

  12. Study on Two Optimization Problems: Line Cover and Maximum Genus Embedding

    … and its cycle space consisting of fundamental cycles only. We revisit a known incorrect approach of finding a maximum genus embedding via computing a maximum pairing of intersected fundamental cycles with respect to an arbitrary spanning tree. We investigate the reason it failed and conclude it …

    tamu Repository record for Study on Two Optimization Problems: Line Cover and Maximum Genus Embedding (opens in a new tab)

  13. Optimization Models for Kidney Paired Donation

    … of finding a matching, i.e., a set of vertex-disjoint cycles and chains. Despite the broad attention that kidney paired donation has received, some questions at algorithmic, operational and managerial levels remain open. This dissertation addresses the design and analysis of more realistic …

    toronto-retro Repository record for Optimization Models for Kidney Paired Donation (opens in a new tab)

  14. Colouring, covering, reconstruction, and 3-to-1 maps of graphs.

    … must contain cycles. A natural question is this: what is the chromatic index of G if {dollar}G\\Delta{dollar} is a union of vertex disjoint cycles? Further information about this question is given in this Chapter. Also we survey several important known results …

    wvu Repository record for Colouring, covering, reconstruction, and 3-to-1 maps of graphs. (opens in a new tab)

  15. Matrices which, under row permutations, give specified values of certain matrix functions

    … transpositions in Sn; let C denote the set of 3-cycles {(r, r+1, t) ; r = 1, …, n-2; t = r+2, …, n} and let I denote the identity matrix in Sn. We shall denote the n-lst elementary symmetric function of the eigenvalues of A by [formula omitted]. In this thesis, we pose the following problems: 1. …

    ubc Repository record for Matrices which, under row permutations, give specified values of certain matrix functions (opens in a new tab) Download PDF for Matrices which, under row permutations, give specified values of certain matrix functions (opens in a new tab)

  16. Foreshadowing the Grid Theorem for Induced Subgraphs

    … (1) Graphs which are the union of three cycles, all sharing a vertex and otherwise pairwise vertex-disjoint. (2) Graphs which are the union of two vertex-disjoint cycles. (3) Graphs consisting of two non-adjacent vertices with three pairwise internally disjoint paths between them, known …

    waterloo Repository record for Foreshadowing the Grid Theorem for Induced Subgraphs (opens in a new tab)

  17. INFERENCE AND CONTROL IN NETWORKS FAR FROM EQUILIBRIUM.

    … to design a likelihood function through the disjoint cycles of the permutation group. The geometric intuition is provided using dihedral group of the same order. We state and prove that our likelihood function is minimally sufficient and present an optimization algorithm with computational …

    maryland Repository record for INFERENCE AND CONTROL IN NETWORKS FAR FROM EQUILIBRIUM. (opens in a new tab)