Abstract: Publication date: January 2018 Source:European Journal of Combinatorics, Volume 67 Author(s): Maria Axenovich, Daniel Gonçalves, Jonathan Rollin, Torsten Ueckerdt The induced arboricity of a graph G is the smallest number of induced forests covering the edges of G . This is a well-defined parameter bounded from above by the number of edges of G when each forest in a cover consists of exactly one edge. Not all edges of a graph necessarily belong to induced forests with larger components. For k ⩾ 1 , we call an edge k -valid if it is contained in an induced tree on k edges. The k -strong induced arboricity of G , denoted by f k ( G ) , is the smallest number of induced forests with components of sizes at least k that cover all k -valid edges in G . This parameter is highly non-monotone. However, we prove that for any proper minor-closed graph class C , and more generally for any class of bounded expansion, and any k ⩾ 1 , the maximum value of f k ( G ) for G ∈ C is bounded from above by a constant depending only on C and k . This implies that the adjacent closed vertex-distinguishing number of graphs from a class of bounded expansion is bounded by a constant depending only on the class. We further prove that f 2 ( G ) ⩽ 3 t + 1 3 for any graph G of tree-width t and that f k ( G ) ⩽ ( 2 k ) d for any graph of tree-depth d . In addition, we prove that f 2 ( G ) ⩽ 310 when G is planar.

Abstract: Publication date: Available online 24 July 2017 Source:European Journal of Combinatorics Author(s): Lars Jaffke, Hans L. Bodlaender, Pinar Heggernes, Jan Arne Telle One of the most famous algorithmic meta-theorems states that every graph property which can be defined in counting monadic second order logic (CMSOL) can be checked in linear time on graphs of bounded treewidth, which is known as Courcelle’s Theorem (Courcelle, 1990). These algorithms are constructed as finite state tree automata and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. In this paper we prove two special cases of this conjecture, first for the class of k -outerplanar graphs, which are known to have treewidth at most 3 k − 1 (Bodlaender, 1998) and for graphs of bounded treewidth without chordless cycles of length at least some constant ℓ . We furthermore show that for a proof of Courcelle’s Conjecture it is sufficient to show that all members of a graph class admit constant width tree decompositions whose bags and edges can be identified with MSOL-predicates. For graph classes that admit MSOL-definable constant width tree decompositions that have bounded degree or allow for a linear ordering of all nodes with the same parent we even give a stronger result: In that case, the counting predicates of CMSOL are not needed.

Abstract: Publication date: Available online 23 July 2017 Source:European Journal of Combinatorics Author(s): Robert Morris Many fundamental and important questions from statistical physics lead to beautiful problems in extremal and probabilistic combinatorics. One particular example of this phenomenon is the study of bootstrap percolation, which is motivated by a variety of ‘real-world’ cellular automata, such as the Glauber dynamics of the Ising model of ferromagnetism, and kinetically constrained spin models of the liquid–glass transition. In this review article, we will describe some dramatic recent developments in the theory of bootstrap percolation (and, more generally, of monotone cellular automata with random initial conditions), and discuss some potential extensions of these methods and results to other automata. In particular, we will state numerous conjectures and open problems.

Abstract: Publication date: Available online 23 July 2017 Source:European Journal of Combinatorics Author(s): F. Botler, G.O. Mota, M.T.I. Oshiro, Y. Wakabayashi A P ℓ -decomposition of a graph G is a set of pairwise edge-disjoint paths with ℓ edges that cover the edge set of G . In 1957, Kotzig proved that a 3 -regular graph admits a P 3 -decomposition if and only if it contains a perfect matching, and also asked what are the necessary and sufficient conditions for an ℓ -regular graph to admit a P ℓ -decomposition, for odd ℓ . Let g , ℓ and m be positive integers with g ≥ 3 . We prove that, (i) if ℓ is odd and m > 2 ⌊ ( ℓ − 2 ) ∕ ( g − 2 ) ⌋ , then every m ℓ -regular graph with girth at least g that contains an m -factor admits a P ℓ -decomposition; (ii) if m > ⌊ ( ℓ − 2 ) ∕ ( g − 2 ) ⌋ , then every 2 m ℓ -regular graph with girth at least g admits a P ℓ -decomposition. Furthermore, we prove that, for graphs with girth at least ℓ − 1 , statement (i) holds for every m ≥ 1 ; and observe that, statement (ii) also holds for every m ≥ 1 .

Abstract: Publication date: Available online 22 July 2017 Source:European Journal of Combinatorics Author(s): Winfried Hochstättler We transfer Tutte’s theory for analyzing the chromatic number of a graph using nowhere-zero-coflows and -flows (NZ-flows) to the dichromatic number of a digraph and define Neumann-Lara-flows (NL-flows). We prove that any digraph whose underlying (multi-)graph is 3 -edge-connected admits a NL-3-flow, and even a NL-2-flow in case the underlying graph is 4 -edge connected. We conjecture that 3 -edge-connectivity already guarantees the existence of a NL-2-flow, which, if true, would imply the 2-Color-Conjecture for planar graphs due to Víctor Neumann-Lara. Finally we present an extension of the theory to oriented matroids.

Abstract: Publication date: Available online 22 July 2017 Source:European Journal of Combinatorics Author(s): Carlos Hoppen, Hanno Lefmann, Knut Odermann Inspired by previous work of Balogh (2006), we show that, given r ≥ 5 and n large, the balanced complete bipartite graph K n ∕ 2 , n ∕ 2 is the n -vertex graph that admits the largest number of r -edge-colorings for which there is no triangle whose edges are assigned three distinct colors. Moreover, we extend this result to lower values of n when r ≥ 10 , and we provide approximate results for r ∈ { 3 , 4 } .

Abstract: Publication date: Available online 22 July 2017 Source:European Journal of Combinatorics Author(s): Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, Sebastian Siebertz The generalised colouring numbers col r ( G ) and wcol r ( G ) were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have since then found important theoretical and algorithmic applications. In this paper, we dramatically improve upon the known upper bounds for generalised colouring numbers for graphs excluding a fixed minor, from the exponential bounds of Grohe et al. to a linear bound for the r -colouring number col r and a polynomial bound for the weak r -colouring number wcol r . In particular, we show that if G excludes K t as a minor, for some fixed t ≥ 4 , then col r ( G ) ≤ t − 1 2 ( 2 r + 1 ) and wcol r ( G ) ≤ r + t − 2 t − 2 ( t − 3 ) ( 2 r + 1 ) ∈ O ( r t − 1 ) . In the case of graphs G of bounded genus g , we improve the bounds to col r ( G ) ≤ ( 2 g + 3 ) ( 2 r + 1 ) (and even col r ( G ) ≤ 5 r + 1 if g = 0 , i.e. if G is planar) and wcol r ( G ) ≤ ( 2 g + r + 2 2 ) ( 2 r + 1 ) .

Abstract: Publication date: Available online 22 July 2017 Source:European Journal of Combinatorics Author(s): Juanjo Rué, Oriol Serra, Lluis Vena We provide asymptotic counting for the number of subsets of given size which are free of certain configurations in finite groups. Applications include sets without solutions to equations in non-abelian groups, and linear configurations in abelian groups defined from group homomorphisms. The results are obtained by combining the methodology of hypergraph containers joint with arithmetic removal lemmas. Random sparse versions and threshold probabilities for existence of configurations in sets of given density are presented as well.

Abstract: Publication date: Available online 21 July 2017 Source:European Journal of Combinatorics Author(s): Zdeněk Dvořák, Ken-ichi Kawarabayashi We prove that every triangle-free graph of tree-width t has chromatic number at most ⌈ ( t + 3 ) ∕ 2 ⌉ , and demonstrate that this bound is tight. The argument also establishes a connection between coloring graphs of tree-width t and on-line coloring of graphs of path-width t .

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Steve Butler, Ron Graham, Catherine H. Yan We consider a generalization of parking functions to parking distributions on trees and study the unordered version and a q -analogue. We give an efficient way to form generating functions to compute these values and establish the positivity and log-concavity of a related polynomial. We also connect the unordered parking distributions on caterpillars (trees whose removal of leaves results in a path) to restricted lattice walks.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Neslihan Gügümcü, Louis H. Kauffman In this paper we construct new invariants of knotoids including the odd writhe, the parity bracket polynomial, the affine index polynomial and the arrow polynomial, and give an introduction to the theory of virtual knotoids. The invariants in this paper are defined for both classical and virtual knotoids in analogy to corresponding invariants of virtual knots. We show that knotoids in S 2 have symmetric affine index polynomials. The affine index polynomial and the arrow polynomial provide bounds on the height (minimum crossing distance between endpoints) of a knotoid in S 2 .

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Felix Breuer, Dennis Eichhorn, Brandt Kronholm In this paper, we use a branch of polyhedral geometry, Ehrhart theory, to expand our combinatorial understanding of congruences for partition functions. Ehrhart theory allows us to give a new decomposition of partitions, which in turn allows us to define statistics called supercranks that combinatorially witness every instance of divisibility of p ( n , 3 ) by any prime m ≡ − 1 ( mod 6 ) , where p ( n , 3 ) is the number of partitions of n into three parts. A rearrangement of lattice points allows us to demonstrate with explicit bijections how to divide these sets of partitions into m equinumerous classes. The behavior for primes m ′ ≡ 1 ( mod 6 ) is also discussed.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Ferenc Bencs The adjoint polynomial of G is h ( G , x ) = ∑ k = 1 n ( − 1 ) n − k a k ( G ) x k , where a k ( G ) denotes the number of ways one can cover all vertices of the graph G by exactly k disjoint cliques of G . In this paper we show the adjoint polynomial of a graph G is a simple transformation of the independence polynomial of another graph G ̂ . This enables us to use the rich theory of independence polynomials to study the adjoint polynomials. In particular we give new proofs of several theorems of R. Liu and P. Csikvári.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): André Kündgen, Binlong Li, Carsten Thomassen A closed curve in the Freudenthal compactification G of an infinite locally finite graph G is called a Hamiltonian curve if it meets every vertex of G exactly once (and hence it meets every end at least once). We prove that G has a Hamiltonian curve if and only if every finite vertex set of G is contained in a cycle of G . We apply this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example, Barnette’s conjecture (that every finite planar cubic 3 -connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3 -connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3 -connected bipartite graph with a nowhere-zero 3 -flow (with no restriction on the number of ends) has a Hamiltonian curve. However, there are 7 -ended planar cubic 3 -connected bipartite graphs that do not have a Hamiltonian curve.

Abstract: Publication date: Available online 18 July 2017 Source:European Journal of Combinatorics Author(s): Karim Adiprasito We construct, for every dimension d ≥ 3 , polytopal spheres S for which neither S nor its dual S ∗ contain 2-faces that are triangles. This answers the topological formulation of a problem of Kalai, Kleinschmidt and Meisinger.

Abstract: Publication date: Available online 18 July 2017 Source:European Journal of Combinatorics Author(s): François Dross, Mickael Montassier, Alexandre Pinlou An ( F , F d ) -partition of a graph is a vertex-partition into two sets F and F d such that the graph induced by F is a forest and the one induced by F d is a forest with maximum degree at most d . We prove that every triangle-free planar graph admits an ( F , F 5 ) -partition. Moreover we show that if for some integer d there exists a triangle-free planar graph that does not admit an ( F , F d ) -partition, then it is an NP-complete problem to decide whether a triangle-free planar graph admits such a partition.

Abstract: Publication date: Available online 17 July 2017 Source:European Journal of Combinatorics Author(s): Martin Balko, Pavel Valtr A classical conjecture of Erdős and Szekeres states that, for every integer k ≥ 2 , every set of 2 k − 2 + 1 points in the plane in general position contains k points in convex position. In 2006, Peters and Szekeres introduced the following stronger conjecture: every red-blue coloring of the edges of the ordered complete 3-uniform hypergraph on 2 k − 2 + 1 vertices contains an ordered subhypergraph with k vertices and k − 2 edges, which is a union of a red monotone path and a blue monotone path that are vertex disjoint except for their two common end-vertices. Applying a state of art SAT solver, we refute the conjecture of Peters and Szekeres. We also apply techniques of Erdős, Tuza, and Valtr to refine the Erdős–Szekeres conjecture in order to tackle it with SAT solvers.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Tony Huynh, Sang-il Oum, Maryam Verdian-Rizi An even-cycle decomposition of a graph G is a partition of E ( G ) into cycles of even length. Evidently, every Eulerian bipartite graph has an even-cycle decomposition. Seymour (1981) proved that every 2-connected loopless Eulerian planar graph with an even number of edges also admits an even-cycle decomposition. Later, Zhang (1994) generalized this to graphs with no K 5 -minor. Our main theorem gives sufficient conditions for the existence of even-cycle decompositions of graphs in the absence of odd minors. Namely, we prove that every 2-connected loopless Eulerian odd- K 4 -minor-free graph with an even number of edges has an even-cycle decomposition. This is best possible in the sense that ‘odd- K 4 -minor-free’ cannot be replaced with ‘odd- K 5 -minor-free.’ The main technical ingredient is a structural characterization of the class of odd- K 4 -minor-free graphs, which is due to Lovász, Seymour, Schrijver, and Truemper.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Sizhong Zhou, Zhiren Sun, Zurun Xu Let G be a digraph with vertex set V ( G ) and arc set E ( G ) . Let m , r , k be three positive integers, and let f = ( f − , f + ) be a pair of nonnegative integer-valued functions defined on V ( G ) with f ( x ) ≥ ( k + 1 ) r for all x ∈ V ( G ) . Let H 1 , H 2 , … , H k be k vertex disjoint m r -subdigraphs of G . In this paper, it is proved that every ( 0 , m f − ( m − 1 ) r ) -digraph has a ( 0 , f ) -factorization r -orthogonal to every H i ( i = 1 , 2 , … , k ).

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): S.V. Avgustinovich, A.E. Frid, S. Puzynina An infinite permutation is a linear ordering of the set of natural numbers. An infinite permutation can be defined by a sequence of real numbers where only the order of elements is taken into account; such sequence of reals is called a representative of a permutation. In this paper we consider infinite permutations which possess an equidistributed representative on [ 0 , 1 ] (i.e., such that the prefix frequency of elements from each interval exists and is equal to the length of this interval), and we call such permutations equidistributed. Similarly to infinite words, a complexity p ( n ) of an infinite permutation is defined as a function counting the number of its subpermutations of length n . We show that, unlike for permutations in general, the minimal complexity of an equidistributed permutation α is p α ( n ) = n , establishing an analog of Morse and Hedlund theorem. The class of equidistributed permutations of minimal complexity coincides with the class of so-called Sturmian permutations, directly related to Sturmian words.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Zoltán L. Blázsik, Zoltán Lóránt Nagy We determine the partition dimension of the incidence graph G ( Π q ) of the projective plane Π q up to a constant factor 2 as ( 2 + o ( 1 ) ) log 2 q ≤ pd ( G ( Π q ) ) ≤ ( 4 + o ( 1 ) ) log 2 q .

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Haimiao Chen Given a finite group Γ , a regular t -balanced Cayley map ( RBCM t for short) is a regular Cayley map CM ( G , Ω , ρ ) such that ρ ( ω ) − 1 = ρ t ( ω ) for all ω ∈ Ω . In this paper, we clarify a connection between quotients of polynomial rings and RBCM t ’s on abelian groups, so as to propose a new approach for classifying RBCM t ’s. We obtain many new results, in particular, a complete classification for RBCM t ’s on abelian 2-groups.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Nicolas Bonichon, Mireille Bousquet-Mélou, Paul Dorbec, Claire Pennarun The number of planar Eulerian maps with n edges is well-known to have a simple expression. But what is the number of planar Eulerian orientations with n edges' This problem appears to be a difficult one. To approach it, we define and count families of subsets and supersets of planar Eulerian orientations, indexed by an integer k , that converge to the set of all planar Eulerian orientations as k increases. The generating functions of our subsets can be characterized by systems of polynomial equations, and are thus algebraic. The generating functions of our supersets are characterized by polynomial systems involving divided differences, as often occurs in map enumeration. We prove that these series are algebraic as well. We obtain in this way lower and upper bounds on the growth rate of planar Eulerian orientations, which appears to be around 12.5.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Julien Cassaigne, Juhani Karhumäki, Aleksi Saarela An extension of abelian complexity, so called k -abelian complexity, has been considered recently in a number of articles. This paper considers two particular aspects of this extension: First, how much the complexity can increase when moving from a level k to the next one. Second, how much the complexity of a given word can fluctuate. For both questions we give optimal solutions.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos For every r ∈ N , let θ r denote the graph with two vertices and r parallel edges. The θ r -girth of a graph G is the minimum number of edges of a subgraph of G that can be contracted to θ r . This notion generalizes the usual concept of girth which corresponds to the case r = 2 . In Kühn and Osthus (2003), Kühn and Osthus showed that graphs of sufficiently large minimum degree contain clique-minors whose order is an exponential function of their girth. We extend this result for the case of θ r -girth and we show that the minimum degree can be replaced by some connectivity measurement. As an application of our results, we prove that, for every fixed r , graphs excluding as a minor the disjoint union of k θ r ’s have treewidth O ( k ⋅ log k ) .

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Nathan Lindzey A perfect matching of a complete graph K 2 n is a 1-regular subgraph that contains all the vertices. Two perfect matchings intersect if they share an edge. It is known that if F is family of intersecting perfect matchings of K 2 n , then F ≤ ( 2 ( n − 1 ) − 1 ) ! ! and if equality holds, then F = F i j where F i j is the family of all perfect matchings of K 2 n that contain some fixed edge i j . We give a short algebraic proof of this result, resolving a question of Godsil and Meagher. Along the way, we show that if a family F is non-Hamiltonian, that is, m ∪ m ′ ≇ C 2 n for any m , m ′ ∈ F , then F ≤ ( 2 ( n − 1 ) − 1 ) ! ! . Our results make ample use of a symmetric commutative association scheme arising from the Gelfand pair ( S 2 n , S 2 ≀ S n ) . We give an exposition of a few new interesting objects that live in this scheme as they pertain to our results.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Vadim Lozin, Viktor Zamaraev We show that the number of labelled P 7 -free bipartite graphs with n vertices grows as n Θ ( n ) . This resolves an open problem posed by Allen (2009), and completes the description of speeds of monogenic classes of bipartite graphs. Our solution is based on a new decomposition scheme of bipartite graphs, which is of independent interest.

Abstract: Publication date: October 2017 Source:European Journal of Combinatorics, Volume 65 Author(s): Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos A graph H is an immersion of a graph G if H can be obtained by some subgraph G after lifting incident edges. We prove that there is a polynomial function f : N × N → N , such that if H is a connected planar sub-cubic graph on h > 0 edges, G is a graph, and k is a non-negative integer, then either G contains k vertex/edge-disjoint subgraphs, each containing H as an immersion, or G contains a set F of f ( k , h ) vertices/edges such that G ∖ F does not contain H as an immersion.

Abstract: Publication date: August 2017 Source:European Journal of Combinatorics, Volume 64 Author(s): Hao Chen, Arnau Padrol In this paper we study various scribability problems for polytopes. We begin with the classical k -scribability problem proposed by Steiner and generalized by Schulte, which asks about the existence of d -polytopes that cannot be realized with all k -faces tangent to a sphere. We answer this problem for stacked and cyclic polytopes for all values of d and k . We then continue with the weak scribability problem proposed by Grünbaum and Shephard, for which we complete the work of Schulte by presenting non weakly circumscribable 3 -polytopes. Finally, we propose new ( i , j ) -scribability problems, in a strong and a weak version, which generalize the classical ones. They ask about the existence of d -polytopes that cannot be realized with all their i -faces “avoiding” the sphere and all their j -faces “cutting” the sphere. We provide such examples for all the cases where j − i ≤ d − 3 .

Abstract: Publication date: August 2017 Source:European Journal of Combinatorics, Volume 64 Author(s): Jin-Xin Zhou, Mi-Mi Zhang A graph with a cyclic group of automorphisms acting semiregularly on the vertices with two orbits is called a bi-circulant. A graph is half-arc-transitive if it is both vertex-transitive and edge-transitive but not arc-transitive. Then we say that a half-arc-transitive graph is half-arc-regular if its full automorphism group acts regularly on its edges. It is known that the smallest possible valency of a half-arc-transitive bi-circulant is 6 . In this paper, a classification is given of connected half-arc-regular bi-circulants of valency 6 . As byproduct, we construct the first known infinite family of half-arc-transitive bi-circulants of valency 6 .

Abstract: Publication date: August 2017 Source:European Journal of Combinatorics, Volume 64 Author(s): Tri Lai MacMahon proved a simple product formula for the generating function of plane partitions fitting in a given box. The theorem implies a q -enumeration of lozenge tilings of a semi-regular hexagon on the triangular lattice. In this paper we generalize MacMahon’s classical theorem by q -enumerating lozenge tilings of a new family of hexagons with four adjacent triangles removed from their boundary.

Abstract: Publication date: August 2017 Source:European Journal of Combinatorics, Volume 64 Author(s): Alejandra Ramos Rivera, Primož Šparl A graph is said to be half-arc-transitive if its automorphism group acts transitively on its vertex set and its edge set, but not on its arc set. In 1970 I. Z. Bouwer constructed an infinite family of vertex- and edge-transitive graphs for each even valence greater than 2 and proved that a subfamily of the constructed graphs, containing one graph for each even valence greater than 2, consists of half-arc-transitive graphs. In a recent paper Conder and Žitnik gave a complete classification of the half-arc-transitive Bouwer graphs. In this paper we generalize the Bouwer graphs to obtain a much larger family of vertex- and edge-transitive graphs, containing almost all so-called tightly attached quartic half-arc-transitive graphs. We give a complete classification of the half-arc-transitive members of this new family of graphs. All half-arc-transitive members are tightly attached.

Abstract: Publication date: August 2017 Source:European Journal of Combinatorics, Volume 64 Author(s): Laura Gellert, Raman Sanyal Bidirected graphs generalize directed and undirected graphs in that edges are oriented locally at every node. The natural notion of the degree of a node that takes into account (local) orientations is that of net-degree. In this paper, we extend the following four topics from (un)directed graphs to bidirected graphs: – Erdős–Gallai-type results: characterization of net-degree sequences, – Havel–Hakimi-type results: complete sets of degree-preserving operations, – Extremal degree sequences: characterization of uniquely realizable sequences, and – Enumerative aspects: counting formulas for net-degree sequences. To underline the similarities and differences to their (un)directed counterparts, we briefly survey the undirected setting and we give a thorough account for digraphs with an emphasis on the discrete geometry of degree sequences. In particular, we determine the tight and uniquely realizable degree sequences for directed graphs.

Abstract: Publication date: August 2017 Source:European Journal of Combinatorics, Volume 64 Author(s): Mark S. MacLean, Štefko Miklavič Let Γ denote a bipartite distance-regular graph with diameter D ≥ 4 and valency k ≥ 3 . Let X denote the vertex set of Γ , and let A denote the adjacency matrix of Γ . For x ∈ X and for 0 ≤ i ≤ D , let Γ i ( x ) denote the set of vertices in X that are distance i from vertex x . Define a parameter Δ 2 in terms of the intersection numbers by Δ 2 = ( k − 2 ) ( c 3 − 1 ) − ( c 2 − 1 ) p 22 2 . For x ∈ X let T = T ( x ) denote the subalgebra of Mat X ( C ) generated by A , E 0 ∗ , E 1 ∗ , … , E D ∗ , where for 0 ≤ i ≤ D , E i ∗ represents the projection onto the i th subconstituent of Γ with respect to x . We refer to T as the Terwilliger algebra of Γ with respect to x . An irreducible T -module W is said to be thin whenever dim ( E i ∗ W ) ≤ 1 for 0 ≤ i ≤ D . By the endpoint of an irreducible T -module W we mean min { i... PubDate: 2017-07-08T02:47:52Z

Abstract: Publication date: August 2017 Source:European Journal of Combinatorics, Volume 64 Author(s): Ruixue Zhang, Fengming Dong In this paper, we present some properties on chromatic polynomials of hypergraphs which do not hold for chromatic polynomials of graphs. We first show that chromatic polynomials of hypergraphs have all integers as their zeros and contain dense real zeros in the set of real numbers. We then prove that for any multigraph G = ( V , E ) , the number of totally cyclic orientations of G is equal to the value of P ( H G , − 1 ) , where P ( H G , λ ) is the chromatic polynomial of a hypergraph H G which is constructed from G . Finally we show that the multiplicity of root “ 0 ” of P ( H , λ ) may be at least 2 for some connected hypergraphs H , and the multiplicity of root “ 1 ” of P ( H , λ ) may be 1 for some connected and separable hypergraphs H and may be 2 for some connected and non-separable hypergraphs H .

Abstract: Publication date: August 2017 Source:European Journal of Combinatorics, Volume 64 Author(s): Agelos Georgakopoulos We classify the planar cubic Cayley graphs of connectivity 2, providing an explicit presentation and embedding for each of them. Combined with Georgakopoulos (2017) this yields a complete description of all planar cubic Cayley graphs.

Abstract: Publication date: June 2017 Source:European Journal of Combinatorics, Volume 63 Author(s): Jianfeng Hou, Shufei Wu, Guiying Yan A bisection of a graph is a partition of its vertex set into two sets which differ in size by at most 1. In this paper, we consider bisections of directed graphs such that both directions of the directed cuts contain many arcs. Let D be a directed graph with minimum outdegree δ ≥ 2 and m arcs. We show that if δ is even, then D has a bisection V ( D ) = V 1 ∪ V 2 such that min { e ( V 1 , V 2 ) , e ( V 2 , V 1 ) } ≥ ( δ 4 ( δ + 1 ) + o ( 1 ) ) m , where e ( V i , V j ) denotes the number of arcs of D from V i to V j for i ≠ j and i , j = 1 , 2 . If the underlying graph of D does not contain cycles of length 4, then we show that D admits a bisection V ( D ) = V 1 ∪ V 2 such that min { e ( V 1 , V 2 ) , e ( V 2 , V 1 ) } ≥ ( 1 / 4 + o ( 1 ) ) m .

Abstract: Publication date: June 2017 Source:European Journal of Combinatorics, Volume 63 Author(s): Carolyn Chun, Deborah Chun, Steven D. Noble We prove a splitter theorem for tight multimatroids, generalizing the corresponding result for matroids, obtained independently by Brylawski and Seymour. Further corollaries give splitter theorems for delta-matroids and ribbon graphs.

Abstract: Publication date: June 2017 Source:European Journal of Combinatorics, Volume 63 Author(s): Catherine Greenhill, Mikhail Isaev, Matthew Kwan, Brendan D. McKay We give an asymptotic expression for the expected number of spanning trees in a random graph with a given degree sequence d = ( d 1 , … , d n ) , provided that the number of edges is at least n + 1 2 d max 4 , where d max is the maximum degree. A key part of our argument involves establishing a concentration result for a certain family of functions over random trees with given degrees, using Prüfer codes.

Abstract: Publication date: June 2017 Source:European Journal of Combinatorics, Volume 63 Author(s): Dan Hefetz, Michael Krivelevich, Wei En Tan We study two types of two player, perfect information games with no chance moves, played on the edge set of the binomial random graph G ( n , p ) . In each round of the ( 1 : q ) Waiter–Client Hamiltonicity game, the first player, called Waiter, offers the second player, called Client, q + 1 edges of G ( n , p ) which have not been offered previously. Client then chooses one of these edges, which he claims, and the remaining q edges go back to Waiter. Waiter wins this game if by the time every edge of G ( n , p ) has been claimed by some player, the graph consisting of Client’s edges is Hamiltonian; otherwise Client is the winner. Client–Waiter games are defined analogously, the main difference being that Client wins the game if his graph is Hamiltonian and Waiter wins otherwise. In this paper we determine a sharp threshold for both games. Namely, for every fixed positive integer q , we prove that the smallest edge probability p for which a.a.s. Waiter has a winning strategy for the ( 1 : q ) Waiter–Client Hamiltonicity game is ( 1 + o ( 1 ) ) log n / n , and the smallest p for which a.a.s. Client has a winning strategy for the ( 1 : q ) Client–Waiter Hamiltonicity game is ( q + 1 + o ( 1 ) ) log n / n .

Abstract: Publication date: June 2017 Source:European Journal of Combinatorics, Volume 63 Author(s): Dongryul Kim The Golomb–Welch conjecture states that there are no perfect e -error-correcting codes in Z n for n ≥ 3 and e ≥ 2 . In this note, we prove the nonexistence of perfect 2 -error-correcting codes for a certain class of n , which is expected to be infinite. This result further substantiates the Golomb–Welch conjecture.