A note on the edge cover chromatic index of multigraphs

Let G be a multigraph with vertex set V(G). An edge coloring C of G is called an edge-cover-coloring if each color appears at least once at each vertex v∈V(G). The maximum positive integer k such that G has a k-edge-cover-coloring is called the edge cover chromatic index of G and is denoted by . It is well known that , where μ(v) is the multiplicity of v and δ(G) is the minimum degree of G. We improve this lower bound to δ(G)−1 when 2≤δ(G)≤5. Furthermore we show that this lower bound is best possible.     

On the unimodality of average edge cover polynomials

The edge cover polynomial of a graph G is the function $E(G,x)={\sum }_{i\ge 1}e(G,i)x^i$, where $e(G,i)$ is the number of edge coverings of G with size i. In this paper, we show that the average edge cover polynomial of order n is reduced to the edge cover polynomial of complete graph $K_n$, based on which we establish that the average edge cover polynomial of order n is unimodal and has at least $n?3$ non-real roots.     

A note on the stability of cut cells and cell merging

Embedded boundary meshes may have cut cells of arbitrarily small volume which can lead to stability problems in finite volume computations with explicit time stepping. We show that time step constraints are not as strict as often believed. We prove this in one dimension for linear advection and the first order upwind scheme. Numerical examples in two dimensions demonstrate that this carries over to more complicated situations. This analysis sheds light on the choice of time step when using cell merging to stabilize the arbitrarily small cells that arise in embedded boundary schemes.     

A sharp bound on the size of a connected matroid

This paper proves that a connected matroid in which a largest circuit and a largest cocircuit have and elements, respectively, has at most elements. It is also shown that if is an element of and and are the sizes of a largest circuit containing and a largest cocircuit containing , then . Both these bounds are sharp and the first is proved using the second. The second inequality is an interesting companion to Lehman's width-length inequality which asserts that the former inequality can be reversed for regular matroids when and are replaced by the sizes of a smallest circuit containing and a smallest cocircuit containing . Moreover, it follows from the second inequality that if and are distinct vertices in a -connected loopless graph , then cannot exceed the product of the length of a longest -path and the size of a largest minimal edge-cut separating from .

     

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.     

Circle graphs and the cycle double cover conjecture

The long standing Cycle Double Cover Conjecture states that every bridgeless graph can be covered by a family of cycles such that every edge is covered exactly twice. Intimately related is the problem of finding, in an eulerian graph, a circuit decomposition compatible with a given transition system (transition systems are also known as decompositions into closed paths). One approach that seems promising consists in finding a black anticlique in the corresponding Sabidussi orbit of bicolored circle graphs.     

Estimates on the size of the cycle spectra of Hamiltonian graphs

Given a graph $G$, let $S\left(G\right)$ be the set of all cycle lengths contained in $G$ and let $s\left(G\right)=\left|S\left(G\right)\right|$. Let $?\left(G\right)=\{3,\dots ,n\}?S\left(G\right)$ and let $d$ be the greatest common divisor of $n?2$ and all the positive pairwise differences of elements in $?\left(G\right)$. We prove that if a Hamiltonian graph $G$ of order $n$ has at least $\frac{n(p+2)}{4}+1$ edges, where $p$ is an integer such that $1\le p\le n?2$, then $s\left(G\right)\ge p$ or $G$ is exceptional, by which we mean $d?(??2)$ for some $?\in ?\left(G\right)$. We also discuss cases where $G$ is not exceptional, for example when $n?2$ is prime. Moreover, we show that $s\left(G\right)\ge min\{p,\frac{n?3}{2}\}$, which if $G$ is bipartite implies that $s\left(G\right)\ge min\{?\frac{4(m?1)}{n}?2?,\frac{n?2}{2}\}$, where $m$ is the number of edges in $G$.     

Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems

We consider an -hard variant (Δ-Max-ATSP) and an -hard relaxation (Max-3-DCC) of the classical traveling salesman problem. We present a -approximation algorithm for Δ-Max-ATSP and a -approximation algorithm for Max-3-DCC with polynomial running time. The results are obtained via a new way of applying techniques for computing undirected cycle covers to directed problems.     

A New Formulation and Computational Results for the Simple Cycle Problem

In this paper we propose a new formulation for the Simple Cycle Problem and conduct preliminary computational tests comparing it with a formulation that comes from the literature.     

A note on submodular set cover on matroids

We consider a problem related to the submodular set cover on polymatroids, when the ground set is the family of independent sets of a matroid. The achievement here is getting a strongly polynomial running time with respect to the ground set of the matroid even though the family of independent sets has exponential size. We also address the optimization problem of the maximization of submodular set functions on the independent sets of a matroid.     

A bound on the size of separating hash families

The paper provides an upper bound on the size of a (generalized) separating hash family, a notion introduced by Stinson, Wei and Chen. The upper bound generalizes and unifies several previously known bounds which apply in special cases, namely bounds on perfect hash families, frameproof codes, secure frameproof codes and separating hash families of small type.     

Edge irregular total labellings for graphs of linear size

As an edge variant of the well-known irregularity strength of a graph G=(V,E) we investigate edge irregular total labellings, i.e. functions f:V∪E→{1,2,…,k} such that f(u)+f(uv)+f(v)≠f(u^′)+f(u^′v^′)+f(v^′) for every pair of different edges uv,u^′v^′∈E. The smallest possible k is the total edge irregularity strength of G. Confirming a conjecture by Ivan?o and Jendrol’ for a large class of graphs we prove that the natural lower bound is tight for every graph of order n, size m and maximum degree Δ with m>111000Δ. This also implies that the probability that a random graph from G(n,p(n)) satisfies the Ivan?o-Jendrol’ Conjecture tends to 1 as n→∞ for all functions p∈[0,1]^N. Furthermore, we prove that is an upper bound for every graph G of order n and size m≥3 whose edges are not all incident to a single vertex.     

A cut finite element method for a Stokes interface problem

We present a finite element method for the Stokes equations involving two immiscible incompressible fluids with different viscosities and with surface tension. The interface separating the two fluids does not need to align with the mesh. We propose a Nitsche formulation which allows for discontinuities along the interface with optimal a priori error estimates. A stabilization procedure is included which ensures that the method produces a well conditioned stiffness matrix independent of the location of the interface.     

Edge choosability of planar graphs without 5-cycles with a chord

Let G be a plane graph having no 5-cycles with a chord. If either Δ≥6, or Δ=5 and G contains no 4-cycles with a chord or no 6-cycles with a chord, then G is edge-(Δ+1)-choosable, where Δ denotes the maximum degree of G.     

A quadratic distance bound on sliding between crossing-free spanning trees

Let S be a set of n points in the plane and let be the set of all crossing-free spanning trees of S. We show that it is possible to transform any two trees in into each other by O(n²) local and constant-size edge slide operations. Previously no polynomial upper bound for this task was known, but in [O. Aichholzer, F. Aurenhammer, F. Hurtado, Sequences of spanning trees and a fixed tree theorem, Comput. Geom.: Theory Appl. 21 (1–2) (2002) 3–20] a bound of O(n²logn) operations was conjectured.