Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable

It is shown that a planar graph without cycles of length 4, 5, 8, or 9 is 3-choosable.     

Novel image encryption algorithm based on cycle shift and chaotic system

In this paper, a novel image encryption algorithm is proposed. The cycle shift in bits of pixels and the chaotic system are employed for the encryption of the proposed scheme. For cycle shift operations, random integers with the same size of the original image are produced to scramble the plaintext image. Moreover, the scrambled image effects the initial values of the chaotic system for the further encryption process, which increases the sensitivity of plaintext images of the scheme. The scrambled image is encrypted into the ciphered image by the keys which are produced by the chaotic system. The simulation experiments and theoretical analyses indicate that the proposed scheme is superior and able to resist exhaustive attack and statistical attack.     

Cycles embedding on folded hypercubes with faulty nodes

Let F_Fv$F{F}_v$ be the set of faulty nodes in an n$n$-dimensional folded hypercube F_Qn$F{Q}_n$ with |F_Fv|≤n−2$\left|F{F}_v\right|\le n-2$. In this paper, we show that if n≥3$n\ge 3$, then every edge of F_Qn−F_Fv$F{Q}_n-F{F}_v$ lies on a fault-free cycle of every even length from 4$4$ to 2ⁿ−2|F_Fv|$2^n-2\left|F{F}_v\right|$, and if n≥2$n\ge 2$ and n$n$ is even, then every edge of F_Qn−F_Fv$F{Q}_n-F{F}_v$ lies on a fault-free cycle of every odd length from n+1$n+1$ to 2ⁿ−2|F_Fv|−1$2^n-2\left|F{F}_v\right|-1$.     

The impact of sampling time on peak capacity and analysis speed in on-line comprehensive two-dimensional liquid chromatography

Comprehensive two-dimensional liquid chromatography (2DLC) offers a number of practical advantages over optimized one-dimensional LC in peak capacity and thus in resolving power. The traditional “product rule” for overall peak capacity for a 2DLC system significantly overestimates peak capacity because it neglects under-sampling of the first dimension separation. Here we expand on previous work by more closely examining the effects of the first dimension peak capacity and gradient time, and the second dimension cycle times on the overall peak capacity of the 2DLC system. We also examine the effects of re-equilibration time on under-sampling as measured by the under-sampling factor and the influence of molecular type (peptide vs. small molecule) on peak capacity. We show that in fast 2D separations (less than 1 h), the second dimension is more important than the first dimension in determining overall peak capacity and conclude that extreme measures to enhance the first dimension peak capacity are usually unwarranted. We also examine the influence of sample types (small molecules vs. peptides) on second dimension peak capacity and peak capacity production rates, and how the sample type influences optimum second dimension gradient and re-equilibration times.     

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M=(V,E,A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C={C₁,…,C_k} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is . The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width.     

The incidence game chromatic number

We introduce the incidence game chromatic number which unifies the ideas of game chromatic number and incidence coloring number of an undirected graph. For k-degenerate graphs with maximum degree Δ, the upper bound 2Δ+4k−2 for the incidence game chromatic number is given. If Δ≥5k, we improve this bound to the value 2Δ+3k−1. We also determine the exact incidence game chromatic number of cycles, stars and sufficiently large wheels and obtain the lower bound for the incidence game chromatic number of graphs of maximum degree Δ.     

Minimum-weight cycle covers and their approximability

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L⊆N.We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise non-constructive polynomial-time approximation algorithms that achieve constant approximation ratios for all sets L. On the other hand, we prove that the problem cannot be approximated with a factor of 2−ε for certain sets L.For directed graphs, we devise non-constructive polynomial-time approximation algorithms that achieve approximation ratios of O(n), where n is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated with a factor of o(n) for certain sets L.To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.     

Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts

In 1998 Cavenagh [N.J. Cavenagh, Decompositions of complete tripartite graphs into k-cycles, Australas. J. Combin. 18 (1998) 193-200] gave necessary and sufficient conditions for the existence of an edge-disjoint decomposition of a complete equipartite graph with three parts, into cycles of some fixed length k. Here we extend this to paths, and show that such a complete equipartite graph with three partite sets of size m, has an edge-disjoint decomposition into paths of length k if and only if k divides 3m² and k<3m. Further, extending to five partite sets, we show that a complete equipartite graph with five partite sets of size m has an edge-disjoint decomposition into cycles (and also into paths) of length k with k?3 if and only if k divides 10m² and k?5m for cycles (or k<5m for paths).     

Asymptotic analysis of a risk process with high dividend barrier

In this paper we study a risk model with constant high dividend barrier. We apply Keilson’s (1966) results to the asymptotic distribution of the time until occurrence of a rare event in a regenerative process, and then results of the cycle maxima for random walk to obtain the asymptotic distribution of the time to ruin and the amount of dividends paid until ruin.