Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 20 for “"graph homomorphisms"”.

  1. Graph Homomorphisms and Vector Colorings

    A graph vertex coloring is an assignment of labels, which are referred to as colors, such that no two adjacent vertices receive the same color. The vertex coloring problem is NP-Complete [8], and so no polynomial time algorithm is believed to exist. The notion of a graph vector coloring was …

    south-carolina Repository record for Graph Homomorphisms and Vector Colorings (opens in a new tab)

  2. The topology of graph homomorphisms

    In this thesis we consider topological aspects of graph homomorphisms. Our main object of study is the Hom complex of graphs, a space first introduced by Lovasz to obtain lower bounds on chromatic number, and more recently studied by Babson and Kozlov and others in a series of papers. We prove …

    washington Repository record for The topology of graph homomorphisms (opens in a new tab)

  3. Variations on a Theme: Graph Homomorphisms

    … 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 …

    waterloo Repository record for Variations on a Theme: Graph Homomorphisms (opens in a new tab)

  4. Counting, modular counting and graph homomorphisms

    <p>A homomorphism from a graph <em>G</em> to a graph <em>H</em> is a function from <em>V</em> (<em>G</em>) to <em>V</em> (<em>H</em>) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as …

    oxford Repository record for Counting, modular counting and graph homomorphisms (opens in a new tab)

  5. Extremal Problems for Graph Homomorphisms and Automata

    Graph theory first arose in 1736 when Euler developed the basic concepts solving the Bridges of Konigsberg problem. Many modern areas of graph theory are unified in the study of graph homomorphisms; a homomorphism is a function from the vertices of a source graph to the vertices of a target graph …

    nebraska Repository record for Extremal Problems for Graph Homomorphisms and Automata (opens in a new tab)

  6. Factorization Systems for Discrete Homotopy Theory

    … developed for the mathematical objects called graphs. In this thesis, I further develop one of these homotopy theories for graphs, called A-homotopy theory, by constructing a covering graph theory, completing the work of my Master’s thesis. Covering graphs allow us to factor graph homomorphisms …

    calgary Repository record for Factorization Systems for Discrete Homotopy Theory (opens in a new tab)

  7. Mixed covering arrays on graphs and tabu search algorithms

    … networks and circuits. Mixed covering arrays on graphs are new generalizations of both mixed covering arrays and covering arrays on graphs. In this thesis, we give new theoretical results and constructions for mixed covering arrays on graphs. First, we extend to the mixed case the work done by …

    ottawa-retro Repository record for Mixed covering arrays on graphs and tabu search algorithms (opens in a new tab)

  8. Problems in catalan mixing and matchings in regular hypergraphs

    … of matchings and independent sets in regular graphs. First we propose a method for tackling the Upper Matching Conjecture of Friedland, et al. for matchings of small fixed size. Next we prove a conjecture of Galvin regarding the extremal graph for number of Widom-Rowlinson configurations, a …

    gatech Repository record for Problems in catalan mixing and matchings in regular hypergraphs (opens in a new tab)

  9. Graph Relations and Constrained Homomorphism Partial Orders

    We consider constrained variants of graph homomorphisms such as embeddings, monomorphisms, full homomorphisms, surjective homomorpshims, and locally constrained homomorphisms. We also introduce a new variation on this theme which derives from relations between graphs and is related to …

    qucosa-diss

  10. The Graphs of HU+00E4ggkvist & Hell

    This thesis investigates HU+00E4ggkvist & Hell graphs. These graphs are an extension of the idea of Kneser graphs, and as such share many attributes with them. A variety of original results on many different properties of these graphs are given. We begin with an examination of the transitivity and …

    waterloo Repository record for The Graphs of HU+00E4ggkvist & Hell (opens in a new tab)

  11. Studies on math education and weak trigraph homomorphisms

    … thesis is comprised of two parts: (i) a study of homomorphisms of weak trigraphs and (ii) an analysis of the effectiveness of the University of Victoria (UVic) Department of Mathematics and Statistics’ Pretest. In the first part of the thesis, we study homomorphisms of weak trigraphs. Results …

    uvic Repository record for Studies on math education and weak trigraph homomorphisms (opens in a new tab)

  12. Quantum Games, Graphs, and Gödel

    … computer science: the interplay between graph theory, computational complexity, and multiprover interactive proof systems. Specifically, we examine the connections between quantum graph properties, computability theory, and entangled nonlocal games.Building on prior work that defined …

    maryland Repository record for Quantum Games, Graphs, and Gödel (opens in a new tab)

  13. Algebraic Statistics

    … five papers. In paper I we define ideals of graph homomorphisms. These ideals generalize many of the toric ideals defined in terms of graphs that are important in algebraic statistics and commutative algebra. In paper II we study polytopes from subgraph statistics. Polytopes from subgraph …

    aalto Repository record for Algebraic Statistics (opens in a new tab)

  14. Weak homomorphisms of coalgebras

    … For example, there is a natural way to turn graphs into coalgebras obtained from the finite powerset functor. There is also a natural way to turn topological spaces into coalgebras for the filter functor. We observe that when coalgebras are used to model these mathematical structures, …

    iastate Repository record for Weak homomorphisms of coalgebras (opens in a new tab)

  15. Graph Parameters via Operator Systems

    … of operator systems and various aspects of graph theory. We start by showing that two graphs are isomorphic if and only if their corresponding operator systems are isomorphic with respect to their order structure. This means that the study of graphs is equivalent to the study of these …

    houston Repository record for Graph Parameters via Operator Systems (opens in a new tab)

  16. Toward the Combinatorial Limit Theory of free Words

    … advances in the combinatorial limit theory of graphs–notably those involving flag algebras, graph homomorphisms, and graphons–we investigate the extremal and asymptotic theory of pattern containment and avoidance in words. Word V is a factor of word W provided V occurs as consecutive letters …

    south-carolina Repository record for Toward the Combinatorial Limit Theory of free Words (opens in a new tab)

  17. Combinatorial aspects of spatial mixing and new conditions for pressure representation

    … lattice models. Given a locally finite countable graph G and a finite graph H, we consider Hom(G,H) the set of graph homomorphisms from G to H, and we study Gibbs measures supported on Hom(G,H). We develop some sufficient and other necessary conditions on Hom(G,H) for the existence of Gibbs …

    ubc Repository record for Combinatorial aspects of spatial mixing and new conditions for pressure representation (opens in a new tab) Download PDF for Combinatorial aspects of spatial mixing and new conditions for pressure representation (opens in a new tab)

  18. Gibbs measures and factor codes in symbolic dynamics

    … road colouring problem, with the framework of graph homomorphisms introduced by Ashley-Marcus-Tuncel. The chapter also includes several new algorithms relevant to the problem. Chapter 5 solves a symbolic dynamics problem related to zero-error coding. The main result, which generalizes Krieger’s …

    ubc Repository record for Gibbs measures and factor codes in symbolic dynamics (opens in a new tab) Download PDF for Gibbs measures and factor codes in symbolic dynamics (opens in a new tab)

  19. Composing classical and quantum relaxations of CSP and structure isomorphism

    … the quantum monad can be used to capture quantum homomorphisms and isomorphisms from quantum information. These results add to the already well-established connection between game comonads and Spoiler-Duplicator games from finite model theory.<br><br>A key focus is the exploration of distributive …

    oxford Repository record for Composing classical and quantum relaxations of CSP and structure isomorphism (opens in a new tab)

  20. Gamma-Switchable 2-Colourings of (m,n)-Mixed Graphs

    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 …

    uvic Repository record for Gamma-Switchable 2-Colourings of (m,n)-Mixed Graphs (opens in a new tab)