Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

Gaps in the number of generators of monomial Togliatti systems

Let $I_{d,n}?k[x_0,?,x_n]$ be a minimal monomial Togliatti system of forms of degree d. In [4], Mezzetti and Miró-Roig proved that the minimal number of generators $\mu (I_{d,n})$ of $I_{d,n}$ lies in the interval $[2n+1,\left(\begin{array}{c}n+d?1\\ n?1\end{array}\right)]$. In this paper, we prove that for $n\ge 4$ and $d\ge 3$, the integer values in $[2n+3,3n?1]$ cannot be realized as the number of minimal generators of a minimal monomial Togliatti system. We classify minimal monomial Togliatti systems $I_{d,n}?k[x_0,?,x_n]$ of forms of degree d with $\mu (I_{d,n})=2n+2$ or 3n (i.e. with the minimal number of generators reaching the border of the non-existence interval). Finally, we prove that for $n=4$, $d\ge 3$ and $\mu \in [9,\left(\begin{array}{c}d+3\\ 3\end{array}\right)]?\{11\}$ there exists a minimal monomial Togliatti system $I_{d,n}?k[x_0,?,x_n]$ of forms of degree d with $\mu (I_{n,d})=\mu$.     

The combinatorial properties of the Benoumhani polynomials for the Whitney numbers of Dowling lattices

In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials $F_{m,n,1}\left(x\right)$ and $F_{m,n,2}\left(x\right)$. Then, he defined $A_m(n,k)$ and $B_m(n,k)$ to be the polynomials satisfying $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{A}_m(n,k)x^{n?k}{(x+1)}^k$ and $F_{m,n,1}\left(x\right)={\sum }_{k=0}^n{B}_m(n,k)x^{n?k}{(x+1)}^k$. In this paper, we give a combinatorial interpretation of the coefficients of $A_{m+1}(n,k)$ and prove a symmetry of the coefficients, i.e., $\left[m^s\right]A_{m+1}(n,k)=\left[m^{n?s}\right]A_{m+1}(n,n?k)$. We give a combinatorial interpretation of $B_{m+1}(n,k)$ and prove that $B_{m+1}(n,n?1)$ is a polynomial in $m$ with non-negative integer coefficients. We also prove that if $n\ge 6$ then all coefficients of $B_{m+1}(n,n?2)$ except the coefficient of $m^{n?1}$ are non-negative integers. For all $n$, the coefficient of $m^{n?1}$ in $B_{m+1}(n,n?2)$ is $?(n?1)$, and when $n\le 5$ some other coefficients of $B_{m+1}(n,n?2)$ are also negative.     

Bounds for the Graham–Pollak theorem for hypergraphs

Let $f_r\left(n\right)$ represent the minimum number of complete $r$-partite $r$-graphs required to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. The Graham–Pollak theorem states that $f_2\left(n\right)=n?1$. An upper bound of $(1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ was known. Recently this was improved to $\frac{14}{15}(1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ for even $r\ge 4$. A bound of $\left[\frac{r}{2}{\left(\frac{14}{15}\right)}^{\frac{r}{4}}+o\left(1\right)\right](1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ was also proved recently. Let $c_r$ be the limit of $\frac{f_r\left(n\right)}{\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)}$ as $n\to \infty$. The smallest odd $r$ for which $c_r<1$ that was known was for $r=295$. In this note we improve this to $c_{113}<1$ and also give better upper bounds for $f_r\left(n\right)$, for small values of even $r$.     

A C5-decomposition of the λ-fold line graph of the complete graph

In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of $m$ and $n$ does there exist an $m$-cycle decomposition of $L\left(K_n\right)?$ In this paper, the above question is answered for $m=5.$ In fact, it is shown that $L\left(K_n\right)\left(\lambda \right),$ the $\lambda$-fold line graph of the complete graph $K_n,$ has a $C_5$-decomposition if and only if $5\mid \lambda \left(\genfrac{}{}{0ex}{}{n}{2}\right)(n?2)$ and $n\ge 4.$     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.     

Fractional chromatic numbers of tensor products of three graphs

The tensor product $(G_1,G_2,G_3)$ of graphs $G_1$, $G_2$ and $G_3$ is defined by $V(G_1,G_2,G_3)=V\left(G_1\right)\times V\left(G_2\right)\times V\left(G_3\right)$and $E(G_1,G_2,G_3)=\left\{\left((u_1,u_2,u_3),(v_1,v_2,v_3)\right):\left|\{i:(u_i,v_i)\in E\left(G_i\right)\}\right|\ge 2\right\}.$Let ${\chi }_f\left(G\right)$ be the fractional chromatic number of a graph $G$. In this paper, we prove that if one of the three graphs $G_1$, $G_2$ and $G_3$ is a circular clique, ${\chi }_f(G_1,G_2,G_3)=min\{{\chi }_f\left(G_1\right){\chi }_f\left(G_2\right),{\chi }_f\left(G_1\right){\chi }_f\left(G_3\right),{\chi }_f\left(G_2\right){\chi }_f\left(G_3\right)\}.$     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

Stable-like fluctuations of Biggins’ martingales

Let ${\left(W_n\left(\theta \right)\right)}_{n\in {\mathbb{N}}_0}$ be Biggins’ martingale associated with a supercritical branching random walk, and let $W\left(\theta \right)$ be its almost sure limit. Under a natural condition for the offspring point process in the branching random walk, we show that if the law of $W_1\left(\theta \right)$ belongs to the domain of normal attraction of an $\alpha$-stable distribution for some $\alpha \in (1,2)$, then, as $n\to \infty$, there is weak convergence of the tail process ${(W\left(\theta \right)?W_{n?k}\left(\theta \right))}_{k\in {\mathbb{N}}_0}$, properly normalized, to a random scale multiple of a stationary autoregressive process of order one with $\alpha$-stable marginals.     

The component counts of random functions

Consider functions $f:A\to A\cup C$, where A and C are disjoint finite sets. The weakly connected components of the digraph of such a function are cycles of rooted trees, as in random mappings, and isolated rooted trees. Let $n_1=|A|$ and $n_3=|C|$. When a function is chosen from all ${(n_1+n_3)}^{n_1}$ possibilities uniformly at random, then we find the following limiting behaviour as $n_1\to \infty$. If $n_3=o(n_1)$, then the size of the maximal mapping component goes to infinity almost surely; if $n_3～\gamma n_1$, $\gamma >0$ a constant, then process counting numbers of mapping components of different sizes converges; if $n_1=o(n_3)$, then the number of mapping components converges to 0 in probability. We get estimates on the size of the largest tree component which are of order $\log ?n_3$ when $n_3～\gamma n_1$ and constant when $n_3～n_1^{\alpha }$, $\alpha >1$. These results are similar to ones obtained previously for random injections, for which the weakly connected components are cycles and linear trees.     

On invariant fields of vectors and covectors

Let ${\mathbb{F}}_q$ be the finite field of order q. Let G be one of the three groups $\mathrm{GL}(n,{\mathbb{F}}_q)$, $\mathrm{SL}(n,{\mathbb{F}}_q)$ or $\mathrm{U}(n,{\mathbb{F}}_q)$ and let W be the standard n-dimensional representation of G. For non-negative integers m and d we let $mW\oplus d{W}^{?}$ denote the representation of G given by the direct sum of m vectors and d covectors. We exhibit a minimal set of homogeneous invariant polynomials $\{{?}_1,{?}_2,\dots ,{?}_{(m+d)n}\}?{\mathbb{F}}_q{[mW\oplus d{W}^{?}]}^G$ such that ${\mathbb{F}}_q{(mW\oplus d{W}^{?})}^G={\mathbb{F}}_q({?}_1,{?}_2,\dots ,{?}_{(m+d)n})$ for all cases except when $md=0$ and $G=\mathrm{GL}(n,{\mathbb{F}}_q)$ or $\mathrm{SL}(n,{\mathbb{F}}_q)$.     

Sharp upper bounds of the spectral radius of a graph

Let $G$ be a simple connected graph with $n$ vertices and $m$ edges. The spectral radius $\rho \left(G\right)$ of $G$ is the largest eigenvalue of its adjacency matrix. In this paper, we firstly consider the effect on the spectral radius of a graph by removing a vertex, and then as an application of the result, we obtain a new sharp upper bound of $\rho \left(G\right)$ which improves some known bounds: If $\frac{(k?2)(k?3)}{2}\le m?n\le \frac{k(k?3)}{2}$, where $k(3\le k\le n)$ is an integer, then $\rho \left(G\right)\le \sqrt{2m?n?k+\frac{5}{2}+\sqrt{2m?2n+\frac{9}{4}}}.$The equality holds if and only if $G$ is a complete graph $K_n$ or $K_4?e$, where $K_4?e$ is the graph obtained from $K_4$ by deleting some edge $e$.