The study of cycles, particularly Hamiltonian cycles, is very important in many applications. Bondy posited his famous metaconjecture, that every condition sufficient for Hamiltonicity actually guarantees a graph is pancyclic. Pancyclicity is a stronger structural property than Hamiltonicity. An even stronger structural property is for a graph to be cycle extendable. Hendry conjectured that any graph which is Hamiltonian and chordal is cycle extendable. In this dissertation, cycle extendability is investigated and generalized. It is proved that chordal 2-connected K1,3-free graphs are cycle extendable. S-cycle extendability was defined by Beasley and Brown, where S is any set of positive integers. A conjecture is presented that Hamiltonian chordal graphs are {1, 2}-cycle extendable. Dirac’s Theorem is an classic result establishing a minimum degree condition for a graph to be Hamiltonian. Ore’s condition is another early result giving a sufficient condition for Hamiltonicity. In this dissertation, generalizations of Dirac’s and Ore’s Theorems are presented. The Chvatal-Erdos condition is a result showing that if the maximum size of an independent set in a graph G is less than or equal to the minimum number of vertices whose deletion increases the number of components of G, then G is Hamiltonian. It is proved here that the Chvatal-Erdos condition guarantees that a graph is cycle extendable. It is also shown that a graph having a Hamiltonian elimination ordering is cycle extendable. The existence of Hamiltonian cycles which avoid sets of edges of a certain size and certain subgraphs is a new topic recently investigated by Harlan, et al., which clearly has applications to scheduling and communication networks among other things. The theory is extended here to bipartite graphs. Specifically, the conditions for the existence of a Hamiltonian cycle that avoids edges, or some subgraph of a certain size, are determined for the bipartite case. Briefly, this dissertation contributes to the state of the art of Hamiltonian cycles, cycle extendability and edge and graph avoiding Hamiltonian cycles, which is an important area of graph theory.

A graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices there are at least k other vertices, each of which is adjacent to the first m vertices but not adjacent to any of the latter n vertices. The class of graphs having property P(m.n,k) is denoted by ζ(m,n,k). The problem that arises is that of characterizing the class ζ(m,n,k). One particularly interesting problem that arises concerns the functionP(m,n,k) = min{υ(G) : G є ζ(m,n,k) }.In Chapter 2, we establish some important properties of graphs in the class ζ(m,n,k) and a lower bound on p(m,n,k). In particular, we prove thatp(n,n,k) ≥ 4n-1 (2(n+k) + ½ (3 = (-1)n+k+1} + 1/3 l 1/3One of the results in Chapter 2 is that almost all graphs have property P(m,n,k). However, few members of ζ(m,n,k) have been exhibited. In Chapter 3. we construct classes of graphs having property P(l,n,k) . These classes include the cubes, "generalized" Petersen graphs and "generalized" Hoffman-Singleton graphs.An important graph in the study of the class ζ(m,n,k) is the Paley graph Gq defined as follows. Let q = l(mod 4) be a prime power. The vertices of Gq are the elements of the finite field IFq. Two vertices a and b are joined by an edge if and only if their difference is a quadratic residue, that is a - b = y2 for some y є IFq. In chapter 4, we prove that for a prime p = l(mod 4), all sufficiently large Paley graphs GP satisfy property P(m.n,k). This is established by making use of results from prime number theory.In Chapter 5 , we establish, by making use of results from finite fields, the adjacency properties of Paley graphs of order q = pd , with p a prime.For directed graphs, there is an analogue of the above adjacency property concerning tournaments. A tournament Tq of order q is said to have property Q(n,k) if every subset of n vertices of Tq is dominated (if there is an arc directed from ++ / a vertex u to a vertex v, we say that u dominates v and that v is dominated by u) by at least k other vertices.Let q = 3(mod 4) is a prime power. The Paley tournament Dq is defined as follows. The vertices of Dq are the elements of the finite field IFq. Vertex a is ioined to vertex b by an arc if and only if a - b is a quadratic residue in Fq. In Chapter 6, we prove that the Paley tournament Dq has property Q(n,k) wheneverq > {(n - 3)2n-1 + Z}G + kZn - 1. A graph G is said to have property P*(rn,n,k) if for any set of rn + n distinct vertices of G there are exactly k other vertices, each of which is adjacent to the first m vertices of the set but not adjacent to any of the latter n vertices. The class of graphs having property P*(m.n,k) is denoted by S*(m,n.k). The class S*(m,n,k) has been studied when one of m or n is zero. In Chapter 7, we show that, for m = n = 1, graphs with this property (k + t)' + 1, are the strongly regular graphs with parameters ( k + t,t - 1,t) for some positive integer t. For rn 2 1, n 2 1, and m + n 2 3, we show that, there is no graph having property P*(m.n,k), for any positive integer k. The first Chapter of this thesis provides the motivation, terminology. general concepts and the problems concerning the adjacency properties of graphs. In Chapter 8 . we present some open problems.

Data warehouses were envisioned to facilitate analytical reporting and data visualization by providing a model for the flow of data from operational databases to decision support environments. Decision support environments provide a multidimensional conceptual view of the underlying data warehouse, which is usually stored in relational DBMSs. Typically, there is an impedance mismatch between this conceptual view — shared also by all decision support applications accessing the data warehouse — and the physical model of the data stored in relational DBMSs. This thesis presents a mapping compilation algorithm in the context of the Conceptual Integration Model (CIM) [67] framework. In the CIM framework, the relationships between the conceptual model and the physical model are specified by a set of attribute-to-attribute correspondences. The algorithm compiles these correspondences into a set of mappings that associate each construct in the conceptual model with a query on the physical model. Moreover, the homogeneity and summarizability of data in conceptual models is the key to accurate query answering, a necessity in decision making environments. A data-driven approach to refactor relational models into summarizable schemas and instances is proposed as the solution of this issue. We outline the algorithms and challenges in bridging multidimensional conceptual models and the physical model of data warehouses and discuss experimental results.

Data warehouses were envisioned to facilitate analytical reporting and data visualization by providing a model for the flow of data from operational databases to decision support environments. Decision support environments provide a multidimensional conceptual view of the underlying data warehouse, which is usually stored in relational DBMSs. Typically, there is an impedance mismatch between this conceptual view — shared also by all decision support applications accessing the data warehouse — and the physical model of the data stored in relational DBMSs. This thesis presents a mapping compilation algorithm in the context of the Conceptual Integration Model (CIM) [67] framework. In the CIM framework, the relationships between the conceptual model and the physical model are specified by a set of attribute-to-attribute correspondences. The algorithm compiles these correspondences into a set of mappings that associate each construct in the conceptual model with a query on the physical model. Moreover, the homogeneity and summarizability of data in conceptual models is the key to accurate query answering, a necessity in decision making environments. A data-driven approach to refactor relational models into summarizable schemas and instances is proposed as the solution of this issue. We outline the algorithms and challenges in bridging multidimensional conceptual models and the physical model of data warehouses and discuss experimental results.

This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting combinatorial incidence structures. We begin with background on the dominating set problem and a review of known bounds, focusing on algebraic bounds. We then consider this problem in the Kneser graphs, discussing basic results and previous work. We compute the domination number for a few of the Kneser graphs with the aid of some original results. We also investigate the connections between Kneser graph domination and the theory of combinatorial designs, and introduce a new type of design that generalizes the properties of dominating sets in Kneser graphs. We then consider dominating sets in the vector space analogue of Kneser graphs. We end by highlighting connections between the dominating set problem and other areas of combinatorics. Conjectures and open problems abound.

We will discuss three ways to bound the chromatic number on a Cayley graph. 1. If the connection set contains information about a smaller graph, then these two graphs are related. Using this information, we will show that Cayley graphs cannot have chromatic number three. 2. We will prove a general statement that all vertex-transitive maximal triangle-free graphs on <i>n</i> vertices with valency greater than <i>n</i>/3 are 3-colourable. Since Cayley graphs are vertex-transitive, the bound of general graphs also applies to Cayley graphs. 3. Since Cayley graphs for abelian groups arise from vector spaces, we can view the connection set as a set of points in a projective geometry. We will give a characterization of all large complete caps, from which we derive that all maximal triangle-free cubelike graphs on 2ⁿ vertices and valency greater than 2ⁿ/4 are either bipartite or 4-colourable.

This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting combinatorial incidence structures. We begin with background on the dominating set problem and a review of known bounds, focusing on algebraic bounds. We then consider this problem in the Kneser graphs, discussing basic results and previous work. We compute the domination number for a few of the Kneser graphs with the aid of some original results. We also investigate the connections between Kneser graph domination and the theory of combinatorial designs, and introduce a new type of design that generalizes the properties of dominating sets in Kneser graphs. We then consider dominating sets in the vector space analogue of Kneser graphs. We end by highlighting connections between the dominating set problem and other areas of combinatorics. Conjectures and open problems abound.

In this thesis we consider two classes of binary matroids, even cycle matroids and even cut matroids. They are a generalization of graphic and cographic matroids respectively. We focus on two main problems for these classes of matroids. We first consider the Isomorphism Problem, that is the relation between two representations of the same matroid. A representation of an even cycle matroid is a pair formed by a graph together with a special set of edges of the graph. Such a pair is called a signed graph. A representation for an even cut matroid is a pair formed by a graph together with a special set of vertices of the graph. Such a pair is called a graft. We show that two signed graphs representing the same even cycle matroid relate to two grafts representing the same even cut matroid. We then present two classes of signed graphs and we solve the Isomorphism Problem for these two classes. We conjecture that any two representations of the same even cycle matroid are either in one of these two classes, or are related by a local modification of a known operation, or form a sporadic example. The second problem we consider is finding the excluded minors for these classes of matroids. A difficulty when looking for excluded minors for these classes arises from the fact that in general the matroids may have an arbitrarily large number of representations. We define degenerate even cycle and even cut matroids. We show that a 3-connected even cycle matroid containing a 3-connected non-degenerate minor has, up to a simple equivalence relation, at most twice as many representations as the minor. We strengthen this result for a particular class of non-degenerate even cycle matroids. We also prove analogous results for even cut matroids.

A star graph consists of an arbitrary number of segments that are joined at a point which is called the vertex. In this work it is investigated from a pure theoretical point of view, in the framework of quantum field theory. As a concrete physical application, the electric conductance tensor is obtained. In particular it is shown that this conductance behaves differently according to whether the scattering matrix associated with the vertex of the graph has bound-state poles or not.

The Ambarzumyan Theorem states that for the classical Sturm-Liouville problem on $[0,1]$, if the set of Neumann eigenvalue $sigma_N={(npi)^2: nin { f N}cup { 0}}$, then the potential function $q=0$. In this thesis, we study the analogues of Ambarzumyan Theorem for the Sturm-Liouville operators on star-shaped graphs with 3 edges of different lengths. We first solve the direct problem: to find out the set of eigenvalues when $q=0$. Then we use the theory of transformation operators and Raleigh-Ritz inequality to prove the inverse problem. Following Pivovarchik's work on star-shaped graphs of uniform lengths, we analyze the Kirchoff condition in detail to prove our theorems. In particular, we study the cases when the lengths of the 3 edges satisfy $a_1=a_2=frac{1}{2}a_3$ or $a_1=frac{1}{2}a_2=frac{1}{3}a_3$. Furthermore, we work on Neumann boundary conditions as well as Dirichlet boundary conditions. In the latter case, some assumptions about $q$ have to be made.