No description available.

This thesis discusses groups, modules, the module of homomorphisms, and extension of modules.

Let K be a class of finite graphs and F = {F1, F2, ..., Fm} be a set of finite graphs. Then, K is said to have finite-duality if there exists a graph U in K such that for any graph G in K, G is homomorphic to U if and only if Fi is not homomorphic to G, for all i = 1, 2, ..., m. Nešetřil asked in [J. Nešetřil, Homonolo Combinatorics Workshop, Nova Louka, Czech Rep., (2003)] if non-trivial examples can be found. In this note, we answer this positively by showing classes containing arbitrary long anti-chains and yet having the finite-duality property.

No description available.

Among the vital problems in a variety of emerging applications is the graph matching problem, which is to determine whether two graphs are similar, and if so, find all the valid matches in one graph for the other, based on specified metrics. Traditional graph matching approaches are mostly based on graph homomorphism and isomorphism, falling short of capturing both structural and semantic similarity in real life applications. Moreover, it is preferable while difficult to find all matches with high accuracy over complex graphs. Worse still, the graph structures in real life applications constantly bear modifications. In response to these challenges, this thesis presents a series of approaches for ef?ciently solving graph matching problems, over both static and dynamic real life graphs. Firstly, the thesis extends graph homomorphism and subgraph isomorphism, respectively, by mapping edges from one graph to paths in another, and by measuring the semantic similarity of nodes. The graph similarity is then measured by the metrics based on these extensions. Several optimization problems for graph matching based on the new metrics are studied, with approximation algorithms having provable guarantees on match quality developed. Secondly, although being extended in the above work, graph matching is defined in terms of functions, which cannot capture more meaningful matches and is usually hard to compute. In response to this, the thesis proposes a class of graph patterns, in which an edge denotes the connectivity in a data graph within a predefined number of hops. In addition, the thesis defines graph pattern matching based on a notion of bounded simulation relation, an extension of graph simulation. With this revision, graph pattern matching is in cubic-time by providing such an algorithm, rather than intractable. Thirdly, real life graphs often bear multiple edge types. In response to this, the thesis further extends and generalizes the proposed revisions of graph simulation to a more powerful case: a novel set of reachability queries and graph pattern queries, constrained by a subclass of regular path expressions. Several fundamental problems of the queries are studied: containment, equivalence and minimization. The enriched reachability query does not increase the complexity of the above problems, shown by the corresponding algorithms. Moreover, graph pattern queries can be evaluated in cubic time, where two such algorithms are proposed. Finally, real life graphs are frequently updated with small changes. The thesis investigates incremental algorithms for graph pattern matching defined in terms of graph simulation, bounded simulation and subgraph isomorphism. Besides studying the results on the complexity bounds, the thesis provides the experimental study verifying that these incremental algorithms significantly outperform their batch counterparts in response to small changes, using real-life data and synthetic data.

A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)-mixed graphs) and k−edge-coloured graphs ((0, k)−mixed graphs). A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. An m−colouring of a (j, k)−mixed graph is a homomorphism from that graph to a target with m vertices. The (j, k)−chromatic number of a (j, k)−mixed graph is the least m such that an m−colouring exists. When (j, k) = (0, 1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring. Similarly, when (j, k) = (1, 0) and (j, k) = (0, k) these definitions are consistent with the usual definitions of homomorphism and colouring for oriented graphs and k−edge-coloured graphs, respectively. In this thesis we study the (j, k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1, 0)−chromatic number, more commonly called the oriented chromatic number, and the (0, k)−chromatic number. In examining oriented graphs, we provide improvements to the upper and lower bounds for the oriented chromatic number of the families of oriented graphs with maximum degree 3 and 4. We generalise the work of Sherk and MacGillivray on the 2−dipath chromatic number, to consider colourings in which vertices at the ends of iii a directed path of length at most k must receive different colours. We examine the implications of the work of Smolikova on simple colourings to study of the oriented chromatic number of the family of oriented planar graphs. In examining k−edge-coloured graphs we provide improvements to the upper and lower bounds for the family of 2−edge-coloured graphs with maximum degree 3. In doing so, we define the alternating 2−path chromatic number of k−edge-coloured graphs, a parameter similar in spirit to the 2−dipath chromatic number for oriented graphs. We also consider a notion of simple colouring for k−edge-coloured graphs, and show that the methods employed by Smolikova ́ for simple colourings of oriented graphs may be adapted to k−edge-coloured graphs. In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs. / Graduate

This paper establishes a basis for abelian categories, then gives the statement and proof of two equivalent definitions of an abelian category, the development of the basic theory of such categories, and the proof of some theorems involving this basic theory.

In (J Graph Theory 33 (2000), 14-24), Hell and Zhu proved that if a series-parallel graph G has girth at least 2⌊(3k-1)/2⌋, then χc(G)≤4k/(2k-1). In (J Graph Theory 33 (2000), 185-198), Chien and Zhu proved that the girth condition given in (J Graph Theory 33 (2000), 14-24) is sharp. Short proofs of both results are given in this note.

Let G and H be graphs. We say G is H-critical, if every proper subgraph of G except G itself is homomorphic to H. This generalizes the widely known concept of k-color-critical graphs, as they are the case H = Kk - 1. In 1963 [T. Gallai, Kritiche Graphen, I., Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 373-395], Gallai proved that the vertices of degree k in a Kk-critical graph induce a subgraph whose blocks are either odd cycles or complete graphs. We generalize Gallai's Theorem for every H-critical graph, where H = Kk - 2 + H′, (the join of a complete graph Kk - 2 with any graph H′). This answers one of the two unknown cases of a problem given in [J. Nešetřil, Y. Nigussie, Finite dualities and map-critical graphs on a fixed surface. (Submitted to Journal of Combin. Theory, Series B)]. We also propose an open question, which may be a characterization of all graphs for which Gallai's Theorem holds.

In this study, I will examine the beliefs and conceptual understanding of instructors and students from two abstract algebra classes. This research takes the form of a case study in which I answer four research questions, each addressing a relationship between instruction and beliefs or conceptual understanding. Specifically, these research questions are: 1. What beliefs do the instructors have about math, teaching, and learning and what relationship exists between these beliefs and instructional practice? 2. What is the relationship between instructional practice and students' beliefs about math, teaching, and learning? 3. What conceptual metaphors do the professors use to describe isomorphisms and homomorphisms and what relationship exists between these metaphors and the mathematical content in instruction? 4. What is the relationship between the mathematical content in instruction and conceptual metaphors the students use to describe isomorphisms and homomorphisms? In terms of beliefs, the instructors articulated considered positions on the nature of math, math learning, and math teaching. These beliefs were clearly reflected in their overall approaches to teaching. However, their instruction shifted in practice over the course of the semester. Students' beliefs seemed to shift slightly as a result of the ways their instructors taught. However, their core beliefs about math seemed unchanged and some lessons students took away were similar in the two classes. In terms of conceptual understanding, the instructors provided many conceptual metaphors that related to how they understood isomorphism. They struggled more to provide an image for homomorphism, which requires thinking about a more complicated mathematical object. Their understandings of isomorphism and homomorphism were largely reflected in their instruction with some notable differences. Students took away similar understandings of isomorphism to the instructors, but did not all take away the same level of structural understanding of homomorphism. In short, relationships between instructors' beliefs and instruction and between instructors' conceptual understanding and instruction were evident. However, certain elements were not made as clear as they perhaps intended. Relationships between instruction and students' beliefs and between instruction and students' conceptual understanding were also evident. However, relationships between instruction and beliefs were subtler than between instruction and conceptual understanding. / Doctor of Philosophy / In this study, I will examine the beliefs and conceptual understanding of instructors and students from two abstract algebra classes. I address four relationships: between instructors’ beliefs and instruction, between instruction and students’ beliefs, between instructors’ conceptual understanding and instruction, and between instruction and students’ conceptual understanding. Relationships between instructors’ beliefs and instruction and between instructors’ conceptual understanding and instruction were evident. However, certain elements were not made as clear as they perhaps intended. Relationships between instruction and students’ beliefs and between instruction and students’ conceptual understanding were also evident. However, relationships between instruction and beliefs were subtler than between instruction and conceptual understanding.