Graph theory

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 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.

Working memory is a mental workspace which utilizes short and long-term 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 3-node 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 small-world 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 non-spatial 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.

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 application-oriented 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 edge-graceful 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 super-edge-graceful tree with any number of edges.

Let G be a 2-connected 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 non-hamiltonian or bipartite, cycles of length at least 2d can be used.

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 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.

This thesis shows that a planar graph is uniquely embeddable in a
sphere whenever it is three-connected and gives related results
about planar graphs of lower connectivity and about non- planar
graphs. A section on the fourteen non-planar graphs with six
vertices is also included.

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 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.