Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): A. Michael Alphonse, Gollapudy Shailaja, Pooja Sinha In this paper we present a method to find the minimum dominating set and domination number of some specific Circulant graphs Circ(n,{1, 5}). In this method we construct a tree in which each path from root to the leaf is a dominating set. At each level we compare the number of vertices dominated by the vertices in each path and select the paths which dominate the maximum number of vertices. Since this tree exhibits repeated patterns the number of comparisons are considerably reduced. Finally we arrive at a sequence (path) which gives the minimum dominating set of the Circulant graph. We also discuss the possibility of extending this methodology to Circ(n,{1, m}), where m is any positive integer greater than or equal to 6.

Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): Ovidiu Bagdasar, Ioan-Lucian Popa Horadam sequences are second-order recurrences depending on a family of four complex parameters: two initial conditions and two recurrence coefficients. The periodicity conditions, as well as the number and geometric structure of self-repeating Horadam sequences of fixed length have been recently investigated. In this paper various geometric properties of non-homogeneous Horadam sequences are explored, including periodicity conditions and the structure of certain periodic orbits.

Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): Sugata Gangopadhyay, Bhupendra Singh, V. Vetrivel We identify an infinite class of cubic rotation symmetric bent functions and prove that these functions do not have affine derivatives. Some experimental results concerning rotation symmetric bent functions in 6, 8, 10 and 12 variables are also included.

Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): Robert Hancock, Andrew Treglown Given a linear equation L , a set A ⊆ [ n ] is L -free if A does not contain any ‘non-trivial’ solutions to L . In this paper we consider the following three general questions: (i) What is the size of the largest L -free subset of [n]? (ii) How many L -free subsets of [n] are there? (iii) How many maximal L -free subsets of [n] are there? We completely resolve (i) in the case when L is the equation p x + q y = z for fixed p , q ∈ N where p ≥ 2 . Further, up to a multiplicative constant, we answer (ii) for a wide class of such equations L , thereby refining a special case of a result of Green [15]. We also give various bounds on the number of maximal L -free subsets of [n] for three-variable homogeneous linear equations L . For this, we make use of container and removal lemmas of Green [15].

Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): Nicholas Korpelainen We define permutation-partition graphs by replacing one part of a 2K 2-free bipartite graph (a bipartite chain graph) by an induced linear forest. We show that this hereditary graph class is of of unbounded clique-width (with a new graph construction of large clique-width). We show that this graph class contains no minimal graph class of unbounded clique-width, and give a conjecture for a contained boundary class for this property.

Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): Fionn Murtagh, Pedro Contreras Reading the clusters from a data set such that the overall computational complexity is linear in both data dimensionality and in the number of data elements has been carried out through filtering the data in wavelet transform space. This objective is also carried out after an initial transforming of the data to a canonical order. Including high dimensional, high cardinality data, such a canonical order is provided by row and column permutations of the data matrix. In our recent work, we induce a hierarchical clustering from seriation through unidimensional representation of our observations. This linear time hierarchical classification is directly derived from the use of the Baire metric, which is simultaneously an ultrametric. In our previous work, the linear time construction of a hierarchical clustering is studied from the following viewpoint: representing the hierarchy initially in an m-adic, m = 10, tree representation, followed by decreasing m to smaller valued representations that include p-adic representations, where p is prime and m is a non-prime positive integer. This has the advantage of facilitating a more direct visualization and hence interpretation of the hierarchy. In this work we present further case studies and examples of how this approach is very advantageous for such an ultrametric topological data mapping.

Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): Ibrahim Ozbek, Irfan Siap Secret sharing schemes (SSS) offer efficient methods in protecting a secret data shared in parts by shareholders against unauthorized people. Furthermore, this sharing is formed in a way that only a predesigned minimum number of shareholders can solve the secret by using their shares. Many methods have been developed over the last decades. In this work, we present a novel (l, t + l) threshold secret sharing scheme by using error correcting codes. The security of this scheme is based on the hardness of syndrome decoding problem.

Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): Shera Marie C. Pausang, Yvette Fajardo-Lim An inspection game is a mathematical model of a situation where an inspector verifies that another party, called inspectee, adheres to certain legal rules. This paper will consider a model with one inspector and n inspectees and investigate the Nash equilibria of a multiple stage inspection game given a budget allocation. The inspector I sets a “target level” for budget allocation of each inspectee P i . The inspector decides to allocate percentage of the target level to n inspectees who work non cooperatively. In each inspection time, computations of Nash equilibria is presented. There are three cases for the inspector's budget in relation to the sum of the target levels for the inspectees. The paper will show that only the case with budget more than the sum of target levels of all inspectees can be extended into a multiple stage inspection game.

Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): Armen Vasil Petrosyan The article is devoted to the investigation of correlative properties of different discrete objects including arithmetic graphs, polyhedrons, chemical graphs, information amounts and different properties of other structures. The main difficulty of this problem is the efficient separation of equivalence classes into elements in the discrete structure. One of such methods of classification is to encode the discrete object through the properties of an arithmetic graph. The theory of arithmetic graphs is taken as a basis for encoding. Encoded polyhedral arithmetic graphs with their equivalence classes are introduced in the given examples, for which an information amount is calculated by Shannons classical formula. The results of the research reveals the correlation/interrelation between materia, energy and information.

Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): Ioan-Lucian Popa, Traian Ceauşu, Ovidiu Bagdasar The generalized exponential trichotomy (g.e.t) concept is explored for linear time-varying systems. Characterizations and relations with the notion of uniform exponential trichotomy (u.e.t) in the sense of Elaydi-Janglajew are also provided.

Abstract: Publication date: December 2016 Source:Electronic Notes in Discrete Mathematics, Volume 56 Author(s): Yury Kartynnik, Andrew Ryzhikov We study the computational complexity of several problems connected with the problems of finding a maximal distance-k matching of minimum cardinality or minimum weight. We introduce the class of k-equimatchable graphs which is an edge analogue of k-equipackable graphs. We prove that the recognition of k-equimatchable graphs is co-NP-complete for any fixed k ≥ 2 . We also prove that the problem of finding a minimum weight maximal distance-2l matching in chordal graphs is hard to approximate within a factor of ε ln V ( G ) for a fixed ε unless P = N P . Finally, we show NP-hardness of the minimum maximal induced matching problem in several restricted graph classes.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Marika Ivanova The shared broadcast tree (SBT) problem in Euclidean graphs resembles the minimum spanning tree (MST) problem, but differs from MST in the definition of the objective function. The SBT problem is known to be NP-hard. In the current work, we analyse how closely the MST-solution approximates the SBT-solution, and we prove in particular that the approximation ratio is at least 6. Further, we conduct numerical experiments comparing the MST-solution and the optimum. The results show that the cost of the MST-solution is around 20% higher than the optimal cost.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Klaus Jansen, Denis Trystram We consider the problem of scheduling parallel jobs on heterogeneous platforms. Given a set J of n jobs where each job j ∈ J is described by a pair ( p j , q j ) with a processing time p j and number q j of processors required and a set of N heterogeneous platforms P i with m i processors, the goal is to find a schedule for all jobs on the platforms minimizing the maximum completion time. The problem is directly related to a two-dimensional multi strip packing problem. Unless P = N P there is no approximation algorithm with absolute ratio better than 2 for the problem. We propose an approximation algorithm with absolute ratio 2 improving the previously best known approximation algorithms. This closes the gap between the lower bound of <2 and the best approximation ratio.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Claudia Justel, Carlos Rocha, Emanuelle Chaves In this work we present a heuristic algorithm to solve the Maximum Algebraic Connectivity Augmentation Problem (MACAP). This is an NP-complete problem (proved by Mosk-Aoyama in 2008) and consists in, given a graph, determining the smallest set of edges not belonging to it in such a way that the value of the algebraic connectivity of the augmented graph is maximum. In 2006, Ghosh and Boyd presented a heuristic procedure to solve this problem. This heuristic is an iterative method that selects one edge at a time based on the values of the components of a Fiedler vector of the graph. Our goal is to increase the value of the algebraic connectivity of a given graph by inserting edges based on the eccentricity of vertices. In order to evaluate our algorithm, computational tests comparing it with the Ghosh and Boyd procedure are presented.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Roberto Cordone, Guglielmo Lulli We review some complexity results and present a viable heuristic approach based on the Variable Neighborhood Search (VNS) framework for multimode extension of combinatorial optimization problems, such as the the Set Covering Problem (SCP) and the Covering Location Problem (CLP).

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Alberto Ceselli, Marco Premoli, Stefano Secci Major interest is currently given to the integration of clusters of virtualization servers, also referred to as ‘cloudlets’, into the access network to allow higher performance and reliability in the access to mobile edge computing services. We tackle the facility location problem arising in the planning of these networks. Due to the complexity of the network topology, and the number of operational constraints, methods from the literature are hard to adapt. While in [A. Ceselli, M. Premoli, S. Secci, “Cloudlet Network Design Optimization”, in Proc. of IFIP Networking 2015, 20–25 May, 2015, Toulouse, France] we discussed the application issues, considering a real test case, in this paper we focus on the algorithmic ones, providing matheuristics solution algorithms for the static case, and an experimental insight on their computational behavior.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Roberto Aringhieri, Andrea Grosso, Pierre Hosteins, Rosario Scatamacchia We discuss how to develop efficient heuristics for the distance based critical node problem, that is the problem of deleting a subset of nodes from a graph G in such a way that the distance between each pair of nodes is as large as possible.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Valentina Cacchiani, Feng Jiang, Paolo Toth We study the Train Timetabling Problem (TTP) of the high-speed trains at the Chinese railways. TTP calls for determining, in the planning phase, an optimal schedule for a given set of trains, while satisfying track capacity occupation constraints. In this work, we are given on input a set of feasible timetables for the trains already planned along a double-track high-speed line, and the main goal consists of scheduling as many additional trains as possible. Beside the main goal, a second objective is to obtain a regular schedule, i.e. a schedule showing regularity in the train frequency. We model TTP on a time-space graph and propose a heuristic algorithm for it. Preliminary computational results on real-world instances of the high-speed line from Beijing to Shanghai in China are reported.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Maurizio Bruglieri, Roberto Cordone We study the computational complexity and approximability for the problem of partitioning a vertex-weighted undirected graph into p connected subgraphs with minimum gap between the largest and the smallest vertex weights.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Isabella Lari, Justo Puerto, Federica Ricca, Andrea Scozzari In this paper we provide polynomial time algorithms for the problem of finding uniform centered partitions of a tree, that is, partitions that are as balanced as possible either w.r.t. the costs or to the weights of their components.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Becky Callaghan, Saïd Salhi, Gábor Nagy Drezner's optimal algorithm for the p-centre problem is an elegant but somewhat slow method. We suggest some technical enhancements that significantly improve the method's efficiency.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Gustavo Dias, Leo Liberti Given an integer K and a simple edge-weighted undirected graph G = ( V , E ) , the Distance Geometry Problem questions the existence of a vertex realization function V → R K such that each vertex pair adjacent to an edge is placed at a distance which is equal to the edge weight. This problem has many applications to science and engineering, and many methods have been proposed to solve it. We propose some new formulation-based methods.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Jia Liu, Abdel Lisser, Zhiping Chen This paper discusses the geometric programs with joint probabilistic constraints. When the coefficients are normally distributed and independent of each other, we approximate the problem by using piecewise linear function and transform the approximation problem into a geometric program. We prove that this approximation method provides a lower bound, and we use Bonferroni approximation to find an upper bound.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Leo Liberti, Pierre-Louis Poirion, Vu Khac Ky A celebrated result of Johnson and Lindenstrauss asserts that, in high enough dimensional spaces, Euclidean distances defined by a finite set of points are approximately preserved when these points are projected to a certain lower dimensional space. We show that the distance from a point to a convex set is another approximate invariant, and leverage this result to approximately solve linear programs with a logarithmic number of rows.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Pierre Hosteins, Roberto Cordone, Giovanni Righini We study a prize-collecting single machine scheduling problem with hard deadlines, where the objective is to minimise the difference between the total tardiness and the total prize of selected jobs. This problem is motivated by industrial applications, both as a standalone model and as a pricing problem for column generation approaches to parallel machine scheduling problems. It is handled through the use of exact approaches, in the form of a Branch and Bound (B&B) algorithm and an Integer Linear Programming (ILP) formulation. The B&B and ILP formulation are compared in their efficiency on randomly generated benchmark instances.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Marco Casazza, Alberto Ceselli Bin Packing Problems with Item Fragmentation (BPPIF) are variants of classical Bin Packing in which items can be split at a price. We extend BPPIF models from the literature by allowing a set of heterogeneous bins, each potentially having a different cost and capacity. We introduce extended formulations and column generation algorithms to obtain good bounds with reasonable computing effort. We test our algorithms on instances from the literature. Our experiments prove our approach to be more effective than state-of-the-art general purpose solvers.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Maurizio Naldi, Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy This work addresses a multi agent allocation problem in which multiple departments compete for shares of a company budget. Each department has its own portfolio of projects with given expected profits and costs and selects an optimal subset of its projects consuming its assigned budget share. Besides considering the total profit of the company a central decision maker should also take fairness issues into account. Thus, we introduce an equity criterion based on maximin fairness. The resulting trade-off between total profit and fairness indicators is studied in this contribution. To this purpose a bicriteria ILP model is presented where one of the objectives is the maximization of the overall profit and the other is the maximization of the minimum budget allocated to one of the departments. We perform an experimental analysis showing a nearly perfect linear anticorrelation between profit and fairness index values.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Luca Mencarelli, Claudia D'Ambrosio, Angelo Di Zio, Silvano Martello We propose heuristic algorithms for the multiple non-linear knapsack problem with separable non-convex profit and weight functions. First, we design a fast constructive algorithm that provides good initial solutions. Secondly, we improve the quality of these solutions through local search procedures. We compare the proposed methods with exact and heuristic algorithms for mixed integer non-linear programming problems, proving that our approach provides good-quality solutions in smaller CPU time.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Marianna De Santis In this work, we propose a strategy for computing valid lower bounds for a specific class of integer nonlinear programming problems, that includes integer quadratic programming problems. This strategy is used within a branch-and-bound scheme. Experimental results for randomly generated instances show that, in the quadratic case, the devised branch-and-bound method compares favorably to the MIQP solver of CPLEX 12.6 when the number of constraints is small.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Borzou Rostami, Federico Malucelli In this paper we propose a new lower bounding procedure for the Quadratic Assignment Problem based on a generalization of the well-known Gilomore-Lawler procedure for a higher order reformulation. Computational results on some benchmark instances show the strength of the new approach compared with other lower bounds.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Jean-Paul Doignon, Samuel Fiorini, Selim Rexhep Let P be a finite poset. By definition, the linear extension polytope of P has as vertices the characteristic vectors of all linear extensions of P. In case P is an antichain, it is the linear ordering polytope. The linear extension polytope appears in combinatorial optimization in the context of scheduling with precedence constraints, see e.g. [A. Schulz, Polytopes and Scheduling, Phd Thesis, TU Berlin, 1996]. It seems also relevant to order theory, being similar in spirit to other constructions such as the linear extension graph, see e.g. [M. Massow, Linear extension graphs and linear extension diameter, PhD thesis, TU Berlin, 2009]. In this work, we relate the combinatorial properties of the poset P to the polyhedral structure of its linear extension polytope. Of particular interest is a natural relaxation of the linear extension polytope. We prove that the relaxation is exact in case P is a width-2 poset, and formulate a conjecture stating exactly when the relaxation is exact.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Evellyn Cavalcante, Johan Oppen, Phillippe Samer, Sebastián Urrutia We investigate an optimization problem in container ports, for which previous models based on generalized set partitioning formulations have been studied. We describe two combinatorial relaxations based on computing maximum weighted matchings in suitable graphs, providing dual bounds and a variable reduction technique.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Maurizio Bruglieri, Simona Mancini, Ferdinando Pezzella, Ornella Pisacane A new MILP formulation for the Green Vehicle Routing Problem is introduced where the visits to the Alternative Fuel Stations (AFSs) are only implicitly considered. The number of variables is also reduced by pre-computing for each couple of customers an efficient set of AFSs, only given by those that may be actually used in an optimal solution. Numerical experiments on benchmark instances show that our model outperforms the previous ones proposed in the literature.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Paolo Gianessi, Alberto Ceselli, Lucas Létocart, Roberto Wolfler Calvo We present a Branch&Price&Cut algorithm for the Vehicle Routing Problem with Intermediate Replenishment Facilities that relies on a new extended formulation. The aim of this latter is to tackle symmetry issues by dropping out the vehicle index. The linear relaxation is further strengthened by adding valid inequalities.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Anja Fischer, J. Fabian Meier, Ulrich Pferschy, Rostislav Staněk We consider the Symmetric Quadratic Traveling Salesman Problem (SQTSP), which is a generalization of the classical TSP where each sequence of two consecutive edges in the tour gives rise to a certain cost value. For the standard linearization we apply a purely integral subtour elimination strategy which outperforms the usual fractional separation routine in computational experiments, even if strengthened inequalities are added. The maximization version of the problem is introduced and turns out to benefit from this strengthening. Finally, a new geometry-based linearization with only a linear number of additional variables is presented for the Angular Metric TSP and variants thereof. It is faster than the other approaches for medium-sized instances of one of the variants.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Ana Silva, Cláudia Linhares Sales A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of G is the maximum integer b(G) for which G has a b-coloring with b(G) colors. A graph G is b-continuous if G has a b-coloring with k colors, for every integer k in the interval [ χ ( G ) , b ( G ) ] . It is known that not all graphs are b-continuous. Here, we show that if G has girth at least 10, then G is b-continuous.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Christoph Brause, Trung Duy Doan, Ingo Schiermeyer An edge-coloured graph G is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a graph G, denoted by pc(G), is the smallest number of colours that are needed in order to make G properly connected. In this paper we consider sufficient conditions in terms of connectivity and forbidden subgraphs, implying a graph to have proper connection number 2.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Christoph Brause, Trung Duy Doan, Ingo Schiermeyer An edge-coloured graph G is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a graph G, denoted by pc(G), is the smallest number of colours that are needed in order to make G properly connected. In this paper we consider sufficient conditions in terms of the ratio between minimum degree and order of a 2-connected graph G implying that G has proper connection number 2.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Parinya Chalermsook, Daniel Vaz We prove a tight connection between two important notions in combinatorial optimization. Let G be a graph class (i.e. a subset of all graphs) and r ( G ) = sup G ∈ G χ f ( G ) ω ( G ) where χ f ( G ) and ω ( G ) are the fractional chromatic number and clique number of G respectively. In this note, we prove that r ( G ) tightly captures the integrality gap of the LP relaxation with clique constraints for the Maximum Weight Independent Set (MWIS) problem. Our proof uses standard applications of multiplicative weight techniques, so it is algorithmic: Any algorithm for rounding the LP can be turned into a fractional coloring algorithm and vice versa. We discuss immediate applications of our results in approximating the fractional chromatic number of certain classes of intersection graphs.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Sreekanth Gorla, Meghana Nasre We consider list coloring of planar graphs without cycles of length in {4, …, 8}. List coloring is a generalization of the classical vertex coloring problem where each vertex has a list of colors associated with it. The goal is to proper vertex color the graph, such that each vertex gets a color available in its list. In this note, we prove that it is possible to 3-list color planar graphs without cycles of length in {4, …, 8} and with restrictions on 9-cycles.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Ömer Can Yavuzyılmaz, Enver Kayaaslan The focus of this paper is on finding a matching in a bipartite graph such that a given subset of vertices are matched. This is called subset matching and generalizes perfect matchings. We prove a necessary and sufficient condition for the existence of a subset matching in bipartite graphs. The proof is algorithmic and based on combination of two matchings. Remarkably, the necessary and sufficient condition always holds when the subset is composed of the vertices with maximum degree. This in turn leads to a simple algorithm that finds an optimal edge coloring in bipartite graphs with no need to transform the bipartite graph into a regular one.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Christoph Brause, Trung Duy Doan, Ingo Schiermeyer In this paper we study the chromatic number of ( P 5 , K 2 , t )-free graphs with t ≥ 2 . It is still an open question whether there are polynomial (χ-binding) functions f k for k ≥ 5 such that every P k -free graph G satisfies χ ( G ) ≤ f k ( ω ( G ) ) , where P k is an induced path on k vertices. Our main result is that every ( P 5 , K 2 , t )-free graph G admits a polynomial χ-binding function. Moreover, we will present polynomial χ-binding functions for several other subclasses of P 5 -free graphs.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Pankaj Pundir, G. Ramakrishna A minimum average stretch spanning tree of a graph is a spanning tree that minimizes the average stretch. We present a necessary-and-sufficient condition for a spanning tree to be a minimum average stretch spanning tree (mast) in grid graphs and provide a linear-time algorithm to construct an mast.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Christina Büsing, Sarah Kirchner, Annika Thome We consider a constraint minimum cost flow problem and show that it is in general NP –complete. For special graph classes we give (pseudo–)polynomial algorithms.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Márcia R. Cerioli, Paloma Lima Let G be a graph and lpt(G) be the size of the smallest set S ⊆ V ( G ) such that every longest path of G has at least one vertex in S. If lpt(G) = 1, then all longest paths of G have non-empty intersection. In this work, we prove that this holds for some graph classes, including ptolemaic graphs, P 4 -sparse graphs, and starlike graphs, generalizing the existing result for split graphs.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Jochen Harant, Igor Fabrici, Stanislav Jendrol' A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that V ( C ) ≥ 2 n + 4 5 . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least 3 4 n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of G are presented if G is an essentially 4-connected planar graph of maximum degree 4 or G is an essentially 4-connected maximal planar graph.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Sascha Kurz, Xavier Molinero, Martin Olsen, Maria Serna This paper studies the complexity of computing a representation of a simple game as the intersection (union) of weighted majority games, as well as, the dimension or the codimension. We also present some examples with linear dimension and exponential codimension with respect to the number of players.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Vikas Vikram Singh, Oualid Jouini, Abdel Lisser We formulate a random bimatrix game, where the entries of the payoff matrix of each player jointly follow a multivariate elliptically symmetric distribution, as a chance-constrained game. We show that a Nash equilibrium of a chance-constrained game can be computed by solving an equivalent nonlinear complementarity problem.

Abstract: Publication date: November 2016 Source:Electronic Notes in Discrete Mathematics, Volume 55 Author(s): Dmitrii Lozovanu, Stefan Pickl We consider a class of zero-sum stochastic positional games that generalizes the deterministic antagonistic positional games with average payoffs. We prove the existence of saddle points for the considered class of games and propose an approach for determining the optimal stationary strategies of the players.