Steiner tree packing number and tree connectivity

Let $S$ be a set of at least two vertices in a graph $G$. A subtree $T$ of $G$ is a $S$-Steiner tree if $S?V\left(T\right)$. Two $S$-Steiner trees $T_1$ and $T_2$ are edge-disjoint (resp. internally vertex-disjoint) if $E\left(T_1\right)\cap E\left(T_2\right)=?$ (resp. $E\left(T_1\right)\cap E\left(T_2\right)=?$ and $V\left(T_1\right)\cap V\left(T_2\right)=S$). Let ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) $S$-Steiner trees in $G$, and let ${\lambda }_k\left(G\right)$ (resp. ${\kappa }_k\left(G\right)$) be the minimum ${\lambda }_G\left(S\right)$ (resp. ${\kappa }_G\left(S\right)$) for $S$ ranges over all $k$-subset of $V\left(G\right)$. Kriesell conjectured that if ${\lambda }_G\left(\{x,y\}\right)\ge 2k$ for any $x,y\in S$, then ${\lambda }_G\left(S\right)\ge k$. He proved that the conjecture holds for $\left|S\right|=3,4$. In this paper, we give a short proof of Kriesell’s Conjecture for $\left|S\right|=3,4$, and also show that ${\lambda }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ (resp. ${\kappa }_k\left(G\right)\ge ?\frac{1}{k?1}?\frac{k?}{2}??$ ) if $\lambda \left(G\right)\ge ?$ (resp. $\kappa \left(G\right)\ge ?$) in $G$, where $k=3,4$. Moreover, we also study the relation between ${\kappa }_k\left(L\left(G\right)\right)$ and ${\lambda }_k\left(G\right)$, where $L\left(G\right)$ is the line graph of $G$.     

A new forbidden pair for 6-contractible edges

An edge of a $k$-connected graph is said to be $k$-contractible if the contraction of the edge results in a $k$-connected graph. If every $k$-connected graph with no $k$-contractible edge has either $H_1$ or $H_2$ as a subgraph, then an unordered pair of graphs $\{H_1,H_2\}$ is said to be a forbidden pair for $k$-contractible edges. We prove that $\{K_1+3K_2,K_1+(P_3\cup K_2)\}$ is a forbidden pair for 6-contractible edges, which is an extension of a previous result due to Ando and Kawarabayashi.     

Proper connection and size of graphs

An edge-coloured graph $G$ is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph $G,$ denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colours that are needed in order to make $G$ properly connected. Our main result is the following: Let $G$ be a connected graph of order $n$ and $k\ge 2$. If $\left|E\left(G\right)\right|\ge \left(\genfrac{}{}{0ex}{}{n?k?1}{2}\right)+k+2$, then $\mathrm{pc}\left(G\right)\le k$ except when $k=2$ and $G\in \{G_1,G_2\},$ where $G_1=K_1\vee (2K_1+K_2)$ and $G_2=K_1\vee (K_1+2K_2).$     

Limit theorems for Hilbert space-valued linear processes under long range dependence

Let ${\left(X_k\right)}_{k\in \mathbb{Z}}$ be a linear process with values in a separable Hilbert space $\mathbb{H}$ given by $X_k={\sum }_{j=0}^{\infty }{(j+1)}^{?N}{\epsilon }_{k?j}$ for each $k\in \mathbb{Z}$, where $N:\mathbb{H}\to \mathbb{H}$ is a bounded, linear normal operator and ${\left({\epsilon }_k\right)}_{k\in \mathbb{Z}}$ is a sequence of independent, identically distributed $\mathbb{H}$-valued random variables with $E{\epsilon }_0=0$ and $E6{\epsilon }_0{6}^2<\infty$. We investigate the central and the functional central limit theorem for ${\left(X_k\right)}_{k\in \mathbb{Z}}$ when the series of operator norms ${\sum }_{j=0}^{\infty }6{(j+1)}^{?N}{6}_{op}$ diverges. Furthermore, we show that the limit process in case of the functional central limit theorem generates an operator self-similar process.     

On disjoint matchings in cubic graphs

For $i=2,3$ and a cubic graph $G$ let ${\nu }_i\left(G\right)$ denote the maximum number of edges that can be covered by $i$ matchings. We show that ${\nu }_2\left(G\right)\ge \frac{4}{5}\left|V\left(G\right)\right|$ and ${\nu }_3\left(G\right)\ge \frac{7}{6}\left|V\left(G\right)\right|$. Moreover, it turns out that ${\nu }_2\left(G\right)\le \frac{\left|V\left(G\right)\right|+2{\nu }_3\left(G\right)}{4}$.     

Partitions of natural numbers with the same weighted representation functions

TextFor any given two positive integers $k_1$ and $k_2$, and any set A of nonnegative integers, let $r_{k_1,k_2}(A,n)$ denote the number of solutions of the equation $n=k_1{a}_1+k_2{a}_2$ with $a_1,a_2\in A$. In this paper, we determine all pairs $k_1,k_2$ of positive integers for which there exists a set $A?\mathbb{N}$ such that $r_{k_1,k_2}(A,n)=r_{k_1,k_2}(\mathbb{N}?A,n)$ for all $n?n_0$. We also pose several problems for further research.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=EnezEsJl0OY.     

Ramsey numbers of odd cycles versus larger even wheels

The generalized Ramsey number $R(G_1,G_2)$ is the smallest positive integer $N$ such that any red–blue coloring of the edges of the complete graph $K_N$ either contains a red copy of $G_1$ or a blue copy of $G_2$. Let $C_m$ denote a cycle of length $m$ and $W_n$ denote a wheel with $n+1$ vertices. In 2014, Zhang, Zhang and Chen determined many of the Ramsey numbers $R(C_{2k+1},W_n)$ of odd cycles versus larger wheels, leaving open the particular case where $n=2j$ is even and $k<j<3k∕2$. They conjectured that for these values of $j$ and $k$, $R(C_{2k+1},W_{2j})=4j+1$. In 2015, Sanhueza-Matamala confirmed this conjecture asymptotically, showing that $R(C_{2k+1},W_{2j})\le 4j+334$. In this paper, we prove the conjecture of Zhang, Zhang and Chen for almost all of the remaining cases. In particular, we prove that $R(C_{2k+1},W_{2j})=4j+1$ if $j?k\ge 251$, $k<j<3k∕2$, and $j\ge 212299$.     

Sum choice number of generalized θ-graphs

Let $G=\left(VE\right)$ be a simple graph and for every vertex $v\in V$ let $L\left(v\right)$ be a set (list) of available colors. $G$ is called $L$-colorable if there is a proper coloring $\phi$ of the vertices with $\phi \left(v\right)\in L\left(v\right)$ for all $v\in V$. A function $f:V\to \mathbb{N}$ is called a choice function of $G$ and $G$ is said to be $f$-list colorable if $G$ is $L$-colorable for every list assignment $L$ choice function is defined by $size\left(f\right)={\sum }_{v\in V}f\left(v\right)$ and the sum choice number ${\chi }_{sc}\left(G\right)$ denotes the minimum size of a choice function of $G$.Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For $r\ge 3$ a generalized ${\theta }_{k_1{k}_2\dots k_r}$-graph is a simple graph consisting of two vertices $v_1$ and $v_2$ connected by $r$ internally vertex disjoint paths of lengths $k_1,k_2,\dots ,k_r$ $(k_1\le k_2\le ?\le k_r)$.In 2014, Carraher et al. determined the sum-paintability of all generalized $\theta$-graphs which is an online-version of the sum choice number and consequently an upper bound for it.In this paper we obtain sharp upper bounds for the sum choice number of all generalized $\theta$-graphs with $k_1\ge 2$ and characterize all generalized $\theta$-graphs $G$ which attain the trivial upper bound $\left|V\left(G\right)\right|+\left|E\left(G\right)\right|$.     

Degree Ramsey numbers for even cycles

Let $H\stackrel{s}{?}G$ denote that any $s$-coloring of $E\left(H\right)$ contains a monochromatic $G$. The degree Ramsey number of a graph $G$, denoted by $R_{\Delta }(G,s)$, is $min\{\Delta \left(H\right):H\stackrel{s}{?}G\}$. We consider degree Ramsey numbers where $G$ is a fixed even cycle. Kinnersley, Milans, and West showed that $R_{\Delta }(C_{2k},s)\ge 2s$, and Kang and Perarnau showed that $R_{\Delta }(C_4,s)=\Theta \left(s^2\right)$. Our main result is that $R_{\Delta }(C_6,s)=\Theta \left(s^{3∕2}\right)$ and $R_{\Delta }(C_{10},s)=\Theta \left(s^{5∕4}\right)$. Additionally, we substantially improve the lower bound for $R_{\Delta }(C_{2k},s)$ for general $k$.