Quasi-bounded trees and analytic inductions

Jean Saint Raymond

Displaying similar documents to “Quasi-bounded trees and analytic inductions”

Closure for spanning trees and distant area

Jun Fujisawa, Akira Saito, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with $d e g_{G} u + d e g_{G} v \geq n - 1$ , G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on $d e g_{G} u + d e g_{G} v$ and the structure of the distant area for u and v. We prove...

Pruning Galton–Watson trees and tree-valued Markov processes

Romain Abraham, Jean-François Delmas, Hui He (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We present a new pruning procedure on discrete trees by adding marks on the nodes of trees. This procedure allows us to construct and study a tree-valued Markov process ${𝒢 (u)}$ by pruning Galton–Watson trees and an analogous process ${𝒢^{*} (u)}$ by pruning a critical or subcritical Galton–Watson tree conditioned to be infinite. Under a mild condition on offspring distributions, we show that the process ${𝒢 (u)}$ run until its ascension time has a representation in terms of ${𝒢^{*} (u)}$ . A similar result was obtained by...

On the (2,2)-domination number of trees

You Lu, Xinmin Hou, Jun-Ming Xu (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let γ(G) and $γ_{2, 2} (G)$ denote the domination number and (2,2)-domination number of a graph G, respectively. In this paper, for any nontrivial tree T, we show that $(2 (γ (T) + 1)) / 3 \leq γ_{2, 2} (T) \leq 2 γ (T)$ . Moreover, we characterize all the trees achieving the equalities.

A note on the cubical dimension of new classes of binary trees

Kamal Kabyl, Abdelhafid Berrachedi, Éric Sopena (2015)

Czechoslovak Mathematical Journal

Similarity:

The cubical dimension of a graph $G$ is the smallest dimension of a hypercube into which $G$ is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with $2^{n}$ vertices, $n \geq 1$ , is $n$ . The 2-rooted complete binary tree of depth $n$ is obtained from two copies of the complete binary tree of depth $n$ by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice...

A partition of the Catalan numbers and enumeration of genealogical trees

Rainer Schimming (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A special relational structure, called genealogical tree, is introduced; its social interpretation and geometrical realizations are discussed. The numbers $C_{n, k}$ of all abstract genealogical trees with exactly n+1 nodes and k leaves is found by means of enumeration of code words. For each n, the $C_{n, k}$ form a partition of the n-th Catalan numer Cₙ, that means $C_{n, 1} + C_{n, 2} + . . . + C_{n, n} = C ₙ$ .

Trees with α-labelings and decompositions of complete graphs into non-symmetric isomorphic spanning trees

Michael Kubesa (2005)

Discussiones Mathematicae Graph Theory

Similarity:

We examine constructions of non-symmetric trees with a flexible q-labeling or an α-like labeling, which allow factorization of $K_{2 n}$ into spanning trees, arising from the trees with α-labelings.

Note about sequences of extrema $(A, 2 B)$ -edge coloured trees

Urszula Bednarz, Iwona Włoch (2017)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

In this paper we determine successive extremal trees with respect to the number of all $(A, 2 B)$ -edge colourings.

Spanning caterpillars with bounded diameter

Ralph Faudree, Ronald Gould, Michael Jacobson, Linda Lesniak (1995)

Discussiones Mathematicae Graph Theory

Similarity:

A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most $c n^{3 / 4}$ (at most n).

Compactness properties of weighted summation operators on trees

Mikhail Lifshits, Werner Linde (2011)

Studia Mathematica

Similarity:

We investigate compactness properties of weighted summation operators $V_{α, σ}$ as mappings from ℓ₁(T) into $ℓ_{q} (T)$ for some q ∈ (1,∞). Those operators are defined by $(V_{α, σ} x) (t) : = α (t) \sum_{s ⪰ t} σ (s) x (s)$ , t ∈ T, where T is a tree with partial order ⪯. Here α and σ are given weights on T. We introduce a metric d on T such that compactness properties of (T,d) imply two-sided estimates for $e ₙ (V_{α, σ})$ , the (dyadic) entropy numbers of $V_{α, σ}$ . The results are applied to concrete trees, e.g. moderately increasing, biased or binary trees and to weights...

Signpost systems and spanning trees of graphs

Ladislav Nebeský (2006)

Czechoslovak Mathematical Journal

Similarity:

By a ternary system we mean an ordered pair $(W, R)$ , where $W$ is a finite nonempty set and $R \subseteq W \times W \times W$ . By a signpost system we mean a ternary system $(W, R)$ satisfying the following conditions for all $x, y, z \in W$ : if $(x, y, z) \in R$ , then $(y, x, x) \in R$ and $(y, x, z) \notin R$ ; if $x \neq y$ , then there exists $t \in W$ such that $(x, t, y) \in R$ . In this paper, a signpost system is used as a common description of a connected graph and a spanning tree of the graph. By a ct-pair we mean an ordered pair $(G, T)$ , where $G$ is a connected graph and $T$ is a spanning tree of $G$ . If $(G, T)$ is a ct-pair, then by...

Fine and quasi connectedness in nonlinear potential theory

David R. Adams, John L. Lewis (1985)

Annales de l'institut Fourier

Similarity:

If $B_{α, p}$ denotes the Bessel capacity of subsets of Euclidean $n$ -space, $α > 0$ , $1 < p < \infty$ , naturally associated with the space of Bessel potentials of $L^{p}$ -functions, then our principal result is the estimate: for $1 < α p \leq n$ , there is a constant $C = C (α, p, n)$ such that for any set $E$ $min {B_{α, p} (E \cap Q), B_{α, p} (E^{c} \cap Q)} \leq C \cdot B_{α, p} (Q \cap \partial_{f} E)$ for all open cubes $Q$ in $n$ -space. Here $\partial_{f} E$ is the boundary of the $E$ in the $(α, p)$ -fine topology i.e. the smallest topology on $c$ -space that makes the associated $(α, p)$ -linear potentials continuous there. As a consequence,...

Proper translation

Heike Mildenberger, Saharon Shelah (2011)

Fundamenta Mathematicae

Similarity:

We continue our work on weak diamonds [J. Appl. Anal. 15 (1009)]. We show that $2^{ω} = ℵ ₂$ together with the weak diamond for covering by thin trees, the weak diamond for covering by meagre sets, the weak diamond for covering by null sets, and “all Aronszajn trees are special” is consistent relative to ZFC. We iterate alternately forcings specialising Aronszajn trees without adding reals (the NNR forcing from [“Proper and Improper Forcing”, Ch. V]) and < ω₁-proper $^{ω} ω$ -bounding forcings adding...

Quasi-algebraic representability of sets in $R^{n}$ .

W. Waliszewski (1984)

Banach Center Publications

Similarity:

The analytic $α$ -capacity and the Cauchy integral

K. Adžievski (1986)

Matematički Vesnik

Similarity: