Thesis (Ph.D.)--McMaster University (Canada), 1992. / Source: Dissertation Abstracts International, Volume: 54-08, Section: B, page: 4199. Adviser: Bernhard Banaschewski.

Thesis (D.Com.(Financial Management Sciences))--University of Pretoria, 2009. / Abstract in English. Includes bibliographical references.

We investigate quotient-fine nearness frames, showing that they are reflective in the category of strong nearness frames, and that, in those with spatial completion, any near subset is contained in a near grill. We construct two categories, each of which is shown to be equivalent to that of quotient-fine nearness frames. We also consider some subcategories of the category of nearness frames, which are co-hereditary and closed under coproducts. We give due attention to relations between these subcategories. We introduce totally strong nearness frames, whose category we show to be closed under completions. We investigate N-homomorphisms and remote points in the context of totally bounded uniform frames, showing the role played by these uniform N-homomorphisms in the transfer of remote points, and their relationship with C -quotient maps. A further study on grills enables us to establish, among other things, that grills are precisely unions of prime filters. We conclude the thesis by showing that the lattice of all nearnesses on a regular frame is a pseudo-frame, by which we mean a poset pretty much like a frame except for the possible absence of the bottom element. / Mathematical Sciences / Ph.D. (Mathematics)

This thesis is about graph-indexed random walks, Lipschitz mappings and graph homo- morphisms. It discusses connections between these notions, surveys the existing results, and shows new results. Graph homomorphism is an adjacency-preserving mapping between two graphs. Our main objects of study are graph homomorphisms to an infinite path. We are interested in two parameters: maximum range and average range. The average range of a graph is the expected size of the image of a uniformly picked random homomorphism to an infinite path. We obtain formulas for several graph classes and investigate main conjectures on this parameter. For maximum range parameter we show a general formula and an algorithm to compute it for general graphs. Besides that, we study the problem of extending a prescribed partial graph homomorphism to a full graph homomorphism. We show that this problem is polynomial in some cases. 1

A $(m,n)$-mixed graph is a mixed graph whose edges are assigned one of $m$ colours, and whose arcs are assigned one of $n$ colours. Let $G$ be a $(m,n)$-mixed graph and $\pi=(\alpha,\beta,\gamma_1,\gamma_2,\ldots,\gamma_n)$ be a $(n+2)$-tuple of permutations from $S_m \times S_n \times S_2^n$. We define \emph{switching at a vertex $v$ with respect to $\pi$} as follows. Replace each edge $vw$ of colour $\phi$ by an edge $vw$ of colour $\alpha(\phi)$, and each arc $vx$ of colour $\phi$ by an arc $\gamma_\phi(vx)$ of colour $\beta(\phi)$. In this thesis, we study the complexity of the question: ``Given a $(m,n)$-mixed graph $G$, is there a sequence of switches at vertices of $G$ with respect to the fixed group $\Gamma$ so that the resulting $(m,n)$-mixed graph admits a homomorphism to some $(m,n)$-mixed graph on $2$ vertices?'' We show the following: (1) When restricted to $(m,0)$-mixed graphs $H$ on at most $2$ vertices, the $\Gamma$-switchable homomorphism decision problem is solvable in polynomial time; (2) for each bipartite $(0,n)$-mixed graph $H$, there is a bipartite $(2n,0)$-mixed graph such that the respective $\Gamma$-switchable homomorphism decision problems are polynomially equivalent; (3) For all $(m,n)$-mixed graphs and groups, when $H$ has at most $2$ vertices, the $\Gamma$-switchable homomorphism decision problem is polynomial time solvable; (4) For a yes-instance of the $\Gamma$-switchable homomorphism problem for $(m,0)$-mixed graphs, we can find in quadratic time a sequence of switches on $G$ such that the resulting $(m,0)$-mixed graph admits a homomorphism to $H$. By proving (1)-(4), we show that the $\Gamma$-switchable $2$-colouring problem for $(m,n)$-mixed graphs is solvable in polynomial time for all finite permutation groups $\Gamma$ and provide a step towards a dichotomy theorem for the complexity of the $\Gamma$-switchable homomorphism decision problem. / Graduate

Let X be a planar or one-dimensional Peano continuum. Let E be a Hawaiian Earring with fundamental group H. We show that every homomorphism from H to the fundamental group of X is conjugate to a homomorphism which is induced by a continuous function.

The purpose of this thesis is to construct finite groups as homomorphic images of progenitors.

This thesis investigates three areas of the theory of graph homomorphisms: cores of graphs, the homomorphism order, and quantum homomorphisms. A core of a graph X is a vertex minimal subgraph to which X admits a homomorphism. Hahn and Tardif have shown that, for vertex transitive graphs, the size of the core must divide the size of the graph. This motivates the following question: when can the vertex set of a vertex transitive graph be partitioned into sets which each induce a copy of its core? We show that normal Cayley graphs and vertex transitive graphs with cores half their size always admit such partitions. We also show that the vertex sets of vertex transitive graphs with cores less than half their size do not, in general, have such partitions. Next we examine the restriction of the homomorphism order of graphs to line graphs. Our main focus is in comparing this restriction to the whole order. The primary tool we use in our investigation is that, as a consequence of Vizing's theorem, this partial order can be partitioned into intervals which can then be studied independently. We denote the line graph of X by L(X). We show that for all n ≥ 2, for any line graph Y strictly greater than the complete graph Kₙ, there exists a line graph X sitting strictly between Kₙ and Y. In contrast, we prove that there does not exist any connected line graph which sits strictly between L(Kₙ) and Kₙ, for n odd. We refer to this property as being ``n-maximal", and we show that any such line graph must be a core and the line graph of a regular graph of degree n. Finally, we introduce quantum homomorphisms as a generalization of, and framework for, quantum colorings. Using quantum homomorphisms, we are able to define several other quantum parameters in addition to the previously defined quantum chromatic number. We also define two other parameters, projective rank and projective packing number, which satisfy a reciprocal relationship similar to that of fractional chromatic number and independence number, and are closely related to quantum homomorphisms. Using the projective packing number, we show that there exists a quantum homomorphism from X to Y if and only if the quantum independence number of a certain product graph achieves |V(X)|. This parallels a well known classical result, and allows us to construct examples of graphs whose independence and quantum independence numbers differ. Most importantly, we show that if there exists a quantum homomorphism from a graph X to a graph Y, then ϑ̄(X) ≤ ϑ̄(Y), where ϑ̄ denotes the Lovász theta function of the complement. We prove similar monotonicity results for projective rank and the projective packing number of the complement, as well as for two variants of ϑ̄. These immediately imply that all of these parameters lie between the quantum clique and quantum chromatic numbers, in particular yielding a quantum analog of the well known ``sandwich theorem". We also briefly investigate the quantum homomorphism order of graphs.

This thesis investigates three areas of the theory of graph homomorphisms: cores of graphs, the homomorphism order, and quantum homomorphisms. A core of a graph X is a vertex minimal subgraph to which X admits a homomorphism. Hahn and Tardif have shown that, for vertex transitive graphs, the size of the core must divide the size of the graph. This motivates the following question: when can the vertex set of a vertex transitive graph be partitioned into sets which each induce a copy of its core? We show that normal Cayley graphs and vertex transitive graphs with cores half their size always admit such partitions. We also show that the vertex sets of vertex transitive graphs with cores less than half their size do not, in general, have such partitions. Next we examine the restriction of the homomorphism order of graphs to line graphs. Our main focus is in comparing this restriction to the whole order. The primary tool we use in our investigation is that, as a consequence of Vizing's theorem, this partial order can be partitioned into intervals which can then be studied independently. We denote the line graph of X by L(X). We show that for all n ≥ 2, for any line graph Y strictly greater than the complete graph Kₙ, there exists a line graph X sitting strictly between Kₙ and Y. In contrast, we prove that there does not exist any connected line graph which sits strictly between L(Kₙ) and Kₙ, for n odd. We refer to this property as being ``n-maximal", and we show that any such line graph must be a core and the line graph of a regular graph of degree n. Finally, we introduce quantum homomorphisms as a generalization of, and framework for, quantum colorings. Using quantum homomorphisms, we are able to define several other quantum parameters in addition to the previously defined quantum chromatic number. We also define two other parameters, projective rank and projective packing number, which satisfy a reciprocal relationship similar to that of fractional chromatic number and independence number, and are closely related to quantum homomorphisms. Using the projective packing number, we show that there exists a quantum homomorphism from X to Y if and only if the quantum independence number of a certain product graph achieves |V(X)|. This parallels a well known classical result, and allows us to construct examples of graphs whose independence and quantum independence numbers differ. Most importantly, we show that if there exists a quantum homomorphism from a graph X to a graph Y, then ϑ̄(X) ≤ ϑ̄(Y), where ϑ̄ denotes the Lovász theta function of the complement. We prove similar monotonicity results for projective rank and the projective packing number of the complement, as well as for two variants of ϑ̄. These immediately imply that all of these parameters lie between the quantum clique and quantum chromatic numbers, in particular yielding a quantum analog of the well known ``sandwich theorem". We also briefly investigate the quantum homomorphism order of graphs.

Thesis (Ph.D.)--McMaster University (Canada), 1991. / Source: Dissertation Abstracts International, Volume: 54-02, Section: B, page: 0867.