Search

A graph U is universal for a graph class C ∋ U , if every G ∈ C is a minor of U. We prove the existence or absence of universal graphs in several natural graph classes, including graphs component-wise embeddable into a surface, and graphs forbidding K 5 , or K 3 , 3 , or K ∞ as a minor. We prove the existence of uncountably many minor-closed classes of countable graphs that do not have a universal element. Some of our results and questions may be of interest from the finite graph perspective. In particular, one of our side-results is that every K 5 -minor-free graph is a minor of a K 5 -minor-free graph of maximum degree 22. [ABSTRACT FROM AUTHOR]

Huynh et al. recently showed that a countable graph G which contains every countable planar graph as a subgraph must contain arbitrarily large finite complete graphs as topological minors, and an infinite complete graph as a minor. We strengthen this result by showing that the same conclusion holds if G contains every countable planar graph as a topological minor. In particular, there is no countable planar graph containing every countable planar graph as a topological minor, answering a question by Diestel and Kühn. Moreover, we construct a locally finite planar graph which contains every locally finite planar graph as a topological minor. This shows that in the above result it is not enough to require that G contains every locally finite planar graph as a topological minor. [ABSTRACT FROM AUTHOR]

The class of bipartite permutation graphs enjoys many nice and important properties. In particular, this class is critically important in the study of clique‐ and rank‐width of graphs, because it is one of the minimal hereditary classes of graphs of unbounded clique‐ and rank‐width. It also contains a number of important subclasses, which are critical with respect to other parameters, such as graph lettericity or shrub‐depth, and with respect to other notions, such as well‐quasi‐ordering or complexity of algorithmic problems. In the present paper we identify critical subclasses of bipartite permutation graphs of various types. [ABSTRACT FROM AUTHOR]

We investigate the question how 'small' a graph can be, if it contains all members of a given class of locally finite graphs as subgraphs or induced subgraphs. More precisely, we give necessary and sufficient conditions for the existence of a connected, locally finite graph H containing all elements of a graph class G. These conditions imply that such a graph H exists for the class G d consisting of all graphs with maximum degree < d which raises the question whether in this case H can be chosen to have bounded maximum degree. We show that this is not the case, thereby answering a question recently posed by Huynh et al. [ABSTRACT FROM AUTHOR]

For a graph G, the density of G, denoted D(G), is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of G. For a class F of graphs, the value D (F) is the supremum of densities of graphs in F . A k-edge-colored graph is a finite, simple graph with edges labeled by numbers 1 , ... , k . A function from the vertex set of one k-edge-colored graph to another is a homomorphism if the endpoints of any edge are mapped to two different vertices connected by an edge of the same color. Given a class F of graphs, a k-edge-colored graph H (not necessarily with the underlying graph in F ) is k-universal for F when any k-edge-colored graph with the underlying graph in F admits a homomorphism to H . Such graphs are known to exist exactly for classes F of graphs with acyclic chromatic number bounded by a constant. The minimum number of vertices in a k-uniform graph for a class F is known to be Ω (k D (F)) and O (k D (F)) . In this paper we close the gap by improving the upper bound to O (k D (F)) for any rational D (F) . [ABSTRACT FROM AUTHOR]

We discover new hereditary classes of graphs that are minimal (with respect to set inclusion) of unbounded clique-width. The new examples include split permutation graphs and bichain graphs. Each of these classes is characterised by a finite list of minimal forbidden induced subgraphs. These, therefore, disprove a conjecture due to Daligault, Rao and Thomassé from 2010 claiming that all such minimal classes must be defined by infinitely many forbidden induced subgraphs. In the same paper, Daligault, Rao and Thomassé make another conjecture that every hereditary class of unbounded clique-width must contain a labelled infinite antichain. We show that the two example classes we consider here satisfy this conjecture. Indeed, they each contain a canonical labelled infinite antichain, which leads us to propose a stronger conjecture: that every hereditary class of graphs that is minimal of unbounded clique-width contains a canonical labelled infinite antichain. [ABSTRACT FROM AUTHOR]

A subgraph H of a graph G is isometric if the distances between vertices in H coincide with the distances between the corresponding vertices in G. We show that for any integer n \geqslant 1, there is a graph on 3n+O(log2 n) vertices that contains isometric copies of all n-vertex graphs. Our main tool is a new type of distance labelling scheme, whose study might be of independent interest. [ABSTRACT FROM AUTHOR]

A bowtie is a graph consisting of two triangles with one vertex identified. We show that the class of all (finite) graphs not containing a bowtie as a subgraph has a Ramsey lift (expansion). This solves one of the old problems in the area and it is the first Ramsey class with a non-trivial algebraic closure. [ABSTRACT FROM AUTHOR]

The zero-divisor graph of a finite commutative ring with unity is the graph whose vertex set is the set of zero-divisors in the ring, with a and b adjacent if a b = 0. We show that the class of zero-divisor graphs is universal, in the sense that every finite graph is isomorphic to an induced subgraph of a zero-divisor graph. This remains true for various restricted classes of rings, including boolean rings, products of fields, and local rings. But in more restricted classes, the zero-divisor graphs do not form a universal family. For example, the zero-divisor graph of a local ring whose maximal ideal is principal is a threshold graph; and every threshold graph is embeddable in the zero-divisor graph of such a ring. More generally, we give necessary and sufficient conditions on a non-local ring for which its zero-divisor graph to be a threshold graph. In addition, we show that there is a countable local ring whose zero-divisor graph embeds the Rado graph , and hence every finite or countable graph, as induced subgraph. Finally, we consider embeddings in related graphs such as the 2-dimensional dot product graph. [ABSTRACT FROM AUTHOR]

Starting from a supercompact cardinal we build a model in which 2 ℵ ω 1 = 2 ℵ ω 1 + 1 = ℵ ω 1 + 3 but there is a jointly universal family of size ℵ ω 1 + 2 of graphs on ℵ ω 1 + 1 . The same technique will work for any uncountable cardinal in place of ω 1 . [ABSTRACT FROM AUTHOR]

We describe a framework for proving consistency results about singular cardinals of arbitrary cofinality and their successors. This framework allows the construction of models in which the Singular Cardinals Hypothesis fails at a singular cardinal κ of uncountable cofinality, while κ+ enjoys various combinatorial properties. As a sample application, we prove the consistency (relative to that of ZFC plus a supercompact cardinal) of there being a strong limit singular cardinal κ of uncountable cofinality where SCH fails and such that there is a collection of size less than 2κ+ of graphs on κ+ such that any graph on κ+ embeds into one of the graphs in the collection. [ABSTRACT FROM AUTHOR]

A sum graph G is a graph with a mapping of the vertex set of G onto a set of positive integers S in such a way that two vertices of G are adjacent if and only if the sum of their labels is an element of S . In an exclusive sum graph the integers of S that are the sum of two other integers of S form a set of integers that label a collection of isolated vertices associated with the graph G . A graph bears a k-exclusive sum labelling (abbreviated k -ESL), if the set of isolated vertices is of cardinality k . In this paper, observing that the property of having a k -ESL is hereditary, we provide a characterisation of graphs that have a k -exclusive sum labelling, for any k ≥ 1 , in terms of describing a universal graph for the property. [ABSTRACT FROM AUTHOR]

Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: For given m and n with m < n, m is adjacent to n if n has a 1 in the m’th position of its binary expansion. It is well known that R is a universal graph in the set of all countable graphs (since every graph in is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of is provided. We then construct a k-degenerate graph which is universal for the induced-hereditary property of finite k-degenerate graphs. In order to attempt the corresponding problem for the property of countable graphs with colouring number at most k + 1, the notion of a property with assignment is introduced and studied. Using this notion, we are able to construct a universal graph in this graph property and investigate its attributes.

The well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal graphs in I with prescribed attributes. Then we contrast universality for and universality in induced-hereditary properties of graphs and show that the overwhelming majority of induced-hereditary properties contain no universal graphs. This is made precise by showing that there are 2(2א0 ) properties in the lattice K ≤ of induced-hereditary properties of which only at most 2א0 contain universal graphs. In a final section we discuss the outlook on future work; in particular the question of characterizing those induced-hereditary properties for which there is a universal graph in the property.

Bichain graphs form a bipartite analog of split permutation graphs, also known as split graphs of Dilworth number 2. Unlike graphs of Dilworth number 1 that enjoy many nice properties, split permutation graphs are substantially more complex. To better understand the global structure of split permutation graphs, in the present paper we study their bipartite analog. We show that bichain graphs admit a simple geometric representation and have a universal element of quadratic order, i.e. an n -universal bichain graph with n 2 vertices. The latter result improves a recent cubic construction of universal split permutation graphs. [ABSTRACT FROM AUTHOR]

Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: for given m and n with m < n, m is adjacent to n if n has a 1 in the mth position of its binary expansion. It is well known that R is a universal graph in the set $${\mathcal{I}_c}$$ of all countable graphs (since every graph in $${\mathcal{I}_c}$$ is isomorphic to an induced subgraph of R) and that it is a homogeneous graph (since every isomorphism between two finite induced subgraphs of R extends to an automorphism of R). In this paper we construct a graph U( H) which is H-universal in → H, the induced-hereditary hom-property of H-colourable graphs consisting of all (countable) graphs which have a homomorphism into a given (countable) graph H. If H is the (finite) complete graph K, then → H is the property of k-colourable graphs. The universal graph U( H) is characterised by showing that it is, up to isomorphism, the unique denumerable, H-universal graph in → H which is H-homogeneous in → H. The graphs H for which $${U(H) \cong R}$$ are also characterised. With small changes to the definitions, our results translate effortlessly to hold for digraphs too. Another slight adaptation of our work yields related results for ( k, l)-split graphs. [ABSTRACT FROM AUTHOR]

Abstract: We discuss two combinatorial problems concerning classes of finite or countable structures of combinatorial type. We consider classes determined by a finite set of finite constraints (forbidden substructures). Questions about such classes of structures are naturally viewed as algorithmic decision problems, taking the finite set of constraints as the input. While the two problems we consider have been studied in a number of natural contexts, it remains far from clear whether they are decidable in their general form. This broad question leads to a number of more concrete problems. We discuss twelve open problems of varying levels of concreteness, and we point to the “Hairy Ball Problem” as a particularly concrete problem, which we give first in direct model theoretic terms, and then decoded as an explicit graph theoretic problem. [Copyright &y& Elsevier]

In Choi (Quantum Inf Process, 7:193-209, ), we introduced the notion of minor-embedding in adiabatic quantum optimization. A minor-embedding of a graph G in a quantum hardware graph U is a subgraph of U such that G can be obtained from it by contracting edges. In this paper, we describe the intertwined adiabatic quantum architecture design problem, which is to construct a hardware graph U that satisfies all known physical constraints and, at the same time, permits an efficient minor-embedding algorithm. We illustrate an optimal complete-graph-minor hardware graph. Given a family $${\mathcal{F}}$$ of graphs, a (host) graph U is called $${\mathcal{F}}$$-minor-universal if for each graph G in $${\mathcal{F}, U}$$ contains a minor-embedding of G. The problem for designing a $${{\mathcal{F}}}$$-minor-universal hardware graph U in which $${{\mathcal{F}}}$$ consists of a family of sparse graphs (e.g., bounded degree graphs) is open. [ABSTRACT FROM AUTHOR]

A graph property is any isomorphism closed class of simple graphs. For a simple finite graph H, let → H denote the class of all simple countable graphs that admit homomorphisms to H, such classes of graphs are called hom-properties. Given a graph property P, a graph G Ȇ P is universal in P if each member of P is isomorphic to an induced subgraph of G. In particular, we consider universal graphs in→! H and we give a new proof of the existence of a universal graph in → H, for any finite graph H. [ABSTRACT FROM AUTHOR]

There exist finite universal immersion spaces for the following: (a) Edge-colored graphs of bounded degree and boundedly many colors. (b) Nearest-neighbor metrics of bounded degree and boundedly many edge lengths. [ABSTRACT FROM AUTHOR]

Abstract: We show that the problem of the existence of universal graphs with specified forbidden subgraphs can be systematically reduced to certain critical cases by a simple pruning technique which simplifies the underlying structure of the forbidden graphs, viewed as trees of blocks. As an application, we characterize the trees T for which a universal countable T-free graph exists. [Copyright &y& Elsevier]