Spelling suggestions: "subject:"[een] GRAPHS"" "subject:"[enn] GRAPHS""
31 |
Intrinsic Linking and Knotting of GraphsKozai, Kenji 01 May 2008 (has links)
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.
|
32 |
Dot Product Representations of GraphsMinton, Gregory 01 May 2008 (has links)
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.
|
33 |
Graph Linear ComplexityWinerip, Jason 01 May 2008 (has links)
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.
|
34 |
Locality and Complexity in Path SearchHunter, Andrew 01 May 2009 (has links)
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.
|
35 |
Algebraic Properties Of Squarefree Monomial IdealsJanuary 2016 (has links)
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
|
36 |
Perfect graphsHoang, Chinh T. January 1985 (has links)
No description available.
|
37 |
Two classes of perfect graphsHayward, Ryan B. January 1986 (has links)
No description available.
|
38 |
The deprioritised approach to prioritised algorithmsHowe, Stephen Alexander, Mathematics & Statistics, Faculty of Science, UNSW January 2008 (has links)
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.
|
39 |
Polynomially-divided solutions of bipartite self-differential functional equationsDimitrov, Youri, January 2006 (has links)
Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 95).
|
40 |
Spectral problems of optical waveguides and quantum graphsOng, Beng Seong 30 October 2006 (has links)
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.
|
Page generated in 0.043 seconds