Current Search: graph theory (x)
View All Items
 Title
 GALLAIRAMSEY NUMBERS FOR C7 WITH MULTIPLE COLORS.
 Creator

Bruce, Dylan, Song, ZiXia, University of Central Florida
 Abstract / Description

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edgecolorings of complete graphs. For any graphs G, H1, ..., Hk, we write G ? (H1, ..., Hk), or G ? (H)k when H1 = ��� = Hk = H, if every kedgecoloring of G contains a monochromatic Hi in color i for some i ? {1,...,k}. The Ramsey number rk(H1, ..., Hk) is the...
Show moreThe core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edgecolorings of complete graphs. For any graphs G, H1, ..., Hk, we write G ? (H1, ..., Hk), or G ? (H)k when H1 = ��� = Hk = H, if every kedgecoloring of G contains a monochromatic Hi in color i for some i ? {1,...,k}. The Ramsey number rk(H1, ..., Hk) is the minimum integer n such that Kn ? (H1, ..., Hk), where Kn is the complete graph on n vertices. Computing rk(H1, ..., Hk) is a notoriously difficult problem in combinatorics. A weakening of this problem is to restrict ourselves to Gallai colorings, that is, edgecolorings with no rainbow triangles. From this we define the GallaiRamsey number grk(K3,G) as the minimum integer n such that either Kn contains a rainbow triangle, or Kn ? (G)k . In this thesis, we determine the GallaiRamsey numbers for C7 with multiple colors. We believe the method we developed can be applied to find grk(K3, C2n+1) for any integer n ? 2, where C2n+1 denotes a cycle on 2n + 1 vertices.
Show less  Date Issued
 2017
 Identifier
 CFH2000264, ucf:46025
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFH2000264
 Title
 ALLIANCES IN GRAPHS: PARAMETERIZED ALGORITHMS ANDON PARTITIONING SERIESPARALLEL GRAPHS.
 Creator

Enciso, Rosa, Dutton, Ronald, University of Central Florida
 Abstract / Description

Alliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G=(V,E) is a non empty set S⊆V S where, for all x ∈S, N∩S≥NS. Consequently, every vertex that is a member of a defensive alliance has at least as...
Show moreAlliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G=(V,E) is a non empty set S⊆V S where, for all x ∈S, N∩S≥NS. Consequently, every vertex that is a member of a defensive alliance has at least as many vertices defending it as there are vertices attacking it. Alliances can be used to model a variety of applications such as classification problems, communities in the web distributed protocols, etc . In , Gerber and Kobler introduced the problem of partitioning a graph into strong defensive alliances for the first time as the "Satisfactory Graph Partitioning (SGP)" problem. In his dissertation , Shafique used the problem of partitioning a graph into alliances to model problems in data clustering. Decision problems for several types of alliances and alliance partitions have been shown to be NPcomplete. However, because of their applicability, it is of interest to study methods to overcome the complexity of these problems. In this thesis, we will present a variety of algorithms for finding alliances in different families of graphs with a running time that is polynomial in terms of the size of the input, and allowing exponential running time as a function of a chosen parameter. This study is guided by the theory of parameterized complexity introduced by Rod Downey and Michael Fellows in . In addition to parameterized algorithms for alliance related problems, we study the partition of seriesparallel graphs into alliances. The class of seriesparallel graphs is a special class in graph theory since many problems known to be NPcomplete on general graphs have been shown to have polynomial time algorithms on seriesparallel graphs. For example, the problem of finding a minimum defensive alliance has been shown to have a linear time algorithm when restricted to seriesparallel graphs . Seriesparallel graphs have also been to focus of study in a wide range of applications including CMOS layout and scheduling problems [ML86, Oud97]. Our motivation is driven by clustering properties that can be modeled with alliances. We observe that partitioning seriesparallel graphs into alliances of roughly the same size can be used to partition task graphs to minimize the communication between processors and balance the workload of each processor. We present a characterization of seriesparallel graphs that allow a partition into defensive alliances and a subclass of seriesparallel graphs with a satisfactory partitions.
Show less  Date Issued
 2009
 Identifier
 CFE0002956, ucf:47945
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0002956
 Title
 Interval EdgeColorings of Graphs.
 Creator

Foster, Austin, Song, Zixia, Reid, Michael, Brennan, Joseph, University of Central Florida
 Abstract / Description

A proper edgecoloring of a graph G by positive integers is called an interval edgecoloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edgecolorings was first introduced by Asratian and Kamalian in 1987, motivated by the problem of finding compact school timetables. In 1992, Hansen described another scenario using interval edgecolorings to schedule parentteacher conferences so...
Show moreA proper edgecoloring of a graph G by positive integers is called an interval edgecoloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edgecolorings was first introduced by Asratian and Kamalian in 1987, motivated by the problem of finding compact school timetables. In 1992, Hansen described another scenario using interval edgecolorings to schedule parentteacher conferences so that every person's conferences occur in consecutive slots. A solution exists if and only if the bipartite graph with vertices for parents and teachers, and edges for the required meetings, has an interval edgecoloring.A wellknown result of Vizing states that for any simple graph $G$, $\chi'(G) \leq \Delta(G) + 1$, where $\chi'(G)$ and $\Delta(G)$ denote the edgechromatic number and maximum degree of $G$, respectively. A graph $G$ is called class 1 if $\chi'(G) = \Delta(G)$, and class 2 if $\chi'(G) = \Delta(G) + 1$. One can see that any graph admitting an interval edgecoloring must be of class 1, and thus every graph of class 2 does not have such a coloring.Finding an interval edgecoloring of a given graph is hard. In fact, it has been shown that determining whether a bipartite graph has an interval edgecoloring is NPcomplete. In this thesis, we survey known results on interval edgecolorings of graphs, with a focus on the progress of $(a, b)$biregular bipartite graphs. Discussion of related topics and future work is included at the end. We also give a new proof of Theorem 3.15 on the existence of proper path factors of $(3, 4)$biregular graphs. Finally, we obtain a new result, Theorem 3.18, which states that if a proper path factor of any $(3, 4)$biregular graph has no path of length 8, then it contains paths of length 6 only. The new result we obtained and the method we developed in the proof of Theorem 3.15 might be helpful in attacking the open problems mentioned in the Future Work section of Chapter 5.
Show less  Date Issued
 2016
 Identifier
 CFE0006301, ucf:51609
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006301
 Title
 Computing a diameterconstrained minimum spanning tree.
 Creator

Abdalla, Ayman Mahmoud, Deo, Narsingh, Engineering and Computer Science
 Abstract / Description

University of Central Florida College of Engineering Thesis; In numerous practical applications, it is necessary to find the smallest possible tree with a bounded diameter. A diameterconstrained minimum spanning tree (DCMST) of a given undirected, edgeweighted graph, G, is the smallestweight spanning tree of all spanning trees of G which contain no path with more than k edges, where k is a given positive integer. The problem of finding a DCMST is NPcomplete for all values of k; 4
Show moreUniversity of Central Florida College of Engineering Thesis; In numerous practical applications, it is necessary to find the smallest possible tree with a bounded diameter. A diameterconstrained minimum spanning tree (DCMST) of a given undirected, edgeweighted graph, G, is the smallestweight spanning tree of all spanning trees of G which contain no path with more than k edges, where k is a given positive integer. The problem of finding a DCMST is NPcomplete for all values of k; 4 <= k <= (n  2), except when all edgeweights are identical. A DCMST is essential for the efficiency of various distributed mutual exclusion algorithms, where it can minimize the number of messages communicated among processors per critical section. It is also useful in linear lightwave networks, where it can minimize interference in the network by limiting the traffic in the network lines. Another practical application requiring a DCMST arises in data compression, where some algorithms compress a file utilizing a datastructure, and decompress a path in the tree to access a record A DCMST helps such algorithm to be fast without sacrificing a lot of storage storage space.
Show less  Date Issued
 2001
 Identifier
 CFR0002215, ucf:52914
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFR0002215
 Title
 ON SATURATION NUMBERS OF RAMSEYMINIMAL GRAPHS.
 Creator

Davenport, Hunter M, Song, ZiXia, University of Central Florida
 Abstract / Description

Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edgecolorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every kedgecoloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)edgecoloring of G, we say c is a bad coloring if G contains...
Show moreDating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edgecolorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every kedgecoloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)edgecoloring of G, we say c is a bad coloring if G contains no red K3or blue K1,t under c. A graph G is (H1,...,Hk)Ramseyminimal if G arrows (H1,...,Hk) but no proper subgraph of G has this property. Given a family F of graphs, we say that a graph G is Fsaturated if no member of F is a subgraph of G, but for any edge xy not in E(G), G + xy contains a member of F as a subgraph. Letting Rmin(K3, K1,t) be the family of (K3,K1,t)Ramsey minimal graphs, we study the saturation number, denoted sat(n,Rmin(K3,K1,t)), which is the minimum number of edges among all Rmin(K3,K1,t)saturated graphs on n vertices. We believe the methods and constructions developed in this thesis will be useful in studying the saturation numbers of (K4,K1,t)saturated graphs.
Show less  Date Issued
 2018
 Identifier
 CFH2000291, ucf:45881
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFH2000291
 Title
 FINDING DUD VERTICES IN DEFENSIVE ALLIANCES AND SECURE SETS USING COMPUTATIONAL TOOLS.
 Creator

Worley, George, Zhao, Yue, University of Central Florida
 Abstract / Description

Defensive alliances are a way of using graphs to model the defense of resources (people, buildings, countries, etc.) against attacks where the number of potential attackers against each resource is known. The initial study of defensive alliances focused on questions of minimal defensive alliances in a graph and the minimum possible size of a defensive alliance in a graph, but in order to apply defensive alliances in modeling realworld situations, additional considerations are important. In...
Show moreDefensive alliances are a way of using graphs to model the defense of resources (people, buildings, countries, etc.) against attacks where the number of potential attackers against each resource is known. The initial study of defensive alliances focused on questions of minimal defensive alliances in a graph and the minimum possible size of a defensive alliance in a graph, but in order to apply defensive alliances in modeling realworld situations, additional considerations are important. In particular, since each vertex in a defensive alliance represents some realworld object that has a cost associated with remaining in the defensive alliance, it is important to consider the value each vertex adds to the defensive alliance. In this thesis we consider a method of assessing the efficiency of a defensive alliance, including the special case of secure sets.
Show less  Date Issued
 2011
 Identifier
 CFE0004010, ucf:49166
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0004010
 Title
 Sampling and Reconstruction of Spatial Signals.
 Creator

Cheng, Cheng, Li, Xin, Sun, Qiyu, Yong, Jiongmin, Liu, Zhe, Xu, Mengyu, University of Central Florida
 Abstract / Description

Digital processing of signals f may start from sampling on a discrete set ?, f ?? f(?_n), ?_n ??.The sampling theory is one of the most basic and fascinating topics in applied mathematics and in engineering sciences. The most well known form is the uniform sampling theorem for bandlimited/wavelet signals, that gives a framework for converting analog signals into sequences of numbers. Over the past decade, the sampling theory has undergone a strong revival and the standard sampling paradigm...
Show moreDigital processing of signals f may start from sampling on a discrete set ?, f ?? f(?_n), ?_n ??.The sampling theory is one of the most basic and fascinating topics in applied mathematics and in engineering sciences. The most well known form is the uniform sampling theorem for bandlimited/wavelet signals, that gives a framework for converting analog signals into sequences of numbers. Over the past decade, the sampling theory has undergone a strong revival and the standard sampling paradigm is extended to nonbandlimited signals including signals in reproducing kernel spaces (RKSs), signals with finite rate of innovation (FRI) and sparse signals, and to nontraditional sampling methods, such as phaseless sampling.In this dissertation, we first consider the sampling and Galerkin reconstruction in a reproducing kernel space. The fidelity measure of perceptual signals, such as acoustic and visual signals, might not be well measured by least squares. In the first part of this dissertation, we introduce a fidelity measure depending on a given sampling scheme and propose a Galerkin method in Banach space setting for signal reconstruction. We show that the proposed Galerkin method provides a quasioptimal approximation, and the corresponding Galerkin equations could be solved by an iterative approximationprojection algorithm in a reproducing kernel subspace of Lp.A spatially distributed network contains a large amount of agents with limited sensing, data processing, and communication capabilities. Recent technological advances have opened up possibilities to deploy spatially distributed networks for signal sampling and reconstruction. We introduce a graph structure for a distributed sampling and reconstruction system by coupling agents in a spatially distributed network with innovative positions of signals. We split a distributed sampling and reconstruction system into a family of overlapping smaller subsystems, and we show that the stability of the sensing matrix holds if and only if its quasirestrictions to those subsystems have l_2 uniform stability. This new stability criterion could be pivotal for the design of a robust distributed sampling and reconstruction system against supplement, replacement and impairment of agents, as we only need to check the uniform stability of affected subsystems. We also propose an exponentially convergent distributed algorithm for signal reconstruction, that provides a suboptimal approximation to the original signal in the presence of bounded sampling noises.Phase retrieval (Phaseless Sampling and Reconstruction) arises in various fields of science and engineering. It consists of reconstructing a signal of interest from its magnitude measurements. Sampling in shiftinvariant spaces is a realistic model for signals with smooth spectrum. We consider phaseless sampling and reconstruction of realvalued signals in a shiftinvariant space from their magnitude measurements on the whole Euclidean space and from their phaseless samples taken on a discrete set with finite sampling density. We find an equivalence between nonseparability of signals in a shiftinvariant space and their phase retrievability with phaseless samples taken on the whole Euclidean space. We also introduce an undirected graph to a signal and use connectivity of the graph to characterize the nonseparability of highdimensional signals. Under the local complement property assumption on a shiftinvariant space, we find a discrete set with finite sampling density such that signals in shiftinvariant spaces, that are determined by their magnitude measurements on the whole Euclidean space, can be reconstructed in a stable way from their phaseless samples taken on that discrete set. We also propose a reconstruction algorithm which provides a suboptimal approximation to the original signal when its noisy phaseless samples are available only.
Show less  Date Issued
 2017
 Identifier
 CFE0006726, ucf:51889
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006726