On degrees of vertices in paradoxical trees
type: Item
instance of: scholarly article
title: On degrees of vertices in paradoxical trees
zbMATH Open document ID: 0940.05022
DOI: 10.1016/S0012-365X(99)00208-3
published in: Discrete Mathematics
publication date: 2000-06-07T00:00:00Z
review text: The paper gives necessary and sufficient conditions for an infinite tree to be paradoxical. A tree \(T=(V,E)\) is paradoxical if it admits a partition \(V = V_1 \cup V_2\) such that \(V\), \(V_1\) and \(V_2\) are pairwise equivalent (two sets \(A, B\) are equivalent if there is a bijection \(f : A \to B\)). More precisely, the paper gives inequalities involving the total degree of subgraphs induced by the bounded neighborhoods of any finite subset \(M\), i.e. the sets of nodes at distance at most \(d\) from \(M\). The first set of conditions (Theorem 1) indicates that this sum should be somewhat bigger than the total degree of nodes in \(M\) for the tree to be paradoxical (`somewhat' meaning that we alter the sums by subtracting the total number of nodes in the neightborhood under consideration). The second set of conditions (Theorem 2) expresses the importance of nodes of degree 2 in the tree, and states similar inequalities obtained by restricting the previous sums to nodes of degree 2. The paper builds on previous results by \textit{W. A. Deuber, M. Simonovits} and \textit{V. T. Sós} [Stud. Sci. Math. Hung. 30, No. 1-2, 17-23 (1995; Zbl 0857.54030)] adding to the characterization of paradoxical trees already given in \textit{D. Fon-Der-Flaass} [On exponential trees, Eur. J. Comb. 19, No. 1, 25-27 (1998; Zbl 0897.05023)]. It contains a list of technical lemmas dealing with various inequalities on degree, number of edges and cardinality of locally finite trees, thus providing potentially useful tools for the theory.
reviewed by: G. Melançon
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1420213
zbMATH Keywords: infinite trees
zbMATH Keywords: paradoxical trees
zbMATH Keywords: wobbling bijections
zbMATH Keywords: discrete metric space
author: Walter A. Deuber
author: Alexandr Kostochka
MaRDI profile type: MaRDI publication profile
Wikidata QID: Q127629396
full work available at URL: s0012-365x(99)00208-3
OpenAlex ID: W2062191306
Recommended article: A decomposition of locally finite graphs
Recommended article: On tree-partitions of graphs
Recommended article: Infinite paths in locally finite graphs and in their spanning trees
Recommended article: On exponential trees
Recommended article: Q3792711
Recommended article: On induced subgraphs of trees, with restricted degrees
Recommended article: Neighbourhood-width of trees
Recommended article: Q3972100
Recommended article: Counting all parity realizable trees
Recommended article: Every tree contains a large induced subgraph with all degrees odd
description: scientific article; zbMATH DE number 1420213