for Journals by Title or ISSN
for Articles by Keywords
help
  Subjects -> MATHEMATICS (Total: 879 journals)
    - APPLIED MATHEMATICS (71 journals)
    - GEOMETRY AND TOPOLOGY (19 journals)
    - MATHEMATICS (651 journals)
    - MATHEMATICS (GENERAL) (42 journals)
    - NUMERICAL ANALYSIS (19 journals)
    - PROBABILITIES AND MATH STATISTICS (77 journals)

MATHEMATICS (651 journals)                  1 2 3 4 | Last

Showing 1 - 200 of 538 Journals sorted alphabetically
Abakós     Open Access   (Followers: 3)
Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg     Hybrid Journal   (Followers: 2)
Academic Voices : A Multidisciplinary Journal     Open Access   (Followers: 2)
Accounting Perspectives     Full-text available via subscription   (Followers: 8)
ACM Transactions on Algorithms (TALG)     Hybrid Journal   (Followers: 16)
ACM Transactions on Computational Logic (TOCL)     Hybrid Journal   (Followers: 4)
ACM Transactions on Mathematical Software (TOMS)     Hybrid Journal   (Followers: 6)
ACS Applied Materials & Interfaces     Full-text available via subscription   (Followers: 21)
Acta Applicandae Mathematicae     Hybrid Journal   (Followers: 1)
Acta Mathematica     Hybrid Journal   (Followers: 11)
Acta Mathematica Hungarica     Hybrid Journal   (Followers: 2)
Acta Mathematica Scientia     Full-text available via subscription   (Followers: 5)
Acta Mathematica Sinica, English Series     Hybrid Journal   (Followers: 5)
Acta Mathematica Vietnamica     Hybrid Journal  
Acta Mathematicae Applicatae Sinica, English Series     Hybrid Journal  
Advanced Science Letters     Full-text available via subscription   (Followers: 7)
Advances in Applied Clifford Algebras     Hybrid Journal   (Followers: 3)
Advances in Calculus of Variations     Hybrid Journal   (Followers: 2)
Advances in Catalysis     Full-text available via subscription   (Followers: 5)
Advances in Complex Systems     Hybrid Journal   (Followers: 7)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 15)
Advances in Decision Sciences     Open Access   (Followers: 4)
Advances in Difference Equations     Open Access   (Followers: 1)
Advances in Fixed Point Theory     Open Access   (Followers: 5)
Advances in Geosciences (ADGEO)     Open Access   (Followers: 10)
Advances in Linear Algebra & Matrix Theory     Open Access   (Followers: 1)
Advances in Materials Sciences     Open Access   (Followers: 16)
Advances in Mathematical Physics     Open Access   (Followers: 5)
Advances in Mathematics     Full-text available via subscription   (Followers: 10)
Advances in Numerical Analysis     Open Access   (Followers: 4)
Advances in Operations Research     Open Access   (Followers: 11)
Advances in Porous Media     Full-text available via subscription   (Followers: 4)
Advances in Pure and Applied Mathematics     Hybrid Journal   (Followers: 5)
Advances in Pure Mathematics     Open Access   (Followers: 4)
Advances in Science and Research (ASR)     Open Access   (Followers: 6)
Aequationes Mathematicae     Hybrid Journal   (Followers: 2)
African Journal of Educational Studies in Mathematics and Sciences     Full-text available via subscription   (Followers: 5)
African Journal of Mathematics and Computer Science Research     Open Access   (Followers: 4)
Afrika Matematika     Hybrid Journal   (Followers: 1)
Air, Soil & Water Research     Open Access   (Followers: 7)
AKSIOMA Journal of Mathematics Education     Open Access   (Followers: 1)
Algebra and Logic     Hybrid Journal   (Followers: 3)
Algebra Colloquium     Hybrid Journal   (Followers: 4)
Algebra Universalis     Hybrid Journal   (Followers: 2)
Algorithmic Operations Research     Full-text available via subscription   (Followers: 5)
Algorithms     Open Access   (Followers: 11)
Algorithms Research     Open Access   (Followers: 1)
American Journal of Biostatistics     Open Access   (Followers: 9)
American Journal of Computational and Applied Mathematics     Open Access   (Followers: 4)
American Journal of Mathematical Analysis     Open Access  
American Journal of Mathematics     Full-text available via subscription   (Followers: 7)
American Journal of Operations Research     Open Access   (Followers: 5)
American Mathematical Monthly     Full-text available via subscription   (Followers: 6)
An International Journal of Optimization and Control: Theories & Applications     Open Access   (Followers: 7)
Analele Universitatii Ovidius Constanta - Seria Matematica     Open Access   (Followers: 1)
Analysis     Hybrid Journal   (Followers: 2)
Analysis and Applications     Hybrid Journal   (Followers: 1)
Analysis and Mathematical Physics     Hybrid Journal   (Followers: 3)
Analysis Mathematica     Full-text available via subscription  
Annales Mathematicae Silesianae     Open Access  
Annales mathématiques du Québec     Hybrid Journal   (Followers: 4)
Annales UMCS, Mathematica     Open Access   (Followers: 1)
Annales Universitatis Paedagogicae Cracoviensis. Studia Mathematica     Open Access  
Annali di Matematica Pura ed Applicata     Hybrid Journal   (Followers: 1)
Annals of Combinatorics     Hybrid Journal   (Followers: 3)
Annals of Data Science     Hybrid Journal   (Followers: 9)
Annals of Discrete Mathematics     Full-text available via subscription   (Followers: 6)
Annals of Mathematics     Full-text available via subscription  
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 6)
Annals of Pure and Applied Logic     Open Access   (Followers: 2)
Annals of the Alexandru Ioan Cuza University - Mathematics     Open Access  
Annals of the Institute of Statistical Mathematics     Hybrid Journal   (Followers: 1)
Annals of West University of Timisoara - Mathematics     Open Access  
Annuaire du Collège de France     Open Access   (Followers: 5)
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 2)
Applications of Mathematics     Hybrid Journal   (Followers: 1)
Applied Categorical Structures     Hybrid Journal   (Followers: 2)
Applied Computational Intelligence and Soft Computing     Open Access   (Followers: 12)
Applied Mathematics     Open Access   (Followers: 3)
Applied Mathematics     Open Access   (Followers: 4)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 4)
Applied Mathematics - A Journal of Chinese Universities     Hybrid Journal  
Applied Mathematics Letters     Full-text available via subscription   (Followers: 1)
Applied Mathematics Research eXpress     Hybrid Journal   (Followers: 1)
Applied Network Science     Open Access  
Applied Numerical Mathematics     Hybrid Journal   (Followers: 5)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 4)
Arab Journal of Mathematical Sciences     Open Access   (Followers: 2)
Arabian Journal of Mathematics     Open Access   (Followers: 2)
Archive for Mathematical Logic     Hybrid Journal   (Followers: 1)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 4)
Archive of Numerical Software     Open Access  
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 4)
Arkiv för Matematik     Hybrid Journal   (Followers: 1)
Arnold Mathematical Journal     Hybrid Journal   (Followers: 1)
Artificial Satellites : The Journal of Space Research Centre of Polish Academy of Sciences     Open Access   (Followers: 19)
Asia-Pacific Journal of Operational Research     Hybrid Journal   (Followers: 3)
Asian Journal of Algebra     Open Access   (Followers: 1)
Asian Journal of Current Engineering & Maths     Open Access  
Asian-European Journal of Mathematics     Hybrid Journal   (Followers: 2)
Australian Mathematics Teacher, The     Full-text available via subscription   (Followers: 7)
Australian Primary Mathematics Classroom     Full-text available via subscription   (Followers: 2)
Australian Senior Mathematics Journal     Full-text available via subscription   (Followers: 1)
Automatic Documentation and Mathematical Linguistics     Hybrid Journal   (Followers: 5)
Axioms     Open Access  
Baltic International Yearbook of Cognition, Logic and Communication     Open Access  
Basin Research     Hybrid Journal   (Followers: 5)
BIBECHANA     Open Access  
BIT Numerical Mathematics     Hybrid Journal  
BoEM - Boletim online de Educação Matemática     Open Access  
Boletim Cearense de Educação e História da Matemática     Open Access  
Boletim de Educação Matemática     Open Access  
Boletín de la Sociedad Matemática Mexicana     Hybrid Journal  
Bollettino dell'Unione Matematica Italiana     Full-text available via subscription   (Followers: 1)
British Journal of Mathematical and Statistical Psychology     Full-text available via subscription   (Followers: 21)
Bruno Pini Mathematical Analysis Seminar     Open Access  
Buletinul Academiei de Stiinte a Republicii Moldova. Matematica     Open Access   (Followers: 7)
Bulletin des Sciences Mathamatiques     Full-text available via subscription   (Followers: 4)
Bulletin of Dnipropetrovsk University. Series : Communications in Mathematical Modeling and Differential Equations Theory     Open Access   (Followers: 1)
Bulletin of Mathematical Sciences     Open Access   (Followers: 1)
Bulletin of the Brazilian Mathematical Society, New Series     Hybrid Journal  
Bulletin of the London Mathematical Society     Hybrid Journal   (Followers: 3)
Bulletin of the Malaysian Mathematical Sciences Society     Hybrid Journal  
Calculus of Variations and Partial Differential Equations     Hybrid Journal  
Canadian Journal of Science, Mathematics and Technology Education     Hybrid Journal   (Followers: 18)
Carpathian Mathematical Publications     Open Access   (Followers: 1)
Catalysis in Industry     Hybrid Journal   (Followers: 1)
CEAS Space Journal     Hybrid Journal  
CHANCE     Hybrid Journal   (Followers: 5)
Chaos, Solitons & Fractals     Hybrid Journal   (Followers: 3)
ChemSusChem     Hybrid Journal   (Followers: 7)
Chinese Annals of Mathematics, Series B     Hybrid Journal  
Chinese Journal of Catalysis     Full-text available via subscription   (Followers: 2)
Chinese Journal of Mathematics     Open Access  
Clean Air Journal     Full-text available via subscription   (Followers: 2)
Cogent Mathematics     Open Access   (Followers: 2)
Cognitive Computation     Hybrid Journal   (Followers: 4)
Collectanea Mathematica     Hybrid Journal  
College Mathematics Journal     Full-text available via subscription   (Followers: 2)
COMBINATORICA     Hybrid Journal  
Combustion Theory and Modelling     Hybrid Journal   (Followers: 13)
Commentarii Mathematici Helvetici     Hybrid Journal   (Followers: 1)
Communications in Contemporary Mathematics     Hybrid Journal  
Communications in Mathematical Physics     Hybrid Journal   (Followers: 1)
Communications On Pure & Applied Mathematics     Hybrid Journal   (Followers: 3)
Complex Analysis and its Synergies     Open Access   (Followers: 2)
Complex Variables and Elliptic Equations: An International Journal     Hybrid Journal  
Complexus     Full-text available via subscription  
Composite Materials Series     Full-text available via subscription   (Followers: 9)
Comptes Rendus Mathematique     Full-text available via subscription   (Followers: 1)
Computational and Applied Mathematics     Hybrid Journal   (Followers: 2)
Computational and Mathematical Methods in Medicine     Open Access   (Followers: 2)
Computational and Mathematical Organization Theory     Hybrid Journal   (Followers: 2)
Computational Complexity     Hybrid Journal   (Followers: 4)
Computational Mathematics and Modeling     Hybrid Journal   (Followers: 8)
Computational Mechanics     Hybrid Journal   (Followers: 4)
Computational Methods and Function Theory     Hybrid Journal  
Computational Optimization and Applications     Hybrid Journal   (Followers: 7)
Computers & Mathematics with Applications     Full-text available via subscription   (Followers: 5)
Concrete Operators     Open Access   (Followers: 4)
Confluentes Mathematici     Hybrid Journal  
COSMOS     Hybrid Journal  
Cryptography and Communications     Hybrid Journal   (Followers: 14)
Cuadernos de Investigación y Formación en Educación Matemática     Open Access  
Cubo. A Mathematical Journal     Open Access  
Czechoslovak Mathematical Journal     Hybrid Journal   (Followers: 1)
Demographic Research     Open Access   (Followers: 11)
Demonstratio Mathematica     Open Access  
Dependence Modeling     Open Access  
Design Journal : An International Journal for All Aspects of Design     Hybrid Journal   (Followers: 29)
Developments in Clay Science     Full-text available via subscription   (Followers: 1)
Developments in Mineral Processing     Full-text available via subscription   (Followers: 3)
Dhaka University Journal of Science     Open Access  
Differential Equations and Dynamical Systems     Hybrid Journal   (Followers: 2)
Discrete Mathematics     Hybrid Journal   (Followers: 7)
Discrete Mathematics & Theoretical Computer Science     Open Access  
Discrete Mathematics, Algorithms and Applications     Hybrid Journal   (Followers: 2)
Discussiones Mathematicae Graph Theory     Open Access   (Followers: 1)
Dnipropetrovsk University Mathematics Bulletin     Open Access  
Doklady Mathematics     Hybrid Journal  
Duke Mathematical Journal     Full-text available via subscription   (Followers: 1)
Edited Series on Advances in Nonlinear Science and Complexity     Full-text available via subscription  
Electronic Journal of Graph Theory and Applications     Open Access   (Followers: 2)
Electronic Notes in Discrete Mathematics     Full-text available via subscription   (Followers: 2)
Elemente der Mathematik     Full-text available via subscription   (Followers: 3)
Energy for Sustainable Development     Hybrid Journal   (Followers: 9)
Enseñanza de las Ciencias : Revista de Investigación y Experiencias Didácticas     Open Access  
Ensino da Matemática em Debate     Open Access  
Entropy     Open Access   (Followers: 5)
ESAIM: Control Optimisation and Calculus of Variations     Full-text available via subscription   (Followers: 1)
European Journal of Combinatorics     Full-text available via subscription   (Followers: 4)
European Journal of Mathematics     Hybrid Journal   (Followers: 1)
European Scientific Journal     Open Access   (Followers: 2)
Experimental Mathematics     Hybrid Journal   (Followers: 4)
Expositiones Mathematicae     Hybrid Journal   (Followers: 2)
Facta Universitatis, Series : Mathematics and Informatics     Open Access  
Fasciculi Mathematici     Open Access  
Finite Fields and Their Applications     Full-text available via subscription   (Followers: 4)
Fixed Point Theory and Applications     Open Access   (Followers: 1)
Formalized Mathematics     Open Access   (Followers: 2)

        1 2 3 4 | Last

Journal Cover European Journal of Combinatorics
  [SJR: 1.233]   [H-I: 35]   [4 followers]  Follow
    
   Full-text available via subscription Subscription journal
   ISSN (Print) 0195-6698 - ISSN (Online) 1095-9971
   Published by Elsevier Homepage  [3043 journals]
  • The k-strong induced arboricity of a graph
    • 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.

      PubDate: 2017-07-28T08:19:36Z
       
  • Definability equals recognizability for k-outerplanar graphs and l-chordal
           partial k-trees
    • 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.

      PubDate: 2017-07-28T08:19:36Z
       
  • Bootstrap percolation, and other automata
    • 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.

      PubDate: 2017-07-28T08:19:36Z
       
  • Decomposing regular graphs with prescribed girth into paths of given
           length
    • 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 .

      PubDate: 2017-07-28T08:19:36Z
       
  • A flow theory for the dichromatic number
    • 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.

      PubDate: 2017-07-28T08:19:36Z
       
  • On graphs with a large number of edge-colorings avoiding a rainbow
           triangle
    • 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 } .

      PubDate: 2017-07-28T08:19:36Z
       
  • On the generalised colouring numbers of graphs that exclude a fixed minor
    • 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 ) .

      PubDate: 2017-07-28T08:19:36Z
       
  • Corrigendum to “On the limiting distribution of the metric dimension for
           random forests” [European J. Combin. 49 (2015) 68–89]
    • Abstract: Publication date: Available online 22 July 2017
      Source:European Journal of Combinatorics
      Author(s): Dieter Mitsche, Juanjo Rué


      PubDate: 2017-07-28T08:19:36Z
       
  • Counting configuration-free sets in groups
    • 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.

      PubDate: 2017-07-28T08:19:36Z
       
  • Triangle-free graphs of tree-width t are
           ⌈(t+3)∕2⌉-colorable
    • 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 .

      PubDate: 2017-07-28T08:19:36Z
       
  • Parking distributions on trees
    • 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.

      PubDate: 2017-07-21T07:29:28Z
       
  • New invariants of knotoids
    • 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 .

      PubDate: 2017-07-21T07:29:28Z
       
  • Polyhedral geometry, supercranks, and combinatorial witnesses of
           congruences for partitions into three parts
    • 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.

      PubDate: 2017-07-21T07:29:28Z
       
  • One more remark on the adjoint polynomial
    • 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.

      PubDate: 2017-07-21T07:29:28Z
       
  • Cycles through all finite vertex sets in infinite graphs
    • 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.

      PubDate: 2017-07-21T07:29:28Z
       
  • A note on the simplex-cosimplex problem
    • 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.

      PubDate: 2017-07-21T07:29:28Z
       
  • Partitioning a triangle-free planar graph into a forest and a forest of
           bounded degree
    • 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.

      PubDate: 2017-07-21T07:29:28Z
       
  • A SAT attack on the Erdős–Szekeres conjecture
    • 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.

      PubDate: 2017-07-21T07:29:28Z
       
  • Even-cycle decompositions of graphs with no odd-K4-minor
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • A result on r-orthogonal factorizations in digraphs
    • 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 ).

      PubDate: 2017-07-08T02:47:52Z
       
  • Minimal complexity of equidistributed infinite permutations
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • Partition dimension of projective planes
    • 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 .

      PubDate: 2017-07-08T02:47:52Z
       
  • Quotients of polynomial rings and regular t-balanced Cayley maps on
           abelian groups
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • On the number of planar Eulerian orientations
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • On growth and fluctuation of k-abelian complexity
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • Minors in graphs of large θr-girth
    • 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 ) .

      PubDate: 2017-07-08T02:47:52Z
       
  • Erdős–Ko–Rado for perfect matchings
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • The structure and the number of P7-free bipartite graphs
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • Packing and covering immersion-expansions of planar sub-cubic graphs
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • Scribability problems for polytopes
    • 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 .

      PubDate: 2017-07-08T02:47:52Z
       
  • The classification of half-arc-regular bi-circulants of valency 6
    • 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 .

      PubDate: 2017-07-08T02:47:52Z
       
  • A q-enumeration of lozenge tilings of a hexagon with four adjacent
           triangles removed from the boundary
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • The classification of half-arc-transitive generalizations of Bouwer graphs
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • On degree sequences of undirected, directed, and bidirected graphs
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • On bipartite distance-regular graphs with exactly one non-thin T-module
           with endpoint two
    • 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
       
  • Properties of chromatic polynomials of hypergraphs not held for chromatic
           polynomials of graphs
    • 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 .

      PubDate: 2017-07-08T02:47:52Z
       
  • The planar cubic Cayley graphs of connectivity 2
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • Announcement from the Editors
    • Abstract: Publication date: June 2017
      Source:European Journal of Combinatorics, Volume 63


      PubDate: 2017-07-08T02:47:52Z
       
  • On bisections of directed 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 .

      PubDate: 2017-07-08T02:47:52Z
       
  • Inductive tools for connected delta-matroids and multimatroids
    • 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.

      PubDate: 2017-07-08T02:47:52Z
       
  • The average number of spanning trees in sparse graphs with given degrees
    • 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.

      PubDate: 2017-03-13T02:50:09Z
       
  • Waiter–Client and Client–Waiter Hamiltonicity games on random
           graphs
    • 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 .

      PubDate: 2017-03-13T02:50:09Z
       
  • Nonexistence of perfect 2-error-correcting Lee codes in certain dimensions
    • 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.

      PubDate: 2017-02-26T01:09:35Z
       
 
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
 
Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs
Your IP address: 54.81.157.56
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-2016