Optimal on-line colorings for minimizing the number of ADMs in optical networks

We consider the problem of minimizing the number of ADMs in optical networks. All previous theoretical studies of this problem dealt with the off-line case, where all the lightpaths are given in advance. In a real-life situation, the requests (lightpaths) arrive at the network on-line, and we have to assign them wavelengths so as to minimize the switching cost. This study is thus of great importance in the theory of optical networks. We present a deterministic on-line algorithm for the problem, and show its competitive ratio to be $\frac{7}{4}$. We show that this result is best possible in general. Moreover, we show that even for the ring topology network there is no on-line algorithm with competitive ratio better than $\frac{7}{4}$. We show that on path topology the competitive ratio of the algorithm is $\frac{3}{2}$. This is optimal for in this topology. The lower bound on ring topology does not hold when the ring is of bounded size. We analyze the triangle topology and show a tight bound of $\frac{5}{3}$ for it. The analyses of the upper bounds, as well as those for the lower bounds, are all using a variety of proof techniques, which are of interest by their own, and which might prove helpful in future research on the topic.     

Dejean's conjecture and letter frequency

We prove two cases of a strong version of Dejean's conjecture involving extremal letter frequencies. The results are that there exist an infinite $\left({\frac{5}{4}}^{+}\right)$-free word over a 5 letter alphabet with letter frequency $\frac{1}{6}$ and an infinite $\left({\frac{6}{5}}^{+}\right)$-free word over a 6 letter alphabet with letter frequency $\frac{1}{5}$.     

On a conjecture of Gentner and Rautenbach

Gentner and Rautenbach conjectured that the size of a minimum zero forcing set in a connected graph on $n$ vertices with maximum degree $3$ is at most $\frac{1}{3}n+2$. We disprove this conjecture by constructing a collection of connected graphs $\left\{G_n\right\}$ with maximum degree 3 of arbitrarily large order having zero forcing number at least $\frac{4}{9}\left|V\left(G_n\right)\right|$.     

Asymptotically good quasi-cyclic codes of fractional index

Generalizing the quasi-cyclic codes of index $1\frac{1}{3}$ introduced by Fan et al., we study a more general class of quasi-cyclic codes of fractional index generated by pairs of polynomials. The parity check polynomial and encoder of these codes are obtained. The asymptotic behaviours of the rates and relative distances of this class of codes are studied by using a probabilistic method. We prove that, for any positive real number $\delta$ such that the asymptotic GV-bound at $\frac{k+l}{2}\delta$ is greater than $\frac{1}{2}$, the relative distance of the code is convergent to $\delta$, while the rate is convergent to $\frac{1}{k+l}$. As a result, quasi-cyclic codes of fractional index are asymptotically good.     

Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability

This paper is the first successful attempt on differential approximability study for a scheduling problem. Such a study considers the weighted completion time minimization on a single machine with a fixed non-availability interval. The analysis shows that the Weighted Shortest Processing Time (WSPT) rule cannot yield a differential approximation for the problem under consideration in the general case. Nevertheless, a slight modification of this rule provides an approximation with a differential ratio of $\frac{3?\sqrt{5}}{2}\approx 0.38$.     

Hamiltonicity of edge chromatic critical graphs

Vizing conjectured that every edge chromatic critical graph contains a 2-factor. Believing that stronger properties hold for this class of graphs, Luo and Zhao (2013) showed that every edge chromatic critical graph of order $n$ with maximum degree at least $\frac{6n}{7}$ is Hamiltonian. Furthermore, Luo et al. (2016) proved that every edge chromatic critical graph of order $n$ with maximum degree at least $\frac{4n}{5}$ is Hamiltonian. In this paper, we prove that every edge chromatic critical graph of order $n$ with maximum degree at least $\frac{3n}{4}$ is Hamiltonian. Our approach is inspired by the recent development of Kierstead path and Tashkinov tree techniques for multigraphs.     

Diffuse reflection diameter and radius for convex-quadrilateralizable polygons

In this paper we study the diffuse reflection diameter and diffuse reflection radius problems for convex-quadrilateralizable polygons. In the usual model of diffuse reflection, a light ray incident at a point on the reflecting surface is reflected from that point in all possible inward directions. A ray reflected from a polygonal edge may graze that reflecting edge but an incident ray cannot graze the reflecting edge. The diffuse reflection diameter of a simple polygon $P$ is the minimum number of diffuse reflections that may be needed in the worst case to illuminate any target point $t$ from any point light source $s$ inside $P$. We show that the diameter is upper bounded by $\frac{3n?10}{4}$ in our usual model of diffuse reflection for convex-quadrilateralizable polygons. To the best of our knowledge, this is the first upper bound on diffuse reflection diameter within a fraction of $n$ for such a class of polygons. We also show that the diffuse reflection radius of a convex-quadrilateralizable simple polygon with $n$ vertices is at most $\frac{3n?10}{8}$ under the usual model of diffuse reflection. In other words, there exists a point inside such a polygon from which $\frac{3n?10}{8}$ usual diffuse reflections are always sufficient to illuminate the entire polygon. In order to establish these bounds for the usual model, we first show that the diameter and radius are $\frac{n?4}{2}$ and $?\frac{n?4}{4}?$ respectively, for the same class of polygons for a relaxed model of diffuse reflections; in the relaxed model an incident ray is permitted to graze a reflecting edge before turning and reflecting off the same edge at any interior point on that edge. We also show that the worst-case diameter and radius lower bounds of $\frac{n?4}{2}$ and $?\frac{n?4}{4}?$ respectively, are sometimes attained in the usual model, as well as in the relaxed model of diffuse reflection.