Ubiquity of graphs with nowhere-linear end structure

Joshua Erde; Nathan  Bowler; Christian Elbracht; J Pascal Gollin; Karl Heuer; Max Pitz; Maximilian Teegen

doi:10.1002/jgt.22936

Ubiquity of graphs with nowhere-linear end structure

Joshua Erde, Nathan Bowler, Christian Elbracht, J Pascal Gollin^*, Karl Heuer, Max Pitz, Maximilian Teegen

^*Corresponding author for this work

Institute of Discrete Mathematics (5050)

Research output: Contribution to journal › Article › peer-review

Abstract

A graph (Formula presented.) is said to be (Formula presented.) -ubiquitous, where (Formula presented.) is the minor relation between graphs, if whenever (Formula presented.) is a graph with (Formula presented.) for all (Formula presented.), then one also has (Formula presented.), where (Formula presented.) is the disjoint union of (Formula presented.) many copies of (Formula presented.). A well-known conjecture of Andreae is that every locally finite connected graph is (Formula presented.) -ubiquitous. In this paper we give a sufficient condition on the structure of the ends of a graph (Formula presented.) which implies that (Formula presented.) is (Formula presented.) -ubiquitous. In particular this implies that the full-grid is (Formula presented.) -ubiquitous.

Original language	English
Number of pages	38
Journal	Journal of Graph Theory
Early online date	2023
DOIs	https://doi.org/10.1002/jgt.22936
Publication status	E-pub ahead of print - 2023

Keywords

graph minors
infinite graphs
ubiquity

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Geometry and Topology

Access to Document

10.1002/jgt.22936Licence: CC BY 4.0

https://arxiv.org/abs/1809.00602

Cite this

@article{7b1526f2e73a40d79a5fe90cdfacd2ec,

title = "Ubiquity of graphs with nowhere-linear end structure",

abstract = "A graph (Formula presented.) is said to be (Formula presented.) -ubiquitous, where (Formula presented.) is the minor relation between graphs, if whenever (Formula presented.) is a graph with (Formula presented.) for all (Formula presented.), then one also has (Formula presented.), where (Formula presented.) is the disjoint union of (Formula presented.) many copies of (Formula presented.). A well-known conjecture of Andreae is that every locally finite connected graph is (Formula presented.) -ubiquitous. In this paper we give a sufficient condition on the structure of the ends of a graph (Formula presented.) which implies that (Formula presented.) is (Formula presented.) -ubiquitous. In particular this implies that the full-grid is (Formula presented.) -ubiquitous.",

keywords = "graph minors, infinite graphs, ubiquity",

author = "Joshua Erde and Nathan Bowler and Christian Elbracht and Gollin, {J Pascal} and Karl Heuer and Max Pitz and Maximilian Teegen",

year = "2023",

doi = "10.1002/jgt.22936",

language = "English",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Blackwell",

}

TY - JOUR

T1 - Ubiquity of graphs with nowhere-linear end structure

AU - Erde, Joshua

AU - Bowler, Nathan

AU - Elbracht, Christian

AU - Gollin, J Pascal

AU - Heuer, Karl

AU - Pitz, Max

AU - Teegen, Maximilian

PY - 2023

Y1 - 2023

N2 - A graph (Formula presented.) is said to be (Formula presented.) -ubiquitous, where (Formula presented.) is the minor relation between graphs, if whenever (Formula presented.) is a graph with (Formula presented.) for all (Formula presented.), then one also has (Formula presented.), where (Formula presented.) is the disjoint union of (Formula presented.) many copies of (Formula presented.). A well-known conjecture of Andreae is that every locally finite connected graph is (Formula presented.) -ubiquitous. In this paper we give a sufficient condition on the structure of the ends of a graph (Formula presented.) which implies that (Formula presented.) is (Formula presented.) -ubiquitous. In particular this implies that the full-grid is (Formula presented.) -ubiquitous.

AB - A graph (Formula presented.) is said to be (Formula presented.) -ubiquitous, where (Formula presented.) is the minor relation between graphs, if whenever (Formula presented.) is a graph with (Formula presented.) for all (Formula presented.), then one also has (Formula presented.), where (Formula presented.) is the disjoint union of (Formula presented.) many copies of (Formula presented.). A well-known conjecture of Andreae is that every locally finite connected graph is (Formula presented.) -ubiquitous. In this paper we give a sufficient condition on the structure of the ends of a graph (Formula presented.) which implies that (Formula presented.) is (Formula presented.) -ubiquitous. In particular this implies that the full-grid is (Formula presented.) -ubiquitous.

KW - graph minors

KW - infinite graphs

KW - ubiquity

UR - http://www.scopus.com/inward/record.url?scp=85148523383&partnerID=8YFLogxK

U2 - 10.1002/jgt.22936

DO - 10.1002/jgt.22936

M3 - Article

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

ER -

Ubiquity of graphs with nowhere-linear end structure

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this