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 170 for “"complete graph"”.
-
The Thickness of The Complete Graph
Made available in DSpace on 2014-12-14T13:09:31Z (GMT). No. of bitstreams: 1 7624197.pdf: 1925056 bytes, checksum: 80d412464c0ec3459b5e89340f2fb485 (MD5) Previous issue date: 1976
-
Solving Traveling Salesman Problem With a non-complete Graph
… algorithms, they all assume that a complete graph is given as an input. However, for very large graphs, generating all edges in a complete graph, which corresponds to finding shortest paths for all city pairs, could be time-consuming. This is definitely a major obstacle for some …
-
On 1-factorizations of the complete graph and the relationship to round robin schedules
… new results concerning 1-factorizations of the complete graph are proved: (1) There are exactly 6 equivalence classes of 1-factorizations of the complete graph with 8 vertices. (2). There are exactly 396 equivalence classes of 1-factorizations of the complete graph with 10 vertices. …
-
Cyclic, f-Cyclic, and Bicyclic Decompositions of the Complete Graph into the 4-Cycle with a Pendant Edge.
In this paper, we consider decompositions of the complete graph on v vertices into 4-cycles with a pendant edge. In part, we will consider decompositions which admit automorphisms consisting of:(1) a single cycle of length v,(2) f fixed points and a cycle of length v − f, or(3) two disjoint …
-
Some Results on Crossing Numbers
The drawing of the complete graph in which the vertices are placed on the rims of a cylinder and connected with geodesic edges is conjectured to produce the minimum number of edge crossings for a complete graph, which is its crossing number. This dissertation proves that no edge in this drawing can …
-
On graph decompositions: Exploring the stars and stripes problem with odd n-stars
… the “Stars and Stripes" problem, which is a graph decomposition problem. The Stars and Stripes problem can be described as finding uniformly resolvable decompositions when the blocks are either $n$-stars or edges. In other words, this refers to decomposing a complete graph into spanning …
-
ON THE MOZART CAFE PROBLEM IN RENDEZVOUS SEARCH THEORY
… the best values for rendezvous search on the complete graph developed in 1990 by Anderson and Weber. The markstart formulation was first proposed by Baston and Gal and we have proved their ideas and developed expansions of the problem on the complete graph. Utilizing tokens is only worthwhile …
-
On the Maker-Breaker k-Cycle Game
… the biased Maker-Breaker k-cycle game on the complete graph for a fixed k ∈ N. This is a special case of Maker-Breaker subraph games that are played by two players called Maker and Breaker who alternately claim edges of the complete graph that were previously unclaimed by either player. Maker …
-
Restricted and Unrestricted Coverings of Complete Bipartite Graphs with Hexagons
A minimal covering of a graph G with isomorphic copies of graph H is a set {H1, H2, H3, ... , Hn} where Hi is isomorphic to H, the vertex set of Hi is a subset of G, the edge set of G is a subset of the union of Hi's, and the cardinality of the union of Hi's minus G is minimum. Some studies have …
-
Propriedades estruturais e espectrais de k-árvores
A k-tree is a complete graph with k vertices or a graph that contains a vertex whose neighborhood induces a complete graph of size k and whose removal results in a k-tree. In this text we show properties and results obtained for this family, which generalizes the already widely studied class of …
-
Enumeration of inequivalent cycle decompositions
… of order n is a partition of the edges of the complete graph on n vertices into k-cycles. In this report a backtracking algorithm is developed to count the number of inequivalent k-cycle decompositions of order n.
-
DC-RST: a highly parallel, divide-and-conquer algorithm for creating random spanning trees on a clique
… for generating a random spanning tree of a complete graph on $n$ vertices such that each edge in the graph is chosen with equal probability. DC-RST parallelizes Wilson's sequential random-walk algorithm which has an expected complexity of $\Theta(n)$ on a complete graph. On a system with 48 …
-
Plane Spanners of Degree Eight
… selects a subset of edges from DT(P) to form the graph D8(P). We then prove that D8(P) has a constant spanning ratio of approximately 4.414 with respect to the complete graph, and a maximum degree of 8.
-
On Ramsey and Gallai-Ramsey numbers of some classes of graphs
… in any edge coloring of a sufficiently large complete graph. This result is commonly known as Ramsey's theorem. The role of Ramsey number is to quantify some specific problems related to Ramsey's theorem. Given a graph H, the Ramsey number R_2(H) is the minimum integer p such that every …
-
Two Ramsey-related Problems
… minimum number of edges of certain co-critical graphs. Given an integer r ≥ 1 and graphs G; H1; : : : ;Hr, we write → G (H1; : : : ;Hr) if every r-coloring of the edges of G contains a monochromatic copy of Hi in color i for some i ϵ {1; : : : ; r}. A non-complete graph G is (H1; : : : …
-
Decompositions, Packings, and Coverings of Complete Directed Gaphs with a 3-Circuit and a Pendent Arc.
In the study of Graph theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K3 ∪ {e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for …
-
Decomposition, Packings and Coverings of Complete Digraphs with a Transitive-Triple and a Pendant Arc.
… theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K3∪{e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings …
-
Connected matchings in special families of graphs.
A connected matching in a graph is a set of disjoint edges such that, for any pair of these edges, there is another edge of the graph incident to both of them. This dissertation investigates two problems related to finding large connected matchings in graphs. The first problem is motivated by a …
-
Efficiency of continuous-time quantum walks: from networks with disorder to deterministic fractals
… of walks for the following structures: star graph and complete graph as well as the transition between these two regular structures, two-dimensional structures, and Sierpinski fractals. Finally, I show that quantum walks can be as efficient as their classical counterpart and in some cases - …
-
Computing the Rectilinear Crossing Number of K
Rectilinear crossing number of a graph is the number of crossing edges in a drawing with all straight line edges. The problem of drawing an n-vertex complete graph such that its rectilinear crossing number is minimum is known to be an NP-Hard problem. In this thesis, we present a heuristic that …
Page 1 of 9