View All Items
(1 - 8 of 8)
- Title
- ALMOST REGULAR GRAPHS AND EDGE FACE COLORINGS OF PLANE GRAPHS.
- Creator
-
Macon, Lisa, Zhao, Yue, University of Central Florida
- Abstract / Description
-
Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost...
Show moreRegular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A linear-time algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A well-known result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.
Show less - Date Issued
- 2009
- Identifier
- CFE0002507, ucf:47684
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0002507
- 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 real-world 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 real-world situations, additional considerations are important. In particular, since each vertex in a defensive alliance represents some real-world 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
- SELF-ASSEMBLED LIPID TUBULES: STRUCTURES, MECHANICAL PROPERTIES, AND APPLICATIONS.
- Creator
-
Zhao, Yue, Fang, Jiyu, University of Central Florida
- Abstract / Description
-
Self-assembled lipid tubules are particularly attractive for inorganic synthesis and drug delivery because they have hollow cylindrical shapes and relatively rigid mechanical properties. In this thesis work, we have synthesized lipid tubules of 1,2-bis(tricosa-10,12-dinoyl)-sn-glycero-3-phosphocholine (DC8,9PC) by self-assembly and polymerization in solutions. We demonstrate for the first time that both uniform and modulated molecular tilt orderings exist in the tubule walls, which have been...
Show moreSelf-assembled lipid tubules are particularly attractive for inorganic synthesis and drug delivery because they have hollow cylindrical shapes and relatively rigid mechanical properties. In this thesis work, we have synthesized lipid tubules of 1,2-bis(tricosa-10,12-dinoyl)-sn-glycero-3-phosphocholine (DC8,9PC) by self-assembly and polymerization in solutions. We demonstrate for the first time that both uniform and modulated molecular tilt orderings exist in the tubule walls, which have been predicted by current theories, and therefore provide valuable supporting evidences for self-assembly mechanisms of chiral molecules. Two novel methods are developed for studying the axial and radial deformations of DC8,9PC lipid tubules. Mechanical properties of DC8,9PC tubules are systematically studied in terms of persistence length, bending rigidity, strain energy, axial and radial elastic moduli, and critical force for collapse. Mechanisms of recovery and surface stiffening are discussed. Due to the high aspect ratio of lipid tubules, the hierarchical assembly of lipid tubules into ordered arrays and desired architectures is critical in developing their applications. Two efficient methods for fabricating ordered arrays of lipid tubules on solid substrates have been developed. Ordered arrays of hybrid silica-lipid tubes are synthesized by tubule array-templated sol-gel reactions. Ordered arrays of optical anisotropic fibers with tunable shapes and refractive indexes are fabricated. This thesis work provides a paradigm for molecularly engineered structures.
Show less - Date Issued
- 2007
- Identifier
- CFE0001918, ucf:47486
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0001918
- Title
- Two Ramsey-related Problems.
- Creator
-
Zhang, Jingmei, Song, Zixia, Zhao, Yue, Martin, Heath, Turgut, Damla, University of Central Florida
- Abstract / Description
-
Extremal combinatorics is one of the central branches of discrete mathematics and has experienced an impressive growth during the last few decades. It deals with the problem of determining or estimating the maximum or minimum possible size of a combinatorial structure which satisfies certain requirements. In this dissertation, we focus on studying the minimum number of edges of certain co-critical graphs. Given an integer r \geq 1 and graphs G, H_1, . . . , H_r, we write G \rightarrow (H_1, ....
Show moreExtremal combinatorics is one of the central branches of discrete mathematics and has experienced an impressive growth during the last few decades. It deals with the problem of determining or estimating the maximum or minimum possible size of a combinatorial structure which satisfies certain requirements. In this dissertation, we focus on studying the minimum number of edges of certain co-critical graphs. Given an integer r \geq 1 and graphs G, H_1, . . . , H_r, we write G \rightarrow (H_1, . . . , H_r) if every r-coloring of the edges of G contains a monochromatic copy of H_i in color i for some i \in {1, . . . , r}. A graph G is (H_1, . . . , H_r)-co-critical if G \nrightarrow (H_1, . . . , H_r), but G+uv \rightarrow (H_1, . . . , H_r) for every pair of non-adjacent vertices u, v in G. Motivated in part by Hanson and Toft's conjecture from 1987, we study the minimum number of edges over all (K_t,\mathcal{T}_k)-co-critical graphs on n vertices, where \mathcal{T}_k denotes the family of all trees on k vertices. We apply graph bootstrap percolation on a not necessarily K_t-saturated graph to prove that for all t \geq 4 and k \geq max{6, t}, there exists a constant c(t,k) such that, for all n \geq (t-1)(k-1)+1, if G is a (K_t,\mathcal{T}_k)-co-critical graph on n vertices, then e(G) \geq ((4t-9)/2+\lceil k/2 \rceil /2)n-c(t,k). We then show that this is asymptotically best possible for all sufficiently large n when t \in {4, 5} and k \geq 6. The method we developed may shed some light on solving Hanson and Toft's conjecture, which is wide open.We also study Ramsey numbers of even cycles and paths under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai k-coloring is a Gallai coloring that uses at most k colors. Given an integer k \geq 1 and graphs H_1, . . . , H_k, the Gallai-Ramsey number GR(H_1, . . . , H_k) is the least integer n such that every Gallai k-coloring of the complete graph K_n contains a monochromatic copy of H_i in color i for some i \in {1, . . . , k}. We completely determine the exact values of GR(H_1, . . . , H_k) for all k \geq 2 when each H_i is a path or an even cycle on at most 13 vertices.
Show less - Date Issued
- 2019
- Identifier
- CFE0007745, ucf:52404
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0007745
- Title
- Hadwiger Numbers and Gallai-Ramsey Numbers of Special Graphs.
- Creator
-
Bosse, Christian, Song, Zixia, Brennan, Joseph, Zhao, Yue, DeMara, Ronald, University of Central Florida
- Abstract / Description
-
This dissertation explores two separate topics on graphs.We first study a far-reaching generalization of the Four Color Theorem. Given a graph G, we use chi(G) to denote the chromatic number; alpha(G) the independence number; and h(G) the Hadwiger number, which is the largest integer t such that the complete graph K_t can be obtained from a subgraph of G by contracting edges. Hadwiger's conjecture from 1943 states that for every graph G, h(G) is greater than or equal to chi(G). This is...
Show moreThis dissertation explores two separate topics on graphs.We first study a far-reaching generalization of the Four Color Theorem. Given a graph G, we use chi(G) to denote the chromatic number; alpha(G) the independence number; and h(G) the Hadwiger number, which is the largest integer t such that the complete graph K_t can be obtained from a subgraph of G by contracting edges. Hadwiger's conjecture from 1943 states that for every graph G, h(G) is greater than or equal to chi(G). This is perhaps the most famous conjecture in Graph Theory and remains open even for graphs G with alpha(G) less than or equal to 2. Let W_5 denote the wheel on six vertices. We establish more evidence for Hadwiger's conjecture by proving that h(G) is greater than or equal to chi(G) for all graphs G such that alpha(G) is less than or equal to 2 and G does not contain W_5 as an induced subgraph.Our second topic is related to Ramsey theory, a field that has intrigued those who study combinatorics for many decades. Computing the classical Ramsey numbers is a notoriously difficult problem, leaving many basic questions unanswered even after more than 80 years. We study Ramsey numbers under Gallai-colorings. A Gallai-coloring of a complete graph is an edge-coloring such that no triangle is colored with three distinct colors. Given a graph H and an integer k at least 1, the Gallai-Ramsey number, denoted GR_k(H), is the least positive integer n such that every Gallai-coloring of K_n with at most k colors contains a monochromatic copy of H. It turns out that GR_k(H) is more well-behaved than the classical Ramsey number R_k(H), though finding exact values of GR_k(H) is far from trivial. We show that for all k at least 3, GR_k(C_{2n+1}) = n2^k+1 where n is 4, 5, 6 or 7, and GR_k(C_{2n+1}) is at most (n ln n)2^k-(k+1)n+1 for all n at least 8, where C_{2n+1} denotes a cycle on 2n+1 vertices.
Show less - Date Issued
- 2019
- Identifier
- CFE0007603, ucf:52532
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0007603
- Title
- Algorithms for Community Identification in Complex Networks.
- Creator
-
Vasudevan, Mahadevan, Deo, Narsingh, Hughes, Charles, Guha, Ratan, Chatterjee, Mainak, Zhao, Yue, University of Central Florida
- Abstract / Description
-
Complex networks such as the Internet, the World Wide Web (WWW), and various social and biological networks, are viewed as large, dynamic, random graphs, with properties significantly different from those of the Erd(&)#246;s-R(&)#233;nyi random graphs. In particular, properties such as degree distribution, network distance, transitivity and clustering coefficient of these networks have been empirically shown to diverge from classical random networks. Existence of communities is one such...
Show moreComplex networks such as the Internet, the World Wide Web (WWW), and various social and biological networks, are viewed as large, dynamic, random graphs, with properties significantly different from those of the Erd(&)#246;s-R(&)#233;nyi random graphs. In particular, properties such as degree distribution, network distance, transitivity and clustering coefficient of these networks have been empirically shown to diverge from classical random networks. Existence of communities is one such property inherent to these networks. A community may informally be defined as a locally-dense induced subgraph, of significant size, in a large globally-sparse graph. Recent empirical results reveal communities in networks spanning across different disciplines (-) physics, statistics, sociology, biology, and linguistics. At least two different questions may be posed on the community structure in large networks: (i) Given a network, detect or extract all (i.e., sets of nodes that constitute) communities; and (ii) Given a node in the network, identify the best community that the given node belongs to, if there exists one. Several algorithms have been proposed to solve the former problem, known as Community Discovery. The latter problem, known as Community Identification, has also been studied, but to a much smaller extent. Both these problems have been shown to be NP-complete, and a number of approximate algorithms have been proposed in recent years. A comprehensive taxonomy of the existing community detection algorithms is presented in this work. Global exploration of these complex networks to pull out communities (community discovery) is time and memory consuming. A more confined approach to mine communities in a given network is investigated in this research. Identifying communities does not require the knowledge of the entire graph. Community identification algorithms exist in the literature, but to a smaller extent. The dissertation presents a thorough description and analysis of the existing techniques to identify communities in large networks. Also a novel heuristic for identifying the community to which a given seed node belongs using only its neighborhood information is presented. An improved definition of a community based on the average degree of the induced subgraph is discussed thoroughly and it is compared with the various definitions in the literature. Next, a faster and accurate algorithm to identify communities in complex networks based on maximizing the average degree is described. The divisive nature of the algorithm (as against the existing agglomerative methods) efficiently identifies communities in large complex networks. The performance of the algorithm on several synthetic and real-world complex networks has also been thoroughly investigated.
Show less - Date Issued
- 2012
- Identifier
- CFE0004294, ucf:49463
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0004294
- Title
- Coloring graphs with forbidden minors.
- Creator
-
Rolek, Martin, Song, Zixia, Brennan, Joseph, Reid, Michael, Zhao, Yue, DeMara, Ronald, University of Central Florida
- Abstract / Description
-
A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. My research is motivated by the famous Hadwiger's Conjecture from 1943 which states that every graph with no Kt-minor is (t - 1)-colorable. This conjecture has been proved true for t ? 6, but remains open for all t ? 7. For t = 7, it is not even yet known if a graph with no K7-minor is 7-colorable. We begin by showing that every graph with no K_t-minor is (2t - 6)-colorable for t = 7, 8, 9, in...
Show moreA graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. My research is motivated by the famous Hadwiger's Conjecture from 1943 which states that every graph with no Kt-minor is (t - 1)-colorable. This conjecture has been proved true for t ? 6, but remains open for all t ? 7. For t = 7, it is not even yet known if a graph with no K7-minor is 7-colorable. We begin by showing that every graph with no K_t-minor is (2t - 6)-colorable for t = 7, 8, 9, in the process giving a shorter and computer-free proof of the known results for t = 7, 8. We also show that this result extends to larger values of t if Mader's bound for the extremal function for Kt-minors is true. Additionally, we show that any graph with no K8?-minor is 9-colorable, and any graph with no K8?-minor is 8-colorable. The Kempe-chain method developed for our proofs of the above results may be of independent interest. We also use Mader's H-Wege theorem to establish some sufficient conditions for a graph to contain a K8-minor.Another motivation for my research is a well-known conjecture of Erd?s and Lov(&)#225;sz from 1968, the Double-Critical Graph Conjecture. A connected graph G is double-critical if for all edges xy ? E(G), ?(G - x - y) = ?(G) - 2. Erd?s and Lov(&)#225;sz conjectured that the only double-critical t-chromatic graph is the complete graph Kt. This conjecture has been show to be true for t ? 5 and remains open for t ? 6. It has further been shown that any non-complete, double-critical, t-chromatic graph contains Kt as a minor for t ? 8. We give a shorter proof of this result for t = 7, a computer-free proof for t = 8, and extend the result to show that G contains a K9-minor for all t ? 9. Finally, we show that the Double-Critical Graph Conjecture is true for double-critical graphs with chromatic number t ? 8 if such graphs are claw-free.
Show less - Date Issued
- 2017
- Identifier
- CFE0006649, ucf:51227
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0006649
- Title
- Routing, Localization and Positioning Protocols for Wireless Sensor and Actor Networks.
- Creator
-
Akbas, Mustafa, Turgut, Damla, Boloni, Ladislau, Georgiopoulos, Michael, Brust, Matthias, Bassiouni, Mostafa, Zhao, Yue, University of Central Florida
- Abstract / Description
-
Wireless sensor and actor networks (WSANs) are distributed systems of sensor nodes and actors that are interconnected over the wireless medium. Sensor nodes collect information about the physical world and transmit the data to actors by using one-hop or multi-hop communications. Actors collect information from the sensor nodes, process the information, take decisions and react to the events.This dissertation presents contributions to the methods of routing, localization and positioning in...
Show moreWireless sensor and actor networks (WSANs) are distributed systems of sensor nodes and actors that are interconnected over the wireless medium. Sensor nodes collect information about the physical world and transmit the data to actors by using one-hop or multi-hop communications. Actors collect information from the sensor nodes, process the information, take decisions and react to the events.This dissertation presents contributions to the methods of routing, localization and positioning in WSANs for practical applications. We first propose a routing protocol with service differentiation for WSANs with stationary nodes. In this setting, we also adapt a sports ranking algorithm to dynamically prioritize the events in the environment depending on the collected data. We extend this routing protocol for an application, in which sensor nodes float in a river to gather observations and actors are deployed at accessible points on the coastline. We develop a method with locally acting adaptive overlay network formation to organize the network with actor areas and to collect data by using locality-preserving communication.We also present a multi-hop localization approach for enriching the information collected from the river with the estimated locations of mobile sensor nodes without using positioning adapters. As an extension to this application, we model the movements of sensor nodes by a subsurface meandering current mobility model with random surface motion. Then we adapt the introduced routing and network organization methods to model a complete primate monitoring system. A novel spatial cut-off preferential attachment model and center of mass concept are developed according to the characteristics of the primate groups. We also present a role determination algorithm for primates, which uses the collection of spatial-temporal relationships. We apply a similar approach to human social networks to tackle the problem of automatic generation and organization of social networks by analyzing and assessing interaction data. The introduced routing and localization protocols in this dissertation are also extended with a novel three dimensional actor positioning strategy inspired by the molecular geometry. Extensive simulations are conducted in OPNET simulation tool for the performance evaluation of the proposed protocols.
Show less - Date Issued
- 2013
- Identifier
- CFE0005292, ucf:50564
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0005292
