Bounded graphs (Q1191915)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounded graphs |
scientific article |
Statements
Bounded graphs (English)
0 references
27 September 1992
0 references
Let \((a_ i)_{i\in\mathbb{N}}\) and \((b_ i)_{i\in\mathbb{N}}\) be sequences of natural numbers. The sequence \((b_ i)\) is said to majorize the sequence \((a_ i)\) if there is an \(n_ 0\) such that \(b_ i>a_ i\) for all \(i\geq n_ 0\). Let \(G\) be an (infinite) graph. A ray \(U=(u_ 0,u_ 1,\dots)\) is a one-way infinite path in \(G\). Let \(f:V(G)\to\mathbb{N}\) be a function and \(b=(b_ i)_{i\in\mathbb{N}}\) a sequence of natural numbers. Then \(b\) is said to majorize \(f\) on \(U\) if \(b\) majorizes \(f(u_ 0)\), \(f(u_ 1),\dots\). Furthermore \(b\) is said to ray-majorize \(f\) (with respect to \(G\) or on \(G)\) if \(b\) majorizes \(f\) on every ray of \(G\). A graph \(G\) is bounded if for every function \(f:V(G)\to\mathbb{N}\) there is a sequence of natural numbers which ray-majorizes \(f\) on \(G\). The author conjectures (under the assumption of the Continuum Hypothesis) which graphs are bounded and proves the conjecture for several classes of graphs.
0 references
bounded graphs
0 references
sequences
0 references
majorize
0 references
ray-majorize
0 references