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"”.
-
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 …
-
A Combinatorial Interpretation of Minimal Transitive Factorizations into Transpositions for Permutations with two Disjoint Cycles
… of the permutations that are the product of two disjoint cycles.
-
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 …
-
Routing and broadcasting in two-dimensional linear congruential graphs of degree four
… a Hamiltonian cycle, and f2 generates a few disjoint cycles."
-
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 …
-
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, …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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. …
-
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 …
-
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 …