A theorem in edge colouring

We prove the following theorem: if G is an edge-chromatic critical multigraph with more than 3 vertices, and if x,y are two adjacent vertices of G, the edge-chromatic number of G does not change if we add an extra edge joining x and y.     

Sparse hamiltonian 2-decompositions together with exact count of numerous Hamilton cycles

We construct multigraphs of any large order with as few as only four 2-decompositions into Hamilton cycles or only two 2-decompositions into Hamilton paths. Nevertheless, some of those multigraphs are proved to have exponentially many Hamilton cycles (Hamilton paths). Two families of large simple graphs are constructed. Members in one class have exactly 16 hamiltonian pairs and in another class exactly four traceable pairs. These graphs also have exponentially many Hamilton cycles and Hamilton paths, respectively. The exact numbers of (Hamilton) cycles and paths are expressed in terms of Lucas- or Fibonacci-like numbers which count 2-independent vertex (or edge) subsets on the n-path or n-cycle. A closed formula which counts Hamilton cycles in the square of the n-cycle is found for n≥5. The presented results complement, improve on, or extend the corresponding well-known Thomason’s results.     

Achieving maximum chromatic index in multigraphs

Let G be a multigraph with maximum degree Δ and maximum edge multiplicity μ. Vizing’s Theorem says that the chromatic index of G is at most Δ+μ. If G is bipartite its chromatic index is well known to be exactly Δ. Otherwise G contains an odd cycle and, by a theorem of Goldberg, its chromatic index is at most , where g_o denotes odd-girth. Here we prove that a connected G achieves Goldberg’s upper bound if and only if G=μC_go and (g_o−1)∣2(μ−1). The question of whether or not G achieves Vizing’s upper bound is NP-hard for μ=1, but for μ≥2 we have reason to believe that this may be answerable in polynomial time. We prove that, with the exception of μK₃, every connected G with μ≥2 which achieves Vizing’s upper bound must contain a specific dense subgraph on five vertices. Additionally, if Δ≤μ², we prove that G must contain K₅, so G must be nonplanar. These results regarding Vizing’s upper bound extend work by Kierstead, whose proof technique influences us greatly here.     

重图的超f - 边覆盖染色

图G的一个超f - 边覆盖染色就是它的一个f - 边覆盖染色并且使得图G中的重边染上不同的颜色. 令χ^H_fc(G)是图G存在一个超f - 边覆盖染色时所需最大的颜色数k. χ^H_fc(G)称作是图G的超f - 边覆盖染色色数. 本文讨论重图的超f - 边覆盖染色的存在性并且给出了重图的超f - 边覆盖染色的色数下界.     

Characterizations of graphs G having all [1,k]-factors in kG

Let $k\ge 1$ be an integer and $G$ be a graph. Let $kG$ denote the graph obtained from $G$ by replacing each edge of $G$ with $k$ parallel edges. We say that $G$ has all $[1,k]$-factors or all fractional $[1,k]$-factors if $G$ has an $h$-factor or a fractional $h$-factor for every function $h:V\left(G\right)\to \{1,2,\dots ,k\}$ with $h\left(V\left(G\right)\right)$ even. In this note, we come up with simple characterizations of a graph $G$ such that $kG$ has all $[1,k]$-factors or all fractional $[1,k]$-factors. These characterizations are extensions of Tutte’s 1-Factor Theorem and Tutte’s Fractional 1-Factor Theorem.     

A continuous family of partition statistics equidistributed with length

This article investigates a remarkable generalization of the generating function that enumerates partitions by area and number of parts. This generating function is given by the infinite product _∏i?11/(1−tqi). We give uncountably many new combinatorial interpretations of this infinite product involving partition statistics that arose originally in the context of Hilbert schemes. We construct explicit bijections proving that all of these statistics are equidistributed with the length statistic on partitions of n. Our bijections employ various combinatorial constructions involving cylindrical lattice paths, Eulerian tours on directed multigraphs, and oriented trees.     

Classical Kloosterman sums: Representation theory, magic squares, and Ramanujan multigraphs

We consider a certain finite group for which Kloosterman sums appear as character values. This leads us to consider a concrete family of commuting hermitian matrices which have Kloosterman sums as eigenvalues. These matrices satisfy a number of “magical” combinatorial properties and they encode various arithmetic properties of Kloosterman sums. These matrices can also be regarded as adjacency matrices for multigraphs which display Ramanujan-like behavior.     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

The crew timetabling problem: An extension of the crew scheduling problem

In some urban transportation companies driving periods are short when compared with the total duty time, leading to long non-driving periods that can be used as cover time. This paper presents the Crew Timetabling Problem, an extension of the Crew Scheduling Problem in which crew timetables are obtained by levelling the cover crew resources. An objective function for this problem is proposed in order to balance the number of driving and cover crews. A Lisbon Underground case study is used to illustrate the Crew Timetabling Problem. The problem is represented in a multigraph and solved by a tabu search-based heuristic.     

Regular multigraphs and their application to the Monte Carlo evaluation of moments of non-linear functions of Gaussian random variables

This paper expands on the multigraph method for expressing moments of non-linear functions of Gaussian random variables. In particular, it includes a list of regular multigraphs that is needed for the computation of some of these moments. The multigraph method is then used to evaluate numerically the moments of non-Gaussian self-similar processes. These self-similar processes are of interest in various applications and the numerical value of their marginal moments yield qualitative information about the behavior of the probability tails of their marginal distributions.