Current Search: Zhao, Yue (x)


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 lineartime algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomialtime algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edgeface 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 wellknown 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 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

SELFASSEMBLED LIPID TUBULES: STRUCTURES, MECHANICAL PROPERTIES, AND APPLICATIONS.

Creator

Zhao, Yue, Fang, Jiyu, University of Central Florida

Abstract / Description

Selfassembled 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,2bis(tricosa10,12dinoyl)snglycero3phosphocholine (DC8,9PC) by selfassembly 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 moreSelfassembled 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,2bis(tricosa10,12dinoyl)snglycero3phosphocholine (DC8,9PC) by selfassembly 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 selfassembly 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 silicalipid tubes are synthesized by tubule arraytemplated solgel 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 Ramseyrelated 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 cocritical 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 cocritical graphs. Given an integer r \geq 1 and graphs G, H_1, . . . , H_r, we write G \rightarrow (H_1, . . . , H_r) if every rcoloring 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)cocritical if G \nrightarrow (H_1, . . . , H_r), but G+uv \rightarrow (H_1, . . . , H_r) for every pair of nonadjacent 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)cocritical 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_tsaturated 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 (t1)(k1)+1, if G is a (K_t,\mathcal{T}_k)cocritical graph on n vertices, then e(G) \geq ((4t9)/2+\lceil k/2 \rceil /2)nc(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 kcoloring is a Gallai coloring that uses at most k colors. Given an integer k \geq 1 and graphs H_1, . . . , H_k, the GallaiRamsey number GR(H_1, . . . , H_k) is the least integer n such that every Gallai kcoloring 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 GallaiRamsey 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 farreaching 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 farreaching 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 Gallaicolorings. A Gallaicoloring of a complete graph is an edgecoloring such that no triangle is colored with three distinct colors. Given a graph H and an integer k at least 1, the GallaiRamsey number, denoted GR_k(H), is the least positive integer n such that every Gallaicoloring of K_n with at most k colors contains a monochromatic copy of H. It turns out that GR_k(H) is more wellbehaved 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;sR(&)#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;sR(&)#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 locallydense induced subgraph, of significant size, in a large globallysparse 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 NPcomplete, 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 realworld 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 Ktminor 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 K7minor is 7colorable. We begin by showing that every graph with no K_tminor 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 Ktminor 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 K7minor is 7colorable. We begin by showing that every graph with no K_tminor is (2t  6)colorable for t = 7, 8, 9, in the process giving a shorter and computerfree 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 Ktminors is true. Additionally, we show that any graph with no K8?minor is 9colorable, and any graph with no K8?minor is 8colorable. The Kempechain method developed for our proofs of the above results may be of independent interest. We also use Mader's HWege theorem to establish some sufficient conditions for a graph to contain a K8minor.Another motivation for my research is a wellknown conjecture of Erd?s and Lov(&)#225;sz from 1968, the DoubleCritical Graph Conjecture. A connected graph G is doublecritical if for all edges xy ? E(G), ?(G  x  y) = ?(G)  2. Erd?s and Lov(&)#225;sz conjectured that the only doublecritical tchromatic 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 noncomplete, doublecritical, tchromatic graph contains Kt as a minor for t ? 8. We give a shorter proof of this result for t = 7, a computerfree proof for t = 8, and extend the result to show that G contains a K9minor for all t ? 9. Finally, we show that the DoubleCritical Graph Conjecture is true for doublecritical graphs with chromatic number t ? 8 if such graphs are clawfree.
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 onehop or multihop 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 onehop or multihop 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 localitypreserving communication.We also present a multihop 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 cutoff 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 spatialtemporal 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