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

Kamal Kabyl; Abdelhafid Berrachedi; Éric Sopena

Displaying similar documents to “A note on the cubical dimension of new classes of binary trees”

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.

A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs

Yaping Mao, Christopher Melekian, Eddie Cheng (2023)

Czechoslovak Mathematical Journal

Similarity:

For a connected graph $G = (V, E)$ and a set $S \subseteq V (G)$ with at least two vertices, an $S$ -Steiner tree is a subgraph $T = (V^{'}, E^{'})$ of $G$ that is a tree with $S \subseteq V^{'}$ . If the degree of each vertex of $S$ in $T$ is equal to 1, then $T$ is called a pendant $S$ -Steiner tree. Two $S$ -Steiner trees are if they share no vertices other than $S$ and have no edges in common. For $S \subseteq V (G)$ and $| S | \geq 2$ , the pendant tree-connectivity $τ_{G} (S)$ is the maximum number of internally disjoint pendant $S$ -Steiner trees in $G$ , and for $k \geq 2$ , the $k$ -pendant tree-connectivity $τ_{k} (G)$ is the...

Quasi-tree graphs with the minimal Sombor indices

Yibo Li, Huiqing Liu, Ruiting Zhang (2022)

Czechoslovak Mathematical Journal

Similarity:

The Sombor index $S O (G)$ of a graph $G$ is the sum of the edge weights $\sqrt{d_{G}^{2} (u) + d_{G}^{2} (v)}$ of all edges $u v$ of $G$ , where $d_{G} (u)$ denotes the degree of the vertex $u$ in $G$ . A connected graph $G = (V, E)$ is called a quasi-tree if there exists $u \in V (G)$ such that $G - u$ is a tree. Denote $𝒬 (n, k) = {G : G$ is a quasi-tree graph of order $n$ with $G - u$ being a tree and $d_{G} (u) = k}$ . We determined the minimum and the second minimum Sombor indices of all quasi-trees in $𝒬 (n, k)$ . Furthermore, we characterized the corresponding extremal graphs, respectively.

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.

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.

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

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

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 relation between the number of leaves of a tree and its diameter

Pu Qiao, Xingzhi Zhan (2022)

Czechoslovak Mathematical Journal

Similarity:

Let $L (n, d)$ denote the minimum possible number of leaves in a tree of order $n$ and diameter $d .$ Lesniak (1975) gave the lower bound $B (n, d) = ⌈ 2 (n - 1) / d ⌉$ for $L (n, d) .$ When $d$ is even, $B (n, d) = L (n, d) .$ But when $d$ is odd, $B (n, d)$ is smaller than $L (n, d)$ in general. For example, $B (21, 3) = 14$ while $L (21, 3) = 19 .$ In this note, we determine $L (n, d)$ using new ideas. We also consider the converse problem and determine the minimum possible diameter of a tree with given order and number of leaves.

Shadow trees of Mandelbrot sets

Virpi Kauko (2003)

Fundamenta Mathematicae

Similarity:

The topology and combinatorial structure of the Mandelbrot set $ℳ^{d}$ (of degree d ≥ 2) can be studied using symbolic dynamics. Each parameter is mapped to a kneading sequence, or equivalently, an internal address; but not every such sequence is realized by a parameter in $ℳ^{d}$ . Thus the abstract Mandelbrot set is a subspace of a larger, partially ordered symbol space, $Λ^{d}$ . In this paper we find an algorithm to construct “visible trees” from symbolic sequences which works whether or not the sequence...

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

Spanning trees whose reducible stems have a few branch vertices

Pham Hoang Ha, Dang Dinh Hanh, Nguyen Thanh Loan, Ngoc Diep Pham (2021)

Czechoslovak Mathematical Journal

Similarity:

Let $T$ be a tree. Then a vertex of $T$ with degree one is a leaf of $T$ and a vertex of degree at least three is a branch vertex of $T$ . The set of leaves of $T$ is denoted by $L (T)$ and the set of branch vertices of $T$ is denoted by $B (T)$ . For two distinct vertices $u$ , $v$ of $T$ , let $P_{T} [u, v]$ denote the unique path in $T$ connecting $u$ and $v .$ Let $T$ be a tree with $B (T) \neq \emptyset$ . For each leaf $x$ of $T$ , let $y_{x}$ denote the nearest branch vertex to $x$ . We delete $V (P_{T} [x, y_{x}]) ∖ {y_{x}}$ from $T$ for all $x \in L (T)$ . The resulting subtree of $T$ is called the reducible stem...

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

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

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

Fires on trees

Jean Bertoin (2012)

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

Similarity:

We consider random dynamics on the edges of a uniform Cayley tree with $n$ vertices, in which edges are either flammable, fireproof, or burnt. Every flammable edge is replaced by a fireproof edge at unit rate, while fires start at smaller rate $n^{- α}$ on each flammable edge, then propagate through the neighboring flammable edges and are only stopped at fireproof edges. A vertex is called fireproof when all its adjacent edges are fireproof. We show that as $n \to \infty$ , the terminal density of fireproof...