Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUbiquity in graphs II: Ubiquity of graphs with nowhere-linear end structure
97
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph $G$ is said to be $preceq$-ubiquitous, where $preceq$ is the minor relation between graphs, if whenever $Gamma$ is a graph with $nG preceq Gamma$ for all $n in mathbb{N}$, then one also has $aleph_0 G preceq Gamma$, where $alpha G$ is the disjoint union of $alpha$ many copies of $G$. A well-known conjecture of Andreae is that every locally finite connected graph is $preceq$-ubiquitous. In this paper we give a sufficient condition on the structure of the ends of a graph~$G$ which implies that $G$ is $preceq$-ubiquitous. In particular this implies that the full grid is $preceq$-ubiquitous.
rate research
Read More
Let $triangleleft$ be a relation between graphs. We say a graph $G$ is emph{$triangleleft$-ubiquitous} if whenever $Gamma$ is a graph with $nG triangleleft Gamma$ for all $n in mathbb{N}$, then one also has $aleph_0 G triangleleft Gamma$, where $alpha G$ is the disjoint union of $alpha$ many copies of $G$. The emph{Ubiquity Conjecture} of Andreae, a well-known open problem in the theory of infinite graphs, asserts that every locally finite connected graph is ubiquitous with respect to the minor relation. In this paper, which is the first of a series of papers making progress towards the Ubiquity Conjecture, we show that all trees are ubiquitous with respect to the topological minor relation, irrespective of their cardinality. This answers a question of Andreae from 1979.
A graph $G$ is said to be ubiquitous, if every graph $Gamma$ that contains arbitrarily many disjoint $G$-minors automatically contains infinitely many disjoint $G$-minors. The well-known Ubiquity conjecture of Andreae says that every locally finite graph is ubiquitous. In this paper we show that locally finite graphs admitting a certain type of tree-decomposition, which we call an extensive tree-decomposition, are ubiquitous. In particular this includes all locally finite graphs of finite tree-width, and also all locally finite graphs with finitely many ends, all of which have finite degree. It remains an open question whether every locally finite graph admits an extensive tree-decomposition.
We investigate the textit{group irregularity strength}, $s_g(G)$, of a graph, i.e. the least integer $k$ such that taking any Abelian group $mathcal{G}$ of order $k$, there exists a function $f:E(G)rightarrow mathcal{G}$ so that the sums of edge labels incident with every vertex are distinct. So far the best upper bound on $s_g(G)$ for a general graph $G$ was exponential in $n-c$, where $n$ is the order of $G$ and $c$ denotes the number of its components. In this note we prove that $s_g(G)$ is linear in $n$, namely not greater than $2n$. In fact, we prove a stronger result, as we additionally forbid the identity element of a group to be an edge label or the sum of labels around a vertex. We consider also locally irregular labelings where we require only sums of adjacent vertices to be distinct. For the corresponding graph invariant we prove the general upper bound: $Delta(G)+{rm col}(G)-1$ (where ${rm col}(G)$ is the coloring number of $G$) in the case when we do not use the identity element as an edge label, and a slightly worse one if we additionally forbid it as the sum of labels around a vertex. In the both cases we also provide a sharp upper bound for trees and a constant upper bound for the family of planar graphs.
Let $k,l,m,n$, and $mu$ be positive integers. A $mathbb{Z}_mu$--{it scheme of valency} $(k,l)$ and {it order} $(m,n)$ is a $m times n$ array $(S_{ij})$ of subsets $S_{ij} subseteq mathbb{Z}_mu$ such that for each row and column one has $sum_{j=1}^n |S_{ij}| = k $ and $sum_{i=1}^m |S_{ij}| = l$, respectively. Any such scheme is an algebraic equivalent of a $(k,l)$-semi-regular bipartite voltage graph with $n$ and $m$ vertices in the bipartition sets and voltages coming from the cyclic group $mathbb{Z}_mu$. We are interested in the subclass of $mathbb{Z}_mu$--schemes that are characterized by the property $a - b + c - d; ot equiv ;0$ (mod $mu$) for all $a in S_{ij}$, $b in S_{ih}$, $c in S_{gh}$, and $d in S_{gj}$ where $i,g in {1,...,m}$ and $j,h in {1,...,n}$ need not be distinct. These $mathbb{Z}_mu$--schemes can be used to represent adjacency matrices of regular graphs of girth $ge 5$ and semi-regular bipartite graphs of girth $ge 6$. For suitable $rho, sigma in mathbb{N}$ with $rho k = sigma l$, they also represent incidence matrices for polycyclic $(rho mu_k, sigma mu_l)$ configurations and, in particular, for all known Desarguesian elliptic semiplanes. Partial projective closures yield {it mixed $mathbb{Z}_mu$-schemes}, which allow new constructions for Krv{c}adinacs sporadic configuration of type $(34_6)$ and Balbuenas bipartite $(q-1)$-regular graphs of girth 6 on as few as $2(q^2-q-2)$ vertices, with $q$ ranging over prime powers. Besides some new results, this survey essentially furnishes new proofs in terms of (mixed) $mathbb{Z}_mu$--schemes for ad-hoc constructions used thus far.
A textit{linear $3$-graph}, $H = (V, E)$, is a set, $V$, of vertices together with a set, $E$, of $3$-element subsets of $V$, called edges, so that any two distinct edges intersect in at most one vertex. The linear Turan number, ${rm ex}(n,F)$, is the maximum number of edges in a linear $3$-graph $H$ with $n$ vertices containing no copy of $F$. We focus here on the textit{crown}, $C$, which consists of three pairwise disjoint edges (jewels) and a fourth edge (base) which intersects all of the jewels. Our main result is that every linear $3$-graph with minimum degree at least $4$ contains a crown. This is not true if $4$ is replaced by $3$. In fact the known bounds of the Turan number are [ 6 leftlfloor{frac{n - 3}{4}}rightrfloor leq {rm ex}(n, C) leq 2n, ] and in the construction providing the lower bound all but three vertices have degree $3$. We conjecture that ${rm ex}(n, C) sim frac{3n}{2}$ but even if this were known it would not imply our main result. Our second result is a step towards a possible proof of ${rm ex}(n,C) leq frac{3n}{2}$ (i.e., determining it within a constant error). We show that a minimal counterexample to this statement must contain certain configurations with $9$ edges and we conjecture that all of them lead to contradiction.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
