An analog to intrinsic linking, intrinsic even linking, is explored in the first half of this paper. Four graphs are established to be minor minimal intrinsically even linked, and it is conjectured that they form a complete minor minimal set. Some characterizations are given, using the simplest of the four graphs as an integral part of the arguments, that may be useful in proving the conjecture. The second half of this paper investigates a new approach to intrinsic knotting. By adapting knot energy to graphs, it is hoped that intrinsic knotting can be detected through direct computation. However, graph energies are difficult to compute, and it is unclear whether they can be used to determine whether a graph is intrinsically knotted.

We introduce the concept of dot product representations of graphs, giving some motivations as well as surveying the previously known results. We extend these representations to more general fields, looking at the complex numbers, rational numbers, and finite fields. Finally, we study the behavior of dot product representations in field extensions.

This thesis expands on the notion of linear complexity for a graph as defined by Michael Orrison and David Neel in their paper "The Linear Complexity of a Graph." It considers additional classes of graphs and provides upper bounds for additional types of graphs and graph operations.

The path search problem considers a simple model of communication networks as channel graphs: directed acyclic graphs with a single source and sink. We consider each vertex to represent a switching point, and each edge a single communication line. Under a probabilistic model where each edge may independently be free (available for use) or blocked (already in use) with some constant probability, we seek to efficiently search the graph: examine (on average) as few edges as possible before determining if a path of free edges exists from source to sink. We consider the difficulty of searching various graphs under different search models, and examine the computational complexity of calculating the search cost of arbitrary graphs.

The class of squarefree monomial ideals is a classical object in commutative algebra, which has a strong connection to combinatorics. Our main goal throughout this dissertation is to study the algebraic properties of squarefree monomial ideals using combinatorial structures and invariants of hypergraphs. We focus on the following algebraic properties and invariants: the persistence property, non-increasing depth property, Castelnuovo-Mumford regularity and projective dimension. It has been believed for a long time that squarefree monomial ideals satisfy the persistence property and non-increasing depth property. In a recent work, Kaiser, Stehlik and Skrekovski provided a family of graphs and showed that the cover ideal of the smallest member of this family gives a counterexample to the persistence and non-increasing depth properties. We show that the cover ideals of all members of their family of graphs indeed fail to have the persistence and non-increasing depth properties. Castelnuovo-Mumford regularity and projective dimension are both important invariants in commutative algebra and algebraic geometry that govern the computational complexity of ideals and modules. Our focus is on finding bounds for the regularity in terms of combinatorial data from associated hypergraphs. We provide two upper bounds for the edge ideal of any vertex decomposable graph in terms of induced matching number and the number of cycles. We then give an upper bound for the edge ideal of a special class of vertex decomposable hypergraphs. Moreover, we generalize a domination parameter from graphs to hypergraphs and use it to give an upper bound for the projective dimension of the edge ideal of any hypergraph. / Mengyao Sun

No description available.

No description available.

Randomised algorithms are an effective method of attacking computationally intractable problems. A simple and fast randomised algorithm may produce results to an accuracy sufficient for many purposes, especially in the average case. In this thesis we consider average case analyses of heuristics for certain NP-hard graph optimisation problems. In particular, we consider algorithms that find dominating sets of random regular directed graphs. As well as providing an average case analysis, our results also determine new upper bounds on domination numbers of random regular directed graphs. The algorithms for random regular directed graphs considered in this thesis are known as prioritised algorithms. Each prioritised algorithm determines a discrete random process. This discrete process may be continuously approximated using differential equations. Under certain conditions, the solutions to these differential equations describe the behaviour of the prioritised algorithm. Applying such an analysis to prioritised algorithms directly is difficult. However, we are able to use prioritised algorithms to define new algorithms, called deprioritised algorithms, that can be analysed in this fashion. Defining a deprioritised algorithm based on a given prioritised algorithm, and then analysing the deprioritised algorithm, is called the deprioritised approach. The initial theory describing the deprioritised approach was developed by Wormald and has been successfully applied in many cases. However not all algorithms are covered by Wormald??s theory: for example, algorithms for random regular directed graphs. The main contribution of this thesis is the extension of the deprioritised approach to a larger class of prioritised algorithms. We demonstrate the new theory by applying it to two algorithms which find dominating sets of random regular directed graphs.

Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 95).

In this dissertation, we consider some spectral problems of optical waveguide and quantum graph theories. We study spectral problems that arise when considerating optical waveguides in photonic band-gap (PBG) materials. Specifically, we address the issue of the existence of modes guided by linear defects in photonic crystals. Such modes can be created for frequencies in the spectral gaps of the bulk material and thus are evanescent in the bulk (i.e., confined to the guide). In the quantum graph part we prove the validity of the limiting absorption principle for finite graphs with infinite leads attached. In particular, this leads to the absence of a singular continuous spectrum. Another problem in quantum graph theory that we consider involves opening gaps in the spectrum of a quantum graph by replacing each vertex of the original graph with a finite graph. We show that such "decorations" can be used to create spectral gaps.