For a connected graph $G=(V,E)$ and a set $S\subseteq V\left(G\right)$ with at least two vertices, an $S$-Steiner tree is a subgraph $T=(V^{\text{'}},E^{\text{'}})$ of $G$ that is a tree with $S\subseteq V^{\text{'}}$. 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\left(G\right)$ and $\left|S\right|\ge 2$, the pendant tree-connectivity ${\tau }_G\left(S\right)$ is the maximum number of internally disjoint pendant $S$-Steiner trees in $G$, and for $k\ge 2$, the $k$-pendant tree-connectivity ${\tau }_k\left(G\right)$ is the...

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)=\lceil 2(n-1)/d\rceil$ 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.

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 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, ${\Lambda }^d$. In this paper we find an algorithm to construct “visible trees” from symbolic sequences which works whether or not the sequence...

The Sombor index $SO\left(G\right)$ of a graph $G$ is the sum of the edge weights $\sqrt{d_G^2\left(u\right)+d_G^2\left(v\right)}$ of all edges $uv$ of $G$, where $d_G\left(u\right)$ 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\left(G\right)$ 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\left(u\right)=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.

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\left(T\right)$ and the set of branch vertices of $T$ is denoted by $B\left(T\right)$. 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\left(T\right)\ne \varnothing$. For each leaf $x$ of $T$, let $y_x$ denote the nearest branch vertex to $x$. We delete $V\left(P_T[x,y_x]\right)\setminus \left\{y_x\right\}$ from $T$ for all $x\in L\left(T\right)$. The resulting subtree of $T$ is called the reducible stem...

For n ∈ ℕ, L > 0, and p ≥ 1 let ${\kappa }_p(n,L)$ be the largest possible value of k for which there is a polynomial P ≠ 0 of the form $P\left(x\right)={\sum }_{j=0}^n{a}_j{x}^j$, $|a_0\left|\ge L\right({\sum }_{j=1}^n|a_j{|}^p$1/p$,$aj ∈ ℂ$,$such that ${(x-1)}^k$ divides P(x). For n ∈ ℕ and L > 0 let ${\kappa }_{\infty }(n,L)$ be the largest possible value of k for which there is a polynomial P ≠ 0 of the form $P\left(x\right)={\sum }_{j=0}^n{a}_j{x}^j$, $|a_0|\ge Lma{x}_{1\le j\le n}|a_j|$, $a_j\in ℂ$, such that ${(x-1)}^k$ divides P(x). We prove that there are absolute constants c₁ > 0 and c₂ > 0 such that $c_1\surd (n/L)-1\le {\kappa }_{\infty }(n,L)\le c_2\surd (n/L)$ for every L ≥ 1. This complements an earlier result of the authors valid for every n ∈ ℕ and L ∈...

The paper deals with the approximation by polynomials with integer coefficients in $L_p(0,1)$, 1 ≤ p ≤ ∞. Let $P_{n,r}$ be the space of polynomials of degree ≤ n which are divisible by the polynomial $x^r{(1-x)}^r$, r ≥ 0, and let $P_{n,r}^{\mathbb{Z}}\subset P_{n,r}$ be the set of polynomials with integer coefficients. Let $\mu (P_{n,r}^{\mathbb{Z}};L_p)$ be the maximal distance of elements of $P_{n,r}$ from $P_{n,r}^{\mathbb{Z}}$ in $L_p(0,1)$. We give rather precise quantitative estimates of $\mu (P_{n,r}^{\mathbb{Z}};L₂)$ for n ≳ 6r. Then we obtain similar, somewhat less precise, estimates of $\mu (P_{n,r}^{\mathbb{Z}};L_p)$ for p ≠ 2. It follows that $\mu (P_{n,r}^{\mathbb{Z}};L_p)\asymp n^{-2r-2/p}$ as n → ∞. The results...

Let D and ∂D denote the open unit disk and the unit circle of the complex plane, respectively. We denote by ₙ (resp. ${ₙ}^c$) the set of all polynomials of degree at most n with real (resp. complex) coefficients. We define the truncation operators Sₙ for polynomials $Pₙ\in {ₙ}^c$ of the form $Pₙ\left(z\right):={\sum }_{j=0}^n{a}_j{z}_j$, $a_j\in C$, by $Sₙ\left(Pₙ\right)\left(z\right):={\sum }_{j=0}^{n}a{̃}_j{z}_j$, $a{̃}_j:=a_j\left|a_j\right|min|a_j|,1$ (here 0/0 is interpreted as 1). We define the norms of the truncation operators by $\parallel Sₙ{\parallel }_{\infty ,\partial D}^{real}:=su{p}_{Pₙ\in ₙ}(ma{x}_{z\in \partial D}\left|Sₙ\left(Pₙ\right)\left(z\right)\right|)/(ma{x}_{z\in \partial D}\left|Pₙ\left(z\right)\right|)$, $\parallel Sₙ{\parallel }_{\infty ,\partial D}^{comp}:=su{p}_{Pₙ\in {ₙ}^c}(ma{x}_{z\in \partial D}\left|Sₙ\left(Pₙ\right)\left(z\right)\right|)/(ma{x}_{z\in \partial D}\left|Pₙ\left(z\right)\right|$. Our main theorem establishes the right order of magnitude of the above norms: there is an absolute constant c₁...

A proper coloring $c:V\left(G\right)\to \{1,2,...,k\}$, $k\ge 2$ of a graph $G$ is called a graceful $k$-coloring if the induced edge coloring $c^{\text{'}}:E\left(G\right)\to \{1,2,...,k-1\}$ defined by $c^{\text{'}}\left(uv\right)=|c\left(u\right)-c\left(v\right)|$ for each edge $uv$ of $G$ is also proper. The minimum integer $k$ for which $G$ has a graceful $k$-coloring is the graceful chromatic number ${\chi }_g\left(G\right)$. It is known that if $T$ is a tree with maximum degree $\Delta$, then ${\chi }_g\left(T\right)\le \lceil \frac{5}{3}\Delta \rceil$ and this bound is best possible. It is shown for each integer $\Delta \ge 2$ that there is an infinite class of trees $T$ with maximum degree $\Delta$ such that ${\chi }_g\left(T\right)=\lceil \frac{5}{3}\Delta \rceil$. In particular, we investigate for each...

For n ∈ ℕ, L > 0, and p ≥ 1 let ${\kappa }_p(n,L)$ be the largest possible value of k for which there is a polynomial P ≢ 0 of the form $P\left(x\right)={\sum }_{j=0}^n{a}_j{x}^j$, $|a_0\left|\ge L\right({\sum }_{j=1}^n|a_j{{|}^p)}^{1/p}$, $a_j\in ℂ$, such that ${(x-1)}^k$ divides P(x). For n ∈ ℕ, L > 0, and q ≥ 1 let ${\mu }_q(n,L)$ be the smallest value of k for which there is a polynomial Q of degree k with complex coefficients such that $\left|Q\left(0\right)\right|>1/L({\sum }_{j=1}^n{\left|Q\left(j\right)\right|}^q{)}^{1/q}$. We find the size of ${\kappa }_p(n,L)$ and ${\mu }_q(n,L)$ for all n ∈ ℕ, L > 0, and 1 ≤ p,q ≤ ∞. The result about ${\mu }_{\infty }(n,L)$ is due to Coppersmith and Rivlin, but our proof is completely different and much shorter even...

Let $\parallel ·\parallel$ be the uniform norm in the unit disk. We study the quantities $M_n\left(\alpha \right):=inf(\parallel zP\left(z\right)+\alpha \parallel -\alpha )$ where the infimum is taken over all polynomials $P$ of degree $n-1$ with $\parallel P\left(z\right)\parallel =1$ and $\alpha >0$. In a recent paper by Fournier, Letac and Ruscheweyh (Math. Nachrichten 283 (2010), 193-199) it was shown that ${inf}_{\alpha >0}{M}_n\left(\alpha \right)=1/n$. We find the exact values of $M_n\left(\alpha \right)$ and determine corresponding extremal polynomials. The method applied uses known cases of maximal ranges of polynomials.

Let K be any subset of ${ℂ}^N$. We define a pluricomplex Green’s function $V_{K,\theta }$ for θ-incomplete polynomials. We establish properties of $V_{K,\theta }$ analogous to those of the weighted pluricomplex Green’s function. When K is a regular compact subset of ${ℝ}^N$, we show that every continuous function that can be approximated uniformly on K by θ-incomplete polynomials, must vanish on $K\setminus supp{\left(d{d}^c{V}_{K,\theta }\right)}^N$. We prove a version of Siciak’s theorem and a comparison theorem for θ-incomplete polynomials. We compute $supp{\left(d{d}^c{V}_{K,\theta }\right)}^N$ when K is a compact...

Let $V$ be the complex vector space of homogeneous linear polynomials in the variables $x_1,...,x_m$. Suppose $G$ is a subgroup of $S_m$, and $\chi$ is an irreducible character of $G$. Let $H_d(G,\chi )$ be the symmetry class of polynomials of degree $d$ with respect to $G$ and $\chi$. For any linear operator $T$ acting on $V$, there is a (unique) induced operator $K_{\chi }\left(T\right)\in \mathrm{End}\left(H_d(G,\chi )\right)$ acting on symmetrized decomposable polynomials by $$K_{\chi }\left(T\right)(f_1*f_2*...*f_d)=T{f}_1*T{f}_2*...*T{f}_d.$$ In this paper, we show that the representation $T\mapsto K_{\chi }\left(T\right)$ of the general linear group $GL\left(V\right)$ is equivalent to the direct sum of $\chi \left(1\right)$ copies...

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

We obtain an estimate on the average cardinality (d,s,a) of the value set of any family of monic polynomials in ${}_q\left[T\right]$ of degree d for which s consecutive coefficients $a=(a_{d-1},...,a_{d-s})$ are fixed. Our estimate asserts that $(d,s,a)={\mu }_{d}q+\left(q^{1/2}\right)$, where ${\mu }_d:={\sum }_{r=1}^d\left({(-1)}^{r-1}\right)/(r!)$. We also prove that $₂(d,s,a)=\mu {²}_{d}q²+\left(q^{3/2}\right)$, where ₂(d,s,a) is the average second moment of the value set cardinalities for any family of monic polynomials of ${}_q\left[T\right]$ of degree d with s consecutive coefficients fixed as above. Finally, we show that $₂(d,0)=\mu {²}_{d}q²+\left(q\right)$, where ₂(d,0) denotes the average second moment for...