Closure for spanning trees and distant area

Jun Fujisawa; Akira Saito; Ingo Schiermeyer

Displaying similar documents to “Closure for spanning trees and distant area”

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...

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...

On locating and differentiating-total domination in trees

Mustapha Chellali (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $γ ₜ^{L} (G)$ and $γ ₜ^{D} (G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total...

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 ₙ$ .

On operators from separable reflexive spaces with asymptotic structure

Bentuo Zheng (2008)

Studia Mathematica

Similarity:

Let 1 < q < p < ∞ and q ≤ r ≤ p. Let X be a reflexive Banach space satisfying a lower- $ℓ_{q}$ -tree estimate and let T be a bounded linear operator from X which satisfies an upper- $ℓ_{p}$ -tree estimate. Then T factors through a subspace of ${(\sum F ₙ)}_{ℓ_{r}}$ , where (Fₙ) is a sequence of finite-dimensional spaces. In particular, T factors through a subspace of a reflexive space with an $(ℓ_{p}, ℓ_{q})$ FDD. Similarly, let 1 < q < r < p < ∞ and let X be a separable reflexive Banach space satisfying an asymptotic...

Turán's problem and Ramsey numbers for trees

Zhi-Hong Sun, Lin-Lin Wang, Yi-Li Wu (2015)

Colloquium Mathematicae

Similarity:

Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with $V = v ₀, v ₁, . . ., v_{n - 1}$ , $E ₁ = v ₀ v ₁, . . ., v ₀ v_{n - 3}, v_{n - 4} v_{n - 2}, v_{n - 3} v_{n - 1}$ and $E ₂ = v ₀ v ₁, . . ., v ₀ v_{n - 3}, v_{n - 3} v_{n - 2}, v_{n - 3} v_{n - 1}$ . For p ≥ n ≥ 5 we obtain explicit formulas for ex(p;T¹ₙ) and ex(p;T²ₙ), where ex(p;L) denotes the maximal number of edges in a graph of order p not containing L as a subgraph. Let r(G₁,G₂) be the Ramsey number of the two graphs G₁ and G₂. We also obtain some explicit formulas for $r (T ₘ, T ₙ^{i})$ , where i ∈ 1,2 and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.

The tree property at both $ℵ_{ω + 1}$ and $ℵ_{ω + 2}$

Laura Fontanella, Sy David Friedman (2015)

Fundamenta Mathematicae

Similarity:

We force from large cardinals a model of ZFC in which $ℵ_{ω + 1}$ and $ℵ_{ω + 2}$ both have the tree property. We also prove that if we strengthen the large cardinal assumptions, then in the final model $ℵ_{ω + 2}$ even satisfies the super tree property.

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.

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...

On operators which factor through $l_{p}$ or c₀

Bentuo Zheng (2006)

Studia Mathematica

Similarity:

Let 1 < p < ∞. Let X be a subspace of a space Z with a shrinking F.D.D. (Eₙ) which satisfies a block lower-p estimate. Then any bounded linear operator T from X which satisfies an upper-(C,p)-tree estimate factors through a subspace of ${(\sum F ₙ)}_{l_{p}}$ , where (Fₙ) is a blocking of (Eₙ). In particular, we prove that an operator from $L_{p}$ (2 < p < ∞) satisfies an upper-(C,p)-tree estimate if and only if it factors through $l_{p}$ . This gives an answer to a question of W. B. Johnson. We also prove...

Trees and the dynamics of polynomials

Laura G. DeMarco, Curtis T. McMullen (2008)

Annales scientifiques de l'École Normale Supérieure

Similarity:

In this paper we study branched coverings of metrized, simplicial trees $F : T \to T$ which arise from polynomial maps $f : ℂ \to ℂ$ with disconnected Julia sets. We show that the collection of all such trees, up to scale, forms a contractible space $ℙ T_{D}$ compactifying the moduli space of polynomials of degree $D$ ; that $F$ records the asymptotic behavior of the multipliers of $f$ ; and that any meromorphic family of polynomials over $Δ^{*}$ can be completed by a unique tree at its central fiber. In the cubic case we give a...

The instability of nonseparable complete Erdős spaces and representations in ℝ-trees

Jan J. Dijkstra, Kirsten I. S. Valkenburg (2010)

Fundamenta Mathematicae

Similarity:

One way to generalize complete Erdős space $_{c}$ is to consider uncountable products of zero-dimensional $G_{δ}$ -subsets of the real line, intersected with an appropriate Banach space. The resulting (nonseparable) complete Erdős spaces can be fully classified by only two cardinal invariants, as done in an earlier paper of the authors together with J. van Mill. As we think this is the correct way to generalize the concept of complete Erdős space to a nonseparable setting, natural questions arise...

On a characterization of $k$ -trees

De-Yan Zeng, Jian Hua Yin (2015)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a $k$ -tree if either $G$ is the complete graph on $k + 1$ vertices, or $G$ has a vertex $v$ whose neighborhood is a clique of order $k$ and the graph obtained by removing $v$ from $G$ is also a $k$ -tree. Clearly, a $k$ -tree has at least $k + 1$ vertices, and $G$ is a 1-tree (usual tree) if and only if it is a $1$ -connected graph and has no $K_{3}$ -minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of $k$ -trees as follows: if $G$ is a graph with at least $k + 1$ vertices, then $G$ is...

Bounds On The Disjunctive Total Domination Number Of A Tree

Michael A. Henning, Viroshan Naicker (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, [...] γtd(G) $γ_{t}^{d} (G)$ , is the minimum cardinality of such a set. We observe that [...] γtd(G)≤γt(G)...