Approximating the maximum 3-edge-colorable subgraph problem

We offer the following structural result: every triangle-free graph G of maximum degree 3 has 3 matchings which collectively cover at least of its edges, where γ_o(G) denotes the odd girth of G. In particular, every triangle-free graph G of maximum degree 3 has 3 matchings which cover at least 13/15 of its edges. The Petersen graph, where we can 3-edge-color at most 13 of its 15 edges, shows this to be tight. We can also cover at least 6/7 of the edges of any simple graph of maximum degree 3 by means of 3 matchings; again a tight bound.For a fixed value of a parameter k≥1, the Maximum k-Edge-Colorable Subgraph Problem asks to k-edge-color the most of the edges of a simple graph received in input. The problem is known to be APX-hard for all k≥2. However, approximation algorithms with approximation ratios tending to 1 as k goes to infinity are also known. At present, the best known performance ratios for the cases k=2 and k=3 were 5/6 and 4/5, respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case k=3, achieving approximation ratio of 6/7. Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of 13/15 when the input multigraph is restricted to be triangle-free, and of 19/21 when C₅’s are also banned).     

Factors and vertex-deleted subgraphs

A relationship is considered between an f-factor of a graph and that of its vertex-deleted subgraphs. Katerinis [Some results on the existence of 2n-factors in terms of vertex-deleted subgraphs, Ars Combin. 16 (1983) 271-277] proved that for even integer k, if G-x has a k-factor for each x∈V(G), then G has a k-factor. Enomoto and Tokuda [Complete-factors and f-factors, Discrete Math. 220 (2000) 239-242] generalized Katerinis’ result to f-factors, and proved that if G-x has an f-factor for each x∈V(G), then G has an f-factor for an integer-valued function f defined on V(G) with even. In this paper, we consider a similar problem to that of Enomoto and Tokuda, where for several vertices x we do not have to know whether G-x has an f-factor. Let G be a graph, X be a set of vertices, and let f be an integer-valued function defined on V(G) with even, |V(G)-X|?2. We prove that if and if G-x has an f-factor for each x∈V(G)-X, then G has an f-factor. Moreover, if G excludes an isolated vertex, then we can replace the condition with . Furthermore the condition will be when |X|=1.     

Nowhere-zero 3-flow of graphs with small independence number

Tutte’s $3$-flow conjecture states that every $4$-edge-connected graph admits a nowhere-zero $3$-flow. In this paper, we characterize all graphs with independence number at most $4$ that admit a nowhere-zero $3$-flow. The characterization of $3$-flow verifies Tutte’s $3$-flow conjecture for graphs with independence number at most $4$ and with order at least $21$. In addition, we prove that every odd-$5$-edge-connected graph with independence number at most $3$ admits a nowhere-zero $3$-flow. To obtain these results, we introduce a new reduction method to handle odd wheels.     

Coding of geodesics on some modular surfaces and applications to odd and even continued fractions

The connection between geodesics on the modular surface $PSL(2,\mathbb{Z})?\mathbb{H}$ and regular continued fractions, established by Series, is extended to a connection between geodesics on $\Gamma ?\mathbb{H}$ and odd and grotesque continued fractions, where $\Gamma ?{\mathbb{Z}}_{3}1{\mathbb{Z}}_3$ is the index two subgroup of $PSL(2,\mathbb{Z})$ generated by the order three elements $\left(\begin{array}{cc}\hfill 0\hfill & \hfill ?1\hfill \\ \hfill 1\hfill & \hfill 1\hfill \end{array}\right)$ and $\left(\begin{array}{cc}\hfill 0\hfill & \hfill 1\hfill \\ \hfill ?1\hfill & \hfill 1\hfill \end{array}\right)$, and having an ideal quadrilateral as fundamental domain.A similar connection between geodesics on $\Theta ?\mathbb{H}$ and even continued fractions is discussed in our framework, where $\Theta$ denotes the Theta subgroup of $PSL(2,\mathbb{Z})$ generated by $\left(\begin{array}{cc}\hfill 0\hfill & \hfill ?1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \end{array}\right)$ and $\left(\begin{array}{cc}\hfill 1\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 1\hfill \end{array}\right)$.     

A parallel algorithm for solving Toeplitz linear systems

Numerical methods of solution are considered for systems which are Toeplitz and symmetric. In our case, the coefficient matrix is essentially tridiagonal and sparse. There are two distinct approaches to be considered each of which is efficient in its own way. Here we will combine the two approaches which will allow application of the cyclic reduction method to coefficient matrices of more general forms. The convergence of the approximations to the exact solution will also be examined. Solving linear systems by the adapted cyclic reduction method can be parallel processed.     

Convex Envelopes of Monomials of Odd Degree

Convex envelopes of nonconvex functions are widely used to calculate lower bounds to solutions of nonlinear programming problems (NLP), particularly within the context of spatial Branch-and-Bound methods for global optimization. This paper proposes a nonlinear continuous and differentiable convex envelope for monomial terms of odd degree, x ^2k+1, where k N and the range of x includes zero. We prove that this envelope is the tightest possible. We also derive a linear relaxation from the proposed envelope, and compare both the nonlinear and linear formulations with relaxations obtained using other approaches.     

Checking the odd Goldbach conjecture up to

Vinogradov's theorem states that any sufficiently large odd integer is the sum of three prime numbers. This theorem allows us to suppose the conjecture that this is true for all odd integers. In this paper, we describe the implementation of an algorithm which allowed us to check this conjecture up to .

     

2-piercings via graph theory

We provide a very simple proof for a Helly-type result given by Danzer and Grünbaum on 2-piercings of box families in d-dimensional Euclidean space.     

广义Petersen图的弱点传递性

图X称为弱点传递图如果X的自同态幺半群EndX在顶点集V(X)上的作用是传递的 .本文给出了广义Petersen图是二分图的充要条件 ,刻划了奇围长小于 9的广义Petersen图的弱点传递性 ,作为推论给出了所有h ≤ 1 5的弱点传递的广义Pe tersen图P(h ,t) .     

第Ⅴ类两态叠加多模叠加态光场的等阶N次方H压缩特性研究

本文构造了由多模真空态|{O_j}〉q和多模虚相干态的相反态|{-iZ_j}〉q这两者的线性叠加所组成的第Ⅴ类两态叠加多模叠加态光场ψ₅⁽²⁾〉q,利用多模压缩态理论详细研究了态 ψ₅⁽²⁾〉q的广义非线性等阶N次方H压缩特性.结果发现:1)态ψ₅⁽²⁾〉q是一种典型的多模非经典光场;无论腔模总数q与压缩阶数N这两者之积q·N取奇还是取偶,只要各模的初始相位之和 、态间的初始相位之差(θ_nq^(I)－θ_oq^(o))等满足一定的量子化条件,态ψ₅⁽²⁾〉q总可分别呈现出周期性变化的、任意的奇数模-奇数阶、奇数模-偶数阶、偶数模-偶数阶和偶数模-奇数阶这四种不同形式的等阶N次方H压缩效应.2)上述四种不同形式的等阶N次方H压缩效应,其态间压缩条件完全相同,但模间压缩条件完全不同,结果使其压缩幅度、压缩结果和压缩特性等各不相同.3)无论q·N取奇还是取偶,态ψ₅⁽²⁾〉q的第一和第二这两个正交分量的等阶N次方H压缩效应总是呈现周期性的互补关系.