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 18 of 18 for “"Graph Homomorphism"”.
-
Topos-like Properties in Two Categories of Graphs and Graph-like Features in an Abstract Category
In the study of the Category of Graphs, the usual notion of a graph is that of a simple graph with at most one loop on any vertex, and the usual notion of a graph homomorphism is a mapping of graphs that sends vertices to vertices, edges to edges, and preserves incidence of the mapped vertices and …
-
Topos-like Properties in Two Categories of Graphs and Graph-like Features in an Abstract Category
In the study of the Category of Graphs, the usual notion of a graph is that of a simple graph with at most one loop on any vertex, and the usual notion of a graph homomorphism is a mapping of graphs that sends vertices to vertices, edges to edges, and preserves incidence of the mapped vertices and …
-
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 …
-
Rethinking local structural awareness in graph representation learning
Graph-structured data lies at the heart of many modern applications, from molecular modeling and materials discovery to social networks and relational databases. For these types of problems, graph representation learning has emerged as a powerful framework for reasoning. Models such as graph neural …
-
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 …
-
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 …
-
On the complexity of counting homomorphisms under surjectivity constraints
<p>Given two graphs G and H, a function h that maps the vertices of G to vertices of H is a (graph) homomorphism if h preserves the edges of G, i.e., whenever two vertices u, v of G share an edge then h(u) and h(v) must share an edge in H. For different H, such homomorphisms represent different …
-
Topics in computational complexity
… is notation and definitions. In Chapter 2 the subgraph homeomorphism problem, for fixed pattern graphs H, is considered. For the cases H and#x2245; C<sub>6</sub>,C<sub>7</sub>,W<sub>4</sub> or W<sub>5</sub>, we obtain exact characterizations of graphs with no subgraph homeomorphic from H, and …
-
Synchronous and quantum games: Graphical and algebraic methods
… an equivalence of these linear system games to graph isomorphism games on graphs parameterized by the linear system. Second, we extend nonlocal games to quantum games, in the sense that we allow the questions and answers to be quantum states of a bipartite system. We do this by quantizing the …
-
On the complexity of model checking counter automata
… which we represent separation logic formulae as graphs and decide entailment between them by checking for the existence of a graph homomorphism. We complement this result by considering various natural extensions of this fragment which make entailment coNP-hard. </p>
-
Graph-dependent Covering Arrays and LYM Inequalities
… extremal set theory, design theory, and graph theory. We define and study several generalizations of covering arrays, and we develop a method which produces an infinite family of LYM inequalities for graph-intersecting collections. A common theme throughout is the dependence of these …
-
Homomorphisms of (j, k)-mixed graphs
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 …
-
The complexity of digraph homomorphisms: Local tournaments, injective homomorphisms and polymorphisms
… the computational complexity of certain digraph homomorphism problems. A homomorphism between digraphs, denoted by $f: G \to H$, is a mapping from the vertices of $G$ to the vertices of $H$ such that the arcs of $G$ are preserved. The problem of deciding whether a homomorphism to a fixed …
-
Randomised algorithms for low temperature spin systems
… a general framework in which the vertices of a graph are assigned spins from a finite set. The local interactions between neighbouring spins give rise to a global weight, which describes the probability that the system is in the given configuration. Spin systems provide a framework for sampling …
-
On the Attainability of Upper Bounds for the Circular Chromatic Number of <em>K</em><sub>4</sub>-Minor-Free Graphs.
Let G be a graph. For k ≥ d ≥ 1, a k/d -coloring of G is a coloring c of vertices of G with colors 0, 1, 2, . . ., k - 1, such that d ≤ | c(x) - c(y) | ≤ k - d, whenever xy is an edge of G. We say that the circular chromatic number of G, denoted χc(G), is equal to the smallest k/d where a k/d …
-
Reflexive injective oriented colourings
… on the neighbourhoods of the underlying graph, without requiring the colouring to be proper. An analysis of the complexity of the problem of deciding whether an oriented graph has a k-rio-colouring is considered, and we find a dichotomy for the values of k below 3 and above, being in P or …
-
D-colorable digraphs with large girth
<p>In 1959 Paul Erdos (<italic>Graph theory and probability</italic>, Canad. J. Math. <bold>11</bold> (1959), 34-38) famously proved, nonconstructively, that there exist graphs that have both arbitrarily large girth and arbitrarily large chromatic number. This result, along with its proof, has had …
-
D-colorable digraphs with large girth
<p>In 1959 Paul Erdos (<italic>Graph theory and probability</italic>, Canad. J. Math. <bold>11</bold> (1959), 34-38) famously proved, nonconstructively, that there exist graphs that have both arbitrarily large girth and arbitrarily large chromatic number. This result, along with its proof, has had …