Linearity and classification of ZpZp2-linear generalized Hadamard codes

The ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-additive codes are subgroups of ${\mathbb{Z}}_p^{{\alpha }_1}\times {\mathbb{Z}}_{p^2}^{{\alpha }_2}$, and can be seen as linear codes over ${\mathbb{Z}}_p$ when ${\alpha }_2=0$, ${\mathbb{Z}}_{p^2}$-additive codes when ${\alpha }_1=0$, or ${\mathbb{Z}}_2{\mathbb{Z}}_4$-additive codes when $p=2$. A ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear generalized Hadamard (GH) code is a GH code over ${\mathbb{Z}}_p$ which is the Gray map image of a ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-additive code. Recursive constructions of ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-additive GH codes of type $({\alpha }_1,{\alpha }_2;t_1,t_2)$ with $t_1,t_2\ge 1$ are known. In this paper, we generalize some known results for ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes with $p=2$ to any $p\ge 3$ prime when ${\alpha }_1\ne 0$, and then we compare them with the ones obtained when ${\alpha }_1=0$. First, we show for which types the corresponding ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes are nonlinear over ${\mathbb{Z}}_p$. Then, for these codes, we compute the kernel and its dimension, which allow us to classify them completely. Moreover, by computing the rank of some of these codes, we show that, unlike ${\mathbb{Z}}_4$-linear Hadamard codes, the ${\mathbb{Z}}_{p^2}$-linear GH codes are not included in the family of ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes with ${\alpha }_1\ne 0$ when $p\ge 3$ prime. Indeed, there are some families with infinite nonlinear ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes, where the codes are not equivalent to any ${\mathbb{Z}}_{p^s}$-linear GH code with $s\ge 2$.     

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.     

Quasi-pure E0-semigroups

We introduce a class of $E_0$-semigroups that is broader and more flexible than the class of pure $E_0$-semigroups, and characterize the states of the spectral $C^{?}$-algebra $C^{?}(E)$ of a product system $E={\{E_t\}}_{t>0}$ that give rise to them.     

Hamiltonian cycles in 7-tough (P3 ∪ 2P1)-free graphs

The toughness of a noncomplete graph G is the maximum real number t such that the ratio of $|S|$ to the number of components of $G?S$ is at least t for every cutset S of G. Determining the toughness for a given graph is NP-hard. Chvátal's toughness conjecture, stating that there exists a constant $t_0$ such that every graph with toughness at least $t_0$ is hamiltonian, is still open for general graphs. A graph is called $(P_3\cup 2P_1)$-free if it does not contain any induced subgraph isomorphic to $P_3\cup 2P_1$, the disjoint union of $P_3$ and two isolated vertices. In this paper, we confirm Chvátal's toughness conjecture for $(P_3\cup 2P_1)$-free graphs by showing that every 7-tough $(P_3\cup 2P_1)$-free graph on at least three vertices is hamiltonian.     

Perfect matchings extend to two or more hamiltonian cycles in hypercubes

Kreweras conjectured that every perfect matching of a hypercube $Q_n$ for $n\ge 2$ can be extended to a hamiltonian cycle of $Q_n$. Fink confirmed the conjecture to be true. It is more general to ask whether every perfect matching of $Q_n$ for $n\ge 2$ can be extended to two or more hamiltonian cycles of $Q_n$. In this paper, we prove that every perfect matching of $Q_n$ for $n\ge 4$ can be extended to at least $2^{2^{n?4}}$ different hamiltonian cycles of $Q_n$.