A fundamental theorem of Wilson states that, for every graph , every sufficiently large -divisible clique has an -decomposition. Here a graph is -divisible if divides and the greatest common divisor of the degrees of divides the greatest common divisor of the degrees of , and has an -decomposition if the edges of can be covered by edge-disjoint copies of . We extend this result to graphs which are allowed to be far from complete. In particular, together with a result of Dross, our results imply that every sufficiently large -divisible graph of minimum degree at least has a -decomposition. This significantly improves previous results towards the long-standing conjecture of Nash-Williams that every sufficiently large -divisible graph with minimum degree at least has a -decomposition. We also obtain the asymptotically correct minimum degree thresholds of for the existence of a -decomposition, and of for the existence of a -decomposition, where . Our main contribution is a general ‘iterative absorption’ method which turns an approximate or fractional decomposition into an exact one. In particular, our results imply that in order to prove an asymptotic version of Nash-Williams' conjecture, it suffices to show that every -divisible graph with minimum degree at least has an approximate -decomposition.

E-mobility plays a key role especially in contexts where the transportation activities impact a lot on the total costs. The Electric Vehicles (EVs) are becoming an effective alternative to the internal combustion engines guaranteeing cheaper and eco-sustainable transport solutions. However, the poor battery autonomy is still an Achille's hell since the EVs require many stops for being recharged. We aim to optimally route the EVs for handling a set of customers in time considering the recharging needs during the trips. A Mixed Integer Linear Programming formulation of the problem is proposed assuming that the battery recharging level reached at each station is a decision variable in order to guarantee more flexible routes. The model aims to minimize the total travel, waiting and recharging time plus the number of the employed EVs. Finally, a Variable Neighborhood Search Branching (VNSB) is also designed for solving the problem at hand in reasonable computational times. Numerical results on benchmark instances show the performances of both the mathematical formulation and the VNSB compared to the ones of the model in which the battery level reached at each station is always equal to the maximum capacity.

Given a graph whose vertices have been properly coloured, we say that a path in is if no two vertices in the path have the same colour. It is a corollary of the Gallai–Roy–Vitaver Theorem that every properly coloured graph contains a colourful path on vertices. We explore a conjecture that states that every properly coloured triangle-free graph contains an induced colourful path on vertices and prove its correctness when the girth of is at least . Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function such that if , then an induced colourful path on vertices is guaranteed to exist in any properly coloured triangle-free graph .

A of a graph is a partition of into stable sets . Given a weight function , the is defined as and the as . Guan and Zhu [Inf. Process. Lett., 1997] defined the of a pair ( , ), denoted by , as the minimum weight of a proper coloring of . For a positive integer , they also defined as the minimum of ( ) among all proper -colorings of . The complexity of determining when is a tree was open for almost 20 years, until Araújo [SIAM J. Discrete Math., 2014] recently proved that the problem cannot be solved in time on -vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing and when is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis . Building on the techniques of Araújo , we prove that when is a forest, computing is -hard parameterized by the size of a largest connected component of , and that computing is -hard parameterized by . Our results rule out the existence of algorithms for computing these invariants on trees or forests for many natural choices of the parameter.

A routing of a connected graph is a collection that contains simple paths connecting every ordered pair of vertices in . The (or simply the forwarding index with respect to ) of is the maximum number of paths in passing through any edge of . The of is the minimum over all routings ’s of . This parameter has been studied for different graph classes (Xu and Xu, 2012; Bouabdallah and Sotteau, 1993; Fernandez de la Vega and Gordone, 1992; de la Vega and Manoussakis, 1992). Motivated by energy efficiency, we look, for different numbers of edges, at the best spanning graphs of a square grid, namely those with a low forwarding index.

The is the maximum number of edges in a graph on vertices which does not contain as a subgraph. Gorgol gives a lower bound for when is the disjoint union of copies of and conjectures this bound is tight. In this paper, we give an algorithmic proof of Gorgol’s Conjecture.

A function is a (proper) -colouring of if , for every edge . The is the smallest integer for which there exists a proper -colouring of . Given a graph and a subgraph of , a circular -backbone -colouring of is a -colouring of such that , for each edge . The of a graph pair , denoted , is the minimum such that admits a circular -backbone -colouring. Inspired by Steinberg’s conjecture, we conjecture that if is a planar graph containing no cycles on 4 or 5 vertices and is a forest, then . In this work, we first show that if is a planar graph containing no cycle on 4 or 5 vertices and is a forest, then . Then, we prove that if is a forest whose connected components are paths, then .

We show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. Our approach works for the Tutte polynomial, the independence polynomial, and partition functions of complex-valued spin- and edge-coloring models.

Given a graph representing a substrate (or physical) network with node and edge capacities and a set of virtual networks with node capacity demands and node-to-node traffic demands, the Virtual Network Embedding problem (VNE) calls for an embedding of (a subset of) the virtual networks onto the substrate network which maximizes the total profit while respecting the physical node and edge capacities. In this work, we investigate the computational complexity of VNE. In particular, we present a polynomial-time reduction from the maximum stable set problem which implies strong -hardness for VNE even for very special subclasses of graphs and yields a strong inapproximability result for general graphs. We also consider the special cases obtained when fixing one of the dimensions of the problem to one. We show that VNE is still strongly -hard when a single virtual network request is present or when each virtual network request consists of a single virtual node and that it is weakly -hard for the case with a single physical node.

A graph is -free if it has no induced subgraph isomorphic to . We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of -free split graphs whose clique-width is bounded. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine graphs for which the class of -free split graphs has bounded clique-width.

Consider the sum , where is a sequence of non-zero reals and is a sequence of i.i.d. Rademacher random variables (that is, ). The classical Littlewood–Offord problem asks for the best possible upper bound on the concentration probabilities . In this paper we study a resilience version of the Littlewood–Offord problem: how many of the is an adversary typically allowed to change without being able to force concentration on a particular value? We solve this problem asymptotically, and present a few interesting open problems.

Testing if a given graph contains the -vertex path as a minor or as an induced minor is trivial for every fixed integer . The situation changes for the problem of checking if a graph can be modified into by using only edge contractions. In this case the problem is known to be -complete even if . This led to an intensive investigation for testing contractibility on restricted graph classes. We focus on bipartite graphs. Heggernes, van 't Hof, Lévêque and Paul proved that the problem stays -complete for bipartite graphs if . We strengthen their result from to . We also show that the problem of contracting a bipartite graph to the 6-vertex cycle is -complete. The cyclicity of a graph is the length of the longest cycle the graph can be contracted to. As a consequence of our second result, determining the cyclicity of a bipartite graph is -hard.

A graph is called quasirandom if it possesses typical properties of the corresponding random graph with the same edge density as . A well-known theorem of Chung, Graham and Wilson states that, in fact, many such ‘typical’ properties are asymptotically equivalent and, thus, a graph possessing one property immediately satisfies the others. In recent years, more quasirandom graph properties have been found and extensions to hypergraphs have been explored. For the latter, however, there exist several distinct notions of quasirandomness. A complete description of these notions has been provided recently by Towsner, who proved several central equivalences using an analytic framework. The purpose of this paper is to give short purely combinatorial proofs of most of Towsner's results.

Nowadays finding effective solution for transportation problem is one of the main issues both in industries and academia. According to the real world, in this paper it is assumed that the products are transferred in batches in a fixed charge transportation problem. Furthermore, the fuzzy values are used according to the parameters value in the real world. In addition, six meta-heuristics are utilized in order to solve the presented model. Most of these algorithms are firstly used for a mathematical model in transportation problem literature. Because of the importance of tuning the parameters in solving the given problem, the Taguchi method is used. Finally, computational results with different problem sizes are studied and analyzed.

A Dyck path of length with flaws is a path in the integer lattice that starts at the origin and consists of many -steps and many -steps that change the current coordinate by or , respectively, and that has exactly many -steps below the line . Denoting by the set of Dyck paths of length with flaws, the well-known Chung–Feller theorem asserts that the sets all have the same cardinality , the th Catalan number. The standard combinatorial proof of this classical result establishes a bijection between and that swaps certain parts of the given Dyck path , with the effect that and may differ in many positions. In this paper we strengthen the Chung–Feller theorem by presenting a simple bijection between and which has the additional feature that and differ in only positions (the least possible number). We also present an algorithm that allows to compute a sequence of applications of in constant time per generated Dyck path. As an application, we use our minimum-change bijection to construct cycle-factors in the odd graph and the middle levels graph – two intensively studied families of vertex-transitive graphs – that consist of many cycles of the same length.

Urban waste collection is an important problem in modern cities, where efficient techniques are demanded to reduce large budgetary expenses, and avoid environmental and social problems. This article presents two state-of-the-art multiobjective evolutionary algorithms to solve a variant of the urban waste collection problem considering priorities and the conflicting goals of minimizing the total distance while maximizing the Quality of Service. The main results for real scenarios in Montevideo, Uruguay, show that accurate trade-off solutions outperformed greedy approaches, including the current routing methodology applied by local authorities. The competitiveness of the evolutionary algorithms was also confirmed when solving a prototype scenario using dynamic information.

Network Function Virtualization (NFV) is a promising network architecture concept to reduce operational costs. In legacy networks, network functions, such as firewall or TCP optimization, are performed by specific hardware. In networks enabling NFV coupled with the Software Defined Network (SDN) paradigm, network functions can be implemented dynamically on generic hardware. This is of primary interest to implement energy efficient solutions, in order to adapt dynamically the resource usage to the demands. In this paper, we . We consider a setting in which a flow has to go through a Service Function Chain, that is several network functions in a specific order. We propose a decomposition model that relies on chaining and function placement configurations to solve the problem. We show that virtualization allows to obtain between 15% to 62% of energy savings for networks of different sizes.

A is a maximal bipartite complete induced subgraph of . Bicliques have been studied in the last years motivated by the large number of applications. In particular, enumeration of the maximal bicliques has been of interest in data analysis. Associated with this issue, upper and lower bounds on the maximun number of bicliques were given. In this paper we study lower bounds on the number of bicliques of a graph. Since adding false-twin vertices to does not change the number of bicliques, we restrict to false-twin-free graphs. We give a tight lower bound on the minimum number bicliques in { ,diamond,false-twin}-free graphs, { ,false-twin}-free graphs and we present some conjectures for general false-twin-free graphs.

It was independently conjectured by Häggkvist in 1989 and Kriesell in 2011 that given a positive integer , every simple Eulerian graph with high minimum degree (depending on ) admits an Eulerian tour such that every segment of length at most of the tour is a path. Bensmail, Harutyunyan, Le and Thomassé recently verified the conjecture for 4-edge-connected Eulerian graphs. Building on that proof, we prove here the full statement of the conjecture. This implies a variant of the path case of Barát-Thomassen conjecture that any simple Eulerian graph with high minimum degree can be decomposed into paths of fixed length and possibly an additional path of shorter length.

We propose a Genetic Algorithm (GA) to address a Green Vehicle Routing Problem (G-VRP). Unlike classic formulations of the VRP, this study aims to minimise the CO emissions per route. The G-VRP is of interest to policy makers who wish to reduce greenhouse gas emissions. The GA is tested on a suite of benchmark, and real-world instances which include road speed and gradient data. Our solution approach incorporates elements of local and population search heuristics. Solutions are compared with routes currently used by drivers in a courier company. Reductions in emissions are achieved without incurring additional operational costs.