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.     

All double generalized Petersen graphs are Hamiltonian

The double generalized Petersen graph $DP(n,t)$, $n\ge 3$ and $t\in {\mathbb{Z}}_n?\left\{0\right\}$, $2\le 2t<n$, has vertex-set $\{x_i,y_i,u_i,v_i\mid i\in {\mathbb{Z}}_n\}$, edge-set $\{\{x_i,x_{i+1}\},\{y_i,y_{i+1}\},\{u_i,v_{i+t}\},\{v_i,u_{i+t}\},\{x_i,u_i\},\{y_i,v_i\}\mid i\in {\mathbb{Z}}_n\}$. These graphs were first defined by Zhou and Feng as examples of vertex-transitive non-Cayley graphs. Then, Kutnar and Petecki considered the structural properties, Hamiltonicity properties, vertex-coloring and edge-coloring of $DP(n,t)$, and conjectured that all $DP(n,t)$ are Hamiltonian. In this paper, we prove this conjecture.     

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

The NLC-width and clique-width for powers of graphs of bounded tree-width

The $k$-power graph of a graph $G$ is a graph with the same vertex set as $G$, in that two vertices are adjacent if and only if, there is a path between them in $G$ of length at most $k$. A $k$-tree-power graph is the $k$-power graph of a tree, a $k$-leaf-power graph is the subgraph of some $k$-tree-power graph induced by the leaves of the tree.We show that (1) every $k$-tree-power graph has NLC-width at most $k+2$ and clique-width at most $k+2+max\{?\frac{k}{2}??1,0\}$, (2) every $k$-leaf-power graph has NLC-width at most $k$ and clique-width at most $k+max\{?\frac{k}{2}??2,0\}$, and (3) every $k$-power graph of a graph of tree-width $l$ has NLC-width at most ${(k+1)}^{l+1}?1$, and clique-width at most $2?{(k+1)}^{l+1}?2$.     

Minimal degree univariate piecewise polynomials with prescribed Sobolev regularity

For $k\in \{1,2,3,\dots \}$, we construct an even compactly supported piecewise polynomial ${\psi }_k$ whose Fourier transform satisfies $A_k{(1+{\omega }^2)}^{?k}\le {\stackrel{?}{\psi }}_k\left(\omega \right)\le B_k{(1+{\omega }^2)}^{?k}$, $\omega \in \mathbb{R}$, for some constants $B_k\ge A_k>0$. The degree of ${\psi }_k$ is shown to be minimal, and is strictly less than that of Wendland’s function ${?}_{1,k?1}$ when $k>2$. This shows that, for $k>2$, Wendland’s piecewise polynomial ${?}_{1,k?1}$ is not of minimal degree if one places no restrictions on the number of pieces.     

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.