Current Search: Graph theory (x)
View All Items
 Title
 WHEN DOES A GRAPH HAVE A UNIQUE DRAWING ON A SPHERE?.
 Creator
 FRIEDLANDER, DAVID PAUL, Florida Atlantic University
 Abstract/Description

This thesis shows that a planar graph is uniquely embeddable in a sphere whenever it is threeconnected and gives related results about planar graphs of lower connectivity and about non planar graphs. A section on the fourteen nonplanar graphs with six vertices is also included.
 Date Issued
 1972
 PURL
 http://purl.flvc.org/fcla/dt/13477
 Subject Headings
 Graph theory
 Format
 Document (PDF)
 Title
 Odd sums of long cycles in 2connected graphs.
 Creator
 Teng, Cong., Florida Atlantic University, Locke, Stephen C.
 Abstract/Description

Let G be a 2connected graph with minimum degree d and with at least d + 2 vertices. Suppose that G is not a cycle. Then there is an odd set of cycles, each with length at least d + 1, such that they sum to zero. If G is also nonhamiltonian or bipartite, cycles of length at least 2d can be used.
 Date Issued
 1999
 PURL
 http://purl.flvc.org/fcla/dt/15666
 Subject Headings
 Paths and cycles (Graph theory), Graph theory
 Format
 Document (PDF)
 Title
 Long paths and cycles in graphs with large minimum degree.
 Creator
 Barovich, Mark V., Florida Atlantic University, Locke, Stephen C.
 Abstract/Description

Determining which graphs are hamiltonian is a central unsolved problem in graph theory. More generally, the study of long cycles in graphs has been extensive, and there are numerous results on the subject in the mathematical literature. In this dissertation, we survey several of these results. The study of long paths is related to the study of long cycles. In a graph in which every pair of vertices is connected by a long path, every edge lies on a long cycle. We prove that any set of four...
Show moreDetermining which graphs are hamiltonian is a central unsolved problem in graph theory. More generally, the study of long cycles in graphs has been extensive, and there are numerous results on the subject in the mathematical literature. In this dissertation, we survey several of these results. The study of long paths is related to the study of long cycles. In a graph in which every pair of vertices is connected by a long path, every edge lies on a long cycle. We prove that any set of four vertices lying on a common path in a 2connected graph lie on a common long path, generalizing a result of Lovasz. We further exploit the relationship between long paths and long cycles to prove that the cycle spaces of a large class of hamiltonian graphs are generated by long cycles, partially proving a conjecture made by Bondy.
Show less  Date Issued
 1998
 PURL
 http://purl.flvc.org/fcla/dt/12572
 Subject Headings
 Hamiltonian graph theory
 Format
 Document (PDF)
 Title
 THE MINIMUM KCENTER PROBLEM FOR GRID GRAPH.
 Creator
 HSUEH, CHIFU, Florida Atlantic University, Hadlock, Frank O., Hoffman, Frederick, Charles E. Schmidt College of Science, Department of Mathematical Sciences
 Abstract/Description

A study was made of the problem of locating M facilities on a connected grid graph, so that M is the minimum and so that every demand node on the graph is within given distance K of one of these M facilities. We call this problem briefly the G(N,K,M) problem, with N denoting the total number of demand nodes. An algorithm for solving this problem by using backtrack technique is presented in this thesis. A heuristic algorithm is also present; although the resulting M is not always minimum, it...
Show moreA study was made of the problem of locating M facilities on a connected grid graph, so that M is the minimum and so that every demand node on the graph is within given distance K of one of these M facilities. We call this problem briefly the G(N,K,M) problem, with N denoting the total number of demand nodes. An algorithm for solving this problem by using backtrack technique is presented in this thesis. A heuristic algorithm is also present; although the resulting M is not always minimum, it tends to be near minimum. The advantage over the backtrack algorithm is that the heuristic algorithm operates very quickly. Algorithms represented in this thesis are programmed in the Pascal language for the Univac 1100 computer at Florida Atlantic University, Boca Raton, Florida.
Show less  Date Issued
 1981
 PURL
 http://purl.flvc.org/fcla/dt/14077
 Subject Headings
 Graph theory, Algorithms
 Format
 Document (PDF)
 Title
 Some graph connectivity conditions and their implications.
 Creator
 Abreu, Marien, Florida Atlantic University, Locke, Stephen C.
 Abstract/Description

This dissertation studies two independent problems, each related to a special connectivity condition in a simple graph. The first is a distancedegree condition called cohesion. Given a tree T with n vertices, we analyze the minimum integer f(T) = k, in terms of n, for which any connected kcohesive graph G contains a copy of T, such that GV(T) is connected. The problem comes from a generalization of an exercise by Lovasz [L7] in which it is shown that f(K2) = 5. Locke, Tracy and Voss [L5]...
Show moreThis dissertation studies two independent problems, each related to a special connectivity condition in a simple graph. The first is a distancedegree condition called cohesion. Given a tree T with n vertices, we analyze the minimum integer f(T) = k, in terms of n, for which any connected kcohesive graph G contains a copy of T, such that GV(T) is connected. The problem comes from a generalization of an exercise by Lovasz [L7] in which it is shown that f(K2) = 5. Locke, Tracy and Voss [L5] have proved that in general f(T) > 2n, and in the case in which T is a path, equality is attained. Also Locke [L5.1] proved that f(T) < 4n. Here we improve the upper bound to 4n6 when T is not a path and to 2n + 2 when T has diameter at most 4. In the particular case of K1,3 we show that f(K1,3) = 2n = 8 is attained. The conjecture that remains open is whether f(T) = 2n for any tree T on n vertices. The second problem studied here is a particular case of the well known relation between the pathconnectivity and a set of long cycles, which generate the cycle space of a simple graph. The main conjecture in this topic is by Bondy [B1], and states that if G is a 3connected graph, with minimum degree at least d and with at least 2d vertices, then every cycle of G can be written as the symmetric difference of an odd number of cycles, each of whose lengths are at least 2d1. Hartman [H2], Locke [L1, L2, L3], Barovich [BL] and Teng [L6] have proved results related to this conjecture. Here we show that 2connected, 6pathconnected graphs with at least 9 vertices and minimum degree at least 3 are 6generated. And more generally, we prove that if a graph G is 2connected, kpathconnected, and contains a long cycle, then G is (k + 1)generated, up to some cases which are characterized. The conjecture [L3] of whether, for some constant m, 1/2 < m < 1, every kpathconnected graph is mkgenerated, remains open.
Show less  Date Issued
 2003
 PURL
 http://purl.flvc.org/fcla/dt/12030
 Subject Headings
 Trees (Graph theory), Paths and cycles (Graph theory)
 Format
 Document (PDF)
 Title
 Cycle and path double covers of graphs.
 Creator
 Wu, Xuegong, Florida Atlantic University, Locke, Stephen C.
 Abstract/Description

A cycle double cover (CDC) of a graph G is a collection C of cycles of G such that each edge of G belongs to exactly two members of C. P. D. Seymour conjectured that every 2edgeconnected graph admits a CDC. In a similar way, a path double cover (PDC) of graph G is a collection P of paths of G such that each edge of G belongs to exactly two paths of P. If each vertex of G is an end of exactly two paths of P, then P is called a perfect path double cover (PPDC). J. A. Bondy asked if every...
Show moreA cycle double cover (CDC) of a graph G is a collection C of cycles of G such that each edge of G belongs to exactly two members of C. P. D. Seymour conjectured that every 2edgeconnected graph admits a CDC. In a similar way, a path double cover (PDC) of graph G is a collection P of paths of G such that each edge of G belongs to exactly two paths of P. If each vertex of G is an end of exactly two paths of P, then P is called a perfect path double cover (PPDC). J. A. Bondy asked if every simple graph admits a PPDC. In the first part of this thesis, we present some techniques that have been applied to the cycle double cover conjecture and give a detailed study of CDC for some particular graphs. It has been found that this conjecture is true of planar graphs, 3edgecolorable cubic graphs, Cayley graphs and graphs which have a Hamiltonian path. In the second part of this thesis, we mainly deal with path double covers and their variants. We will see that every simple graph admits a PPDC and the PPDC problem is in class P. A detailed summary about the main results discussed in this thesis is included.
Show less  Date Issued
 1991
 PURL
 http://purl.flvc.org/fcla/dt/14687
 Subject Headings
 Paths and cycles (Graph theory)
 Format
 Document (PDF)
 Title
 LONESUM MATRICES AND ACYCLIC ORIENTATIONS: ENUMERATION AND ASYMPTOTICS.
 Creator
 Khera, Jessica, Lundberg, Erik, Florida Atlantic University, Department of Mathematical Sciences, Charles E. Schmidt College of Science
 Abstract/Description

An acyclic orientation of a graph is an assignment of a direction to each edge in a way that does not form any directed cycles. Acyclic orientations of a complete bipartite graph are in bijection with a class of matrices called lonesum matrices, which can be uniquely reconstructed from their row and column sums. We utilize this connection and other properties of lonesum matrices to determine an analytic form of the generating function for the length of the longest path in an acyclic...
Show moreAn acyclic orientation of a graph is an assignment of a direction to each edge in a way that does not form any directed cycles. Acyclic orientations of a complete bipartite graph are in bijection with a class of matrices called lonesum matrices, which can be uniquely reconstructed from their row and column sums. We utilize this connection and other properties of lonesum matrices to determine an analytic form of the generating function for the length of the longest path in an acyclic orientation on a complete bipartite graph, and then study the distribution of the length of the longest path when the acyclic orientation is random. We use methods of analytic combinatorics, including analytic combinatorics in several variables (ACSV), to determine asymptotics for lonesum matrices and other related classes.
Show less  Date Issued
 2021
 PURL
 http://purl.flvc.org/fau/fd/FA00013716
 Subject Headings
 Matrices, Combinatorial analysis, Graph theory
 Format
 Document (PDF)
 Title
 THE STRUCTURAL ORGANIZATION AND SPECTRAL CHARACTERISTICS OF VISUAL WORKING MEMORY IN THE MONKEY FRONTOPARIETAL NETWORK.
 Creator
 Conklin, Bryan, Alexander, William, Florida Atlantic University, Center for Complex Systems and Brain Sciences, Charles E. Schmidt College of Science
 Abstract/Description

Working memory is a mental workspace which utilizes short and longterm memory to maintain and manipulate information. It is crucial in enabling cognitive control and is largely controlled by interactions within and between frontal and parietal cortices. Recent work has identified visual nonspatial, spatial, and visuospatial working memory spectral characteristics of the local field potential through simultaneous recordings from various areas across the monkey frontoparietal network. However,...
Show moreWorking memory is a mental workspace which utilizes short and longterm memory to maintain and manipulate information. It is crucial in enabling cognitive control and is largely controlled by interactions within and between frontal and parietal cortices. Recent work has identified visual nonspatial, spatial, and visuospatial working memory spectral characteristics of the local field potential through simultaneous recordings from various areas across the monkey frontoparietal network. However, the reports are minimal in number, and there is no clear narrative tying together the heterogenous functionality of the characteristics. Here, a new spectral model of monkey visual working memory is proposed to address these shortcomings. It highlights functional roles for low, mid, and high frequency bands. Next, the organization of structural connectivity which gives rise to these spectral characteristics is investigated. A new binary association matrix representing connections in the frontoparietal network is proposed. A graph theoretic analysis on the matrix found that a 3node dynamical relaying M9 motif was a fundamental building block of the network. It is optimally structured for the synchrony found in the spectral model. The network was also found to have a smallworld architecture, which confers the integration and specialization of function required by visual working memory. Afterwards, three hypotheses generated by the spectral model are tested on nonspatial data. The low and mid band hypotheses were supported by evidence, while the high band hypothesized activity was not observed. This adds credibility to the roles identified in the model for the low and mid band and identifies a need for further investigation of the high band role. Finally, opportunities to expand the spectral model, analyze the M9 motif, and further test the model are explored. In the future, the spectral model could evolve to apply its predictions to humans in the pursuit of treatments for neurological disorders.
Show less  Date Issued
 2020
 PURL
 http://purl.flvc.org/fau/fd/FA00013584
 Subject Headings
 Memory, ShortTerm, Working memory, Monkeys, Graph theory
 Format
 Document (PDF)
 Title
 Graph labeling and nonseparating trees.
 Creator
 Gottipati, Chenchu B., Locke, Stephen C., Florida Atlantic University, Charles E. Schmidt College of Science, Department of Mathematical Sciences
 Abstract/Description

This dissertation studies two independent problems, one is about graph labeling and the other problem is related to connectivity condition in a simple graph. Graph labeling is a rapidly developing area of research in graph theory, having connections with a variety of applicationoriented areas such as VLSI optimization, data structures and data representation. Furthermore, the connectivity conditions in a simple graphs may help us to study the new aspects of ad hoc networks, social networks...
Show moreThis dissertation studies two independent problems, one is about graph labeling and the other problem is related to connectivity condition in a simple graph. Graph labeling is a rapidly developing area of research in graph theory, having connections with a variety of applicationoriented areas such as VLSI optimization, data structures and data representation. Furthermore, the connectivity conditions in a simple graphs may help us to study the new aspects of ad hoc networks, social networks and web graphs. In chapter 2, we study path systems, reduced path systems and how to construct a super edgegraceful tree with any number of edges using path systems. First, we give an algorithm to reduce a labeled path system to a smaller labeled path system of a different type. First, we investigate the cases (m, k) = (3; 5) and (m, k) = (4; 7), where m is the number of paths and 2k is the length of each path, and then we give a generalization for any k, m = 3 and m = 4. We also describe a procedure to construct a superedgegraceful tree with any number of edges.
Show less  Date Issued
 2014
 PURL
 http://purl.flvc.org/fau/fd/FA00004289, http://purl.flvc.org/fau/fd/FA00004289
 Subject Headings
 Computational complexity, Computer graphics, Graph theory, Integrated circuits  Very large scale integration, Mathematical optimization
 Format
 Document (PDF)
 Title
 An Empirical Study of Random Forests for Mining Imbalanced Data.
 Creator
 Golawala, Moiz M., Khoshgoftaar, Taghi M., Florida Atlantic University
 Abstract/Description

Skewed or imbalanced data presents a significant problem for many standard learners which focus on optimizing the overall classification accuracy. When the class distribution is skewed, priority is given to classifying examples from the majority class, at the expense of the often more important minority class. The random forest (RF) classification algorithm, which is a relatively new learner with appealing theoretical properties, has received almost no attention in the context of skewed...
Show moreSkewed or imbalanced data presents a significant problem for many standard learners which focus on optimizing the overall classification accuracy. When the class distribution is skewed, priority is given to classifying examples from the majority class, at the expense of the often more important minority class. The random forest (RF) classification algorithm, which is a relatively new learner with appealing theoretical properties, has received almost no attention in the context of skewed datasets. This work presents a comprehensive suite of experimentation evaluating the effectiveness of random forests for learning from imbalanced data. Reasonable parameter settings (for the Weka implementation) for ensemble size and number of random features selected are determined through experimentation oil 10 datasets. Further, the application of seven different data sampling techniques that are common methods for handling imbalanced data, in conjunction with RF, is also assessed. Finally, RF is benchmarked against 10 other commonlyused machine learning algorithms, and is shown to provide very strong performance. A total of 35 imbalanced datasets are used, and over one million classifiers are constructed in this work.
Show less  Date Issued
 2007
 PURL
 http://purl.flvc.org/fau/fd/FA00012520
 Subject Headings
 Data miningCase studies, Machine learningCase studies, Data structure (Computer science), Trees (Graph theory)Case studies
 Format
 Document (PDF)
 Title
 Embedding binomial trees in faulty hypercube multiprocessors.
 Creator
 Luo, Yinqiu., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
 Abstract/Description

We study the embedding of binomial trees with variable roots in faulty hypercubes. Based on novel embedding strategies, we propose three embedding algorithms with variable nodes as the root. The first algorithm can tolerate up to n  1 faulty links, but the execution can be done within log2(n  1) subcube splits. The second one can tolerate up to [(3(n  1))\2] faulty links. The last one can tolerate up to [(3(n  4))\2] faulty nodes.
 Date Issued
 1996
 PURL
 http://purl.flvc.org/fcla/dt/15345
 Subject Headings
 Hypercube networks (Computer networks), Trees (Graph theory), Multiprocessors, Parallel processing (Electronic computers), Computer algorithms, Faulttolerant computing, Embedded computer systems
 Format
 Document (PDF)
 Title
 Computing topological dynamics from time series.
 Creator
 Wess, Mark., Charles E. Schmidt College of Science, Department of Mathematical Sciences
 Abstract/Description

The topological entropy of a continuous map quantifies the amount of chaos observed in the map. In this dissertation we present computational methods which enable us to compute topological entropy for given time series data generated from a continuous map with a transitive attractor. A triangulation is constructed in order to approximate the attractor and to construct a multivalued map that approximates the dynamics of the linear interpolant on the triangulation. The methods utilize...
Show moreThe topological entropy of a continuous map quantifies the amount of chaos observed in the map. In this dissertation we present computational methods which enable us to compute topological entropy for given time series data generated from a continuous map with a transitive attractor. A triangulation is constructed in order to approximate the attractor and to construct a multivalued map that approximates the dynamics of the linear interpolant on the triangulation. The methods utilize simplicial homology and in particular the Lefschetz Fixed Point Theorem to establish the existence of periodic orbits for the linear interpolant. A semiconjugacy is formed with a subshift of nite type for which the entropy can be calculated and provides a lower bound for the entropy of the linear interpolant. The dissertation concludes with a discussion of possible applications of this analysis to experimental time series.
Show less  Date Issued
 2008
 PURL
 http://purl.flvc.org/FAU/186294
 Subject Headings
 Algebraic topology, Graph theory, Fixed point theory, Singularities (Mathematics)
 Format
 Document (PDF)