Bounded graphs (Q1191915): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(91)90331-u / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2912546343 / rank | |||
Normal rank |
Latest revision as of 10:36, 30 July 2024
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