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.     

On tiling the integers with 4-sets of the same gap sequence

Partitioning a set into similar, if not, identical, parts is a fundamental research topic in combinatorics. The question of partitioning the integers in various ways has been considered throughout history. Given a set $\{x_1,\dots ,x_n\}$ of integers where $x_1<?<x_n$, let the gap sequence of this set be the unordered multiset $\{d_1,\dots ,d_{n?1}\}=\{x_{i+1}?x_i:i\in \{1,\dots ,n?1\}\}$. This paper addresses the following question, which was explicitly asked by Nakamigawa: can the set of integers be partitioned into sets with the same gap sequence? The question is known to be true for any set where the gap sequence has length at most two. This paper provides evidence that the question is true when the gap sequence has length three. Namely, we prove that given positive integers $p$ and $q$, there is a positive integer $r_0$ such that for all $r\ge r_0$, the set of integers can be partitioned into 4-sets with gap sequence $p,q$, $r$.     

A sufficient condition for DP-4-colorability

DP-coloring of a simple graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. It is known that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-choosable. Furthermore, Jin et al. (2016) showed that for each $k\in \{3,4,5,6\}$, every signed planar graph without $C_k$ is signed 4-choosable. In this paper, we show that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-DP-colorable, which is an extension of the above results.     

Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs

Let $\Delta =\{{\delta }_1,{\delta }_2,\dots ,{\delta }_m\}$ be a finite set of 2-connected patterns, i.e. graphs up to vertex relabelling. We study the generating function $D_{\Delta }(z,u_1,u_2,\dots ,u_m),$ which counts polygon dissections and marks subgraph copies of ${\delta }_i$ with the variable $u_i$. We prove that this is always algebraic, through an explicit combinatorial decomposition depending on $\Delta$. The decomposition also gives a defining system for $D_{\Delta }(z,\mathbf{0})$, which encodes polygon dissections that avoid these patterns as subgraphs. In this way, we are able to extract normal limit laws for the patterns when they are encoded, and perform asymptotic enumeration of the resulting classes when they are avoided. The results can be transferred to the case of labelled outerplanar graphs. We give examples and compute the relevant constants when the patterns are small cycles or dissections.     

Minimal solutions of the isometry equation

For a finite vector space $W$ over ${\mathbb{F}}_q$, there are described all the pairs of multisets $\{V_1,\dots ,V_{q+1}\}$ and $\{U_1,\dots ,U_{q+1}\}$ of subspaces in $W$ such that for all $w\in W$ the equality $\left|\{i\mid w\in V_i\}\right|=\left|\{i\mid w\in U_i\}\right|$ holds.     

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.     

The expansion of a chord diagram and the Tutte polynomial

A chord diagram is a set of chords of a circle such that no pair of chords has a common endvertex. A chord diagram $E$ is called nonintersecting if $E$ contains no crossing. For a chord diagram $E$ having a crossing $S=\{x_1{x}_3,x_2{x}_4\}$, the expansion of $E$ with respect to $S$ is to replace $E$ with $E_1=(E?S)\cup \{x_2{x}_3,x_4{x}_1\}$ or $E_2=(E?S)\cup \{x_1{x}_2,x_3{x}_4\}$. For a chord diagram $E$, let $f\left(E\right)$ be the chord expansion number of $E$, which is defined as the cardinality of the multiset of all nonintersecting chord diagrams generated from $E$ with a finite sequence of expansions.In this paper, it is shown that the chord expansion number $f\left(E\right)$ equals the value of the Tutte polynomial at the point $(2,?1)$ for the interlace graph $G_E$ corresponding to $E$. The chord expansion number of a complete multipartite chord diagram is also studied. An extended abstract of the paper was published (Nakamigawa and Sakuma, 2017) [13].