Authors:Daniel A. Jaume; Gonzalo Molina Pages: 836 - 850 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Daniel A. Jaume, Gonzalo Molina Let T be a tree. We show that the null space of the adjacency matrix of T has relevant information about the structure of T . We introduce the Null Decomposition of trees, which is a decomposition into two different types of trees: N-trees and S-trees. N-trees are the trees that have a unique maximum (perfect) matching. S-trees are the trees with a unique maximum independent set. We obtain formulas for the independence number and the matching number of a tree using this decomposition. We also show how the number of maximum matchings and the number of maximum independent sets in a tree are related to its null decomposition.

Authors:Fabrizio Caselli; Mario Marietti Pages: 851 - 862 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Fabrizio Caselli, Mario Marietti We give a simple characterization of special matchings in lower Bruhat intervals (that is, intervals starting from the identity element) of a Coxeter group. As a byproduct, we obtain some results on the action of special matchings.

Authors:Adam Kabela Pages: 579 - 587 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Adam Kabela Studying the shortness of longest cycles in maximal planar graphs, we improve the upper bound on the shortness exponent of the class of 5 4 -tough maximal planar graphs presented by Harant and Owens (1995). In addition, we present two generalizations of a similar result of Tkáč who considered 1 -tough maximal planar graphs (Tkáč, 1996); we remark that one of these generalizations gives a tight upper bound. We fix a problematic argument used in both mentioned papers.

Authors:Zhengke Miao; Yingqian Wang; Chuanni Zhang; Huajun Zhang Pages: 588 - 599 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Zhengke Miao, Yingqian Wang, Chuanni Zhang, Huajun Zhang Given a nonnegative integer d and a positive integer k , a graph G is said to be ( k , d ) -colorable if the vertices of G can be colored with k colors such that every vertex has at most d neighbors receiving the same color as itself. Let ℱ be the family of planar graphs without 3 -cycles adjacent to cycles of length 3 or 5. This paper proves that everyone in ℱ is ( 3 , 1 ) -colorable. This is the best possible in the sense that there are members in ℱ which are not ( 3 , 0 ) -colorable.

Authors:Mohit Kumbhat; Kevin Moss; Derrick Stolee Pages: 600 - 605 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Mohit Kumbhat, Kevin Moss, Derrick Stolee List coloring generalizes graph coloring by requiring the color of a vertex to be selected from a list of colors specific to that vertex. One refinement of list coloring, called choosability with separation, requires that the intersection of adjacent lists is sufficiently small. We introduce a new refinement, called choosability with union separation, where we require that the union of adjacent lists is sufficiently large. For t ≥ k , a ( k , t ) -list assignment is a list assignment L where L ( v ) ≥ k for all vertices v and L ( u ) ∪ L ( v ) ≥ t for all edges u v . A graph is ( k , t ) -choosable if there is a proper coloring for every ( k , t ) -list assignment. We explore this concept through examples of graphs that are not ( k , t ) -choosable, demonstrating sparsity conditions that imply a graph is ( k , t ) -choosable, and proving that all planar graphs are ( 3 , 11 ) -choosable and ( 4 , 9 ) -choosable.

Authors:Hiroshi Nishiyama; Yusuke Kobayashi; Yukiko Yamauchi; Shuji Kijima; Masafumi Yamashita Pages: 606 - 626 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Hiroshi Nishiyama, Yusuke Kobayashi, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita Motivated by a relaxed notion of the celebrated Hamiltonian cycle, this paper investigates its variant, parity Hamiltonian cycle (PHC): A PHC of a graph is a closed walk which visits every vertex an odd number of times, where we remark that the walk may use an edge more than once. First, we give a complete characterization of the graphs which have PHCs, and give a linear time algorithm to find a PHC, in which every edge appears at most four times, in fact. In contrast, we show that finding a PHC is NP -hard if a closed walk is allowed to use each edge at most z times for each z = 1 , 2 , 3 ( PHC z for short), even when a given graph is two-edge-connected. We then further investigate the PHC 3 problem, and show that the problem is in P when an input graph is four-edge-connected. Finally, we are concerned with three (or two)-edge-connected graphs, and show that the PHC 3 problem is in P for any C ≥ 5 -free or P 6 -free graphs. Note that the Hamiltonian cycle problem is known to be NP -hard for those graph classes.

Authors:Carl Johan Casselgren; Hrant H. Khachatrian; Petros A. Petrosyan Pages: 627 - 637 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Carl Johan Casselgren, Hrant H. Khachatrian, Petros A. Petrosyan An interval t -coloring of a multigraph G is a proper edge coloring with colors 1 , … , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors. A cyclic interval t -coloring of a multigraph G is a proper edge coloring with colors 1 , … , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t . Denote by w ( G ) ( w c ( G ) ) and W ( G ) ( W c ( G ) ) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph G , respectively. We present some new sharp bounds on w ( G ) and W ( G ) for multigraphs G satisfying various conditions. In particular, we show that if G is a 2 -connected multigraph with an interval coloring, then W ( G ) ≤ 1 + V ( G ) 2 ( Δ ( G ) − 1 ) . We also give several results towards the general conjecture that W c ( G ) ≤ V ( G ) for any triangle-free graph G with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most 4 .

Authors:Sebastián González Hermosillo de la Maza; César Hernández-Cruz Pages: 638 - 651 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Sebastián González Hermosillo de la Maza, César Hernández-Cruz Let D = ( V ( D ) , A ( D ) ) be a digraph. A subset S ⊆ V ( D ) is k -independent if the distance between every pair of vertices of S is at least k , and it is ℓ -absorbent if for every vertex u in V ( D ) ∖ S there exists v ∈ S such that the distance from u to v is less than or equal to ℓ . A k -kernel is a k -independent and ( k − 1 ) -absorbent set. A kernel is simply a 2 -kernel. A classical result due to Duchet states that if every directed cycle in a digraph D has at least one symmetric arc, then D has a kernel. We propose a conjecture generalizing this result for k -kernels and prove it true for k = 3 and k = 4 .

Authors:Danila Cherkashin Pages: 652 - 657 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Danila Cherkashin This paper studies the quantity p ( n , r ) , that is the minimal number of edges of an n -uniform hypergraph without panchromatic coloring (it means that every edge meets every color) in r colors. If r ≤ c n ln n then all bounds have a type A 1 ( n , ln n , r ) ( r r − 1 ) n ≤ p ( n , r ) ≤ A 2 ( n , r , ln r ) ( r r − 1 ) n , where A 1 , A 2 are some algebraic fractions. The main result is a new lower bound on p ( n , r ) when r is at least c n ; we improve an upper bound on p ( n , r ) if n = o ( r 3 ∕ 2 ) . Also we show that p ( n , r ) has upper and lower bounds depending only on n ∕ r when the ratio n ∕ r is small, which cannot be reached by the previous probabilistic machinery. Finally we construct an explicit example of a hypergraph without panchromatic coloring and with ( r r − 1 + o ( 1 ) ) n edges for r = o ( n ln n ) .

Authors:Małgorzata Bednarska-Bzdęga; Michael Krivelevich; Viola Mészáros; Clément Requilé Pages: 658 - 664 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Małgorzata Bednarska-Bzdęga, Michael Krivelevich, Viola Mészáros, Clément Requilé We consider the following two-player game, parametrised by positive integers n and k . The game is played between Painter and Builder, alternately taking turns, with Painter moving first. The game starts with the empty graph on n vertices. In each round Painter colours a vertex of her choice by one of the k colours and Builder adds an edge between two previously unconnected vertices. Both players must adhere to the restriction that the game graph is properly k -coloured. The game ends if either all n vertices have been coloured, or Painter has no legal move. In the former case, Painter wins the game; in the latter one, Builder is the winner. We prove that the minimal number of colours k = k ( n ) allowing Painter’s win is of logarithmic order in the number of vertices n . Biased versions of the game are also considered.

Authors:Aaron Berger; Christopher Chute; Matthew Stone Pages: 665 - 671 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Aaron Berger, Christopher Chute, Matthew Stone We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called codemaker constructs a hidden sequence H = ( h 1 , h 2 , … , h n ) of colors selected from an alphabet A = { 1 , 2 , … , k } (i.e., h i ∈ A for all i ∈ { 1 , 2 , … , n } ). The game then proceeds in turns, each of which consists of two parts: in turn t , the second player (the codebreaker) first submits a query sequence Q t = ( q 1 , q 2 , … , q n ) with q i ∈ A for all i , and second receives feedback Δ ( Q t , H ) , where Δ is some agreed-upon function of distance between two sequences with n components. The game terminates when the codebreaker has determined the value of H , and the codebreaker seeks to end the game in as few turns as possible. Throughout we let f ( n , k ) denote the smallest integer such that the codebreaker can determine any H in f ( n , k ) turns. We prove three main results: First, when H is known to be a permutation of { 1 , 2 , … , n } , we prove that f ( n , n ) ≥ n − log log n for all sufficiently large n . Second, we show that Knuth’s Minimax algorithm identifies any H in at most n k queries. Third, when feedback is not received until all queries have been submitted, we show that f ( n , k ) = Ω ( n log k ) .

Authors:Jeng-Jung Wang; Lih-Hsing Hsu Pages: 672 - 690 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Jeng-Jung Wang, Lih-Hsing Hsu In this paper, we employed lattice model to describe the three internally vertex-disjoint paths that span the vertex set of the generalized Petersen graph P ( n , 3 ) . We showed that the P ( n , 3 ) is 3-spanning connected for odd n . Based on the lattice model, five amalgamated and one extension mechanisms are introduced to recursively establish the 3-spanning connectivity of the P ( n , 3 ) . In each amalgamated mechanism, a particular lattice trail was amalgamated with the lattice trails that was dismembered, transferred, or extended from parts of the lattice trails for P ( n − 6 , 3 ) , where a lattice tail is a trail in the lattice model that represents a path in P ( n , 3 ) .

Authors:Ik-Pyo Kim; Michael J. Tsatsomeros Pages: 691 - 700 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Ik-Pyo Kim, Michael J. Tsatsomeros As an inverse relation, involution with an invariant sequence plays a key role in combinatorics and features prominently in some of Shapiro’s open questions (Shapiro, 2001). In this paper, invariant sequences are used to provide answers to some of these questions about the Fibonacci matrix and Riordan involutions.

Authors:P. Danziger; S. Park Pages: 701 - 704 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): P. Danziger, S. Park An orthogonally resolvable matching design OMD ( n , k ) is a partition of the edges of the complete graph K n into matchings of size k , called blocks, such that the blocks can be resolved in two different ways. Such a design can be represented as a square array whose cells are either empty or contain a matching of size k , where every vertex appears exactly once in each row and column. In this paper we show that an OMD ( n , k ) exists if and only if n ≡ 0 ( mod 2 k ) except when k = 1 and n = 4 or 6 .

Authors:S. Costa; F. Morini; A. Pasotti; M.A. Pellegrini Pages: 705 - 712 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): S. Costa, F. Morini, A. Pasotti, M.A. Pellegrini In this paper we propose a conjecture concerning partial sums of an arbitrary finite subset of an abelian group that naturally arises investigating simple Heffter systems. Then we show its connection with related open problems and we present some results about the validity of these conjectures.

Authors:Jessica McDonald; Gregory J. Puleo Pages: 713 - 722 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Jessica McDonald, Gregory J. Puleo We study the class of simple graphs G ∗ for which every pair of distinct odd cycles intersect in at most one edge. We give a structural characterization of the graphs in G ∗ and prove that every G ∈ G ∗ satisfies the list-edge-coloring conjecture. When Δ ( G ) ≥ 4 , we in fact prove a stronger result about kernel-perfect orientations in L ( G ) which implies that G is ( m Δ ( G ) : m ) -edge-choosable and Δ ( G ) -edge-paintable for every m ≥ 1 .

Authors:Lu Lu; Qiongxiang Huang; Jiangxia Hou; Xun Chen Pages: 723 - 731 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Lu Lu, Qiongxiang Huang, Jiangxia Hou, Xun Chen Let G be a connected graph with vertex set V ( G ) and edge set E ( G ) . For a subset S of V ( G ) , the Steiner distance d ( S ) of S is the minimum size of a connected subgraph whose vertex set contains S . For an integer k with 2 ≤ k ≤ n − 1 , the Steiner k -Wiener index SW k ( G ) is ∑ S ⊆ V ( G ) , S = k d ( S ) . In this paper, we introduce some transformations for trees that do not increase their Steiner k -Wiener index for 2 ≤ k ≤ n − 1 . Using these transformations, we get a sharp lower bound on Steiner k -Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.

Authors:Shengxiang Lv; Zihan Yuan Pages: 732 - 747 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Shengxiang Lv, Zihan Yuan Finding the smallest number of crosscaps that suffice to orientation-embed every edge signature of the complete bipartite graph K m , n is an open problem. In this paper that number for the complete bipartite graph K 4 , n , n ≥ 4 , is determined by using diamond products of signed graphs. The number is 2 ⌊ n − 1 2 ⌋ + 1 , which is attained by K 4 , n with exactly 1 negative edge, except that when n = 4 , the number is 4, which is attained by K 4 , 4 with exactly 4 independent negative edges.

Authors:Yi Zhang; Mei Lu Pages: 748 - 758 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Yi Zhang, Mei Lu A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. A d -matching in a 3-uniform hypergraph H is a matching of size d . Let V 1 , V 2 be a partition of n vertices such that V 1 = 2 d − 1 and V 2 = n − 2 d + 1 . Denote by E 3 ( 2 d − 1 , n − 2 d + 1 ) the 3-uniform hypergraph with vertex set V 1 ∪ V 2 consisting of all those edges which contain at least two vertices of V 1 . Let H be a 3-uniform hypergraph of order n ≥ 9 d 2 such that d e g ( u ) + d e g ( v ) > 2 [ n − 1 2 − n − d 2 ] for any two adjacent vertices u , v ∈ V ( H ) . In this paper, we prove H contains a d -matching if and only if H is not a subgraph of E 3 ( 2 d − 1 , n − 2 d + 1 ) .

Authors:Hongwei Liu; Xiaoqiang Wang; Dabin Zheng Pages: 759 - 771 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Hongwei Liu, Xiaoqiang Wang, Dabin Zheng Let m and k be two positive integers such that v 2 ( m ) = v 2 ( k ) , where v 2 ( ⋅ ) denotes the 2-valuation function, and let α be a primitive element of F p 2 m . Let C be a cyclic code over F p with a parity-check polynomial h 1 ( x ) h 2 ( x ) h 3 ( x ) ∈ F p 2 m [ x ] , where h 1 ( x ) , h 2 ( x ) and h 3 ( x ) are the minimal polynomials of α − p k + 1 2 , − α − p k + 1 2 and α − p m + 1 2 over F p respectively. In this paper, we determine the weight distribution and the complete weight distribution of the code C .

Authors:Slobodan Filipovski; Robert Jajcay Pages: 772 - 780 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Slobodan Filipovski, Robert Jajcay We consider a restriction of the well-known Cage Problem to the class of vertex-transitive graphs, and consider the problem of finding the smallest vertex-transitive k -regular graphs of girth g . Counting cycles to obtain necessary arithmetic conditions on the parameters ( k , g ) , we extend previous results of Biggs, and prove that, for any given excess e and any given degree k ≥ 4 , the asymptotic density of the set of girths g for which there exists a vertex-transitive ( k , g ) -cage with excess not exceeding e is 0.

Authors:Bartłomiej Bosek; Michał Dębski; Jarosław Grytczuk; Joanna Sokół; Małgorzata Śleszyńska-Nowak; Wiktor Żelazny Pages: 781 - 785 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Bartłomiej Bosek, Michał Dębski, Jarosław Grytczuk, Joanna Sokół, Małgorzata Śleszyńska-Nowak, Wiktor Żelazny In this paper we introduce and study two graph coloring problems and relate them to some deep number-theoretic problems. For a fixed positive integer k consider a graph B k whose vertex set is the set of all positive integers with two vertices a , b joined by an edge whenever the two numbers a ∕ gcd ( a , b ) and b ∕ gcd ( a , b ) are both at most k . We conjecture that the chromatic number of every such graph B k is equal to k . This would generalize the greatest common divisor problem of Graham from 1970; in graph-theoretic terminology it states that the clique number of B k is equal to k . Our conjecture is connected to integer lattice tilings and partial Latin squares completions.

Authors:Deqiong Li; Yaoping Hou Pages: 786 - 792 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Deqiong Li, Yaoping Hou Let G be a finite connected graph. In this note, we show that the complexity of G can be obtained from the partial derivatives at ( 1 − 1 t , t ) of a determinant in terms of the Bartholdi zeta function of G . Moreover, the second order partial derivatives at ( 1 − 1 t , t ) of this determinant can all be expressed as the linear combination of the Kirchhoff index, the additive degree-Kirchhoff index, and the multiplicative degree-Kirchhoff index of the graph G .

Authors:Jonathan Cutler; A.J. Radcliffe Pages: 793 - 800 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Jonathan Cutler, A.J. Radcliffe Recently, Davies, Jenssen, Perkins, and Roberts gave a very nice proof of the result (due, in various parts, to Kahn, Galvin–Tetali, and Zhao) that the independence polynomial of a d -regular graph is maximized by disjoint copies of K d , d . Their proof uses linear programming bounds on the distribution of a cleverly chosen random variable. In this paper, we use this method to give lower bounds on the independence polynomial of regular graphs. We also give a new bound on the number of independent sets in triangle-free cubic graphs.

Authors:Damir Vukičević; Shuang Zhao; Jelena Sedlar; Shou-Jun Xu; Tomislav Došlić Pages: 801 - 809 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Damir Vukičević, Shuang Zhao, Jelena Sedlar, Shou-Jun Xu, Tomislav Došlić Let M ( G ) denote the set of all maximal matchings in a simple graph G , and f : M ( G ) → { 0 , 1 } E ( G ) be the characteristic function of maximal matchings of G . Any set S ⊆ E ( G ) such that f S is an injection is called a global forcing set for maximal matchings in G , and the cardinality of smallest such S is called the global forcing number for maximal matchings of G . In this paper we establish sharp lower and upper bounds on this quantity and prove explicit formulas for certain classes of graphs. At the end, we also state some open problems and discuss some further developments.

Authors:O.V. Borodin; A.O. Ivanova; O.N. Kazak; E.I. Vasil’eva Pages: 825 - 829 Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): O.V. Borodin, A.O. Ivanova, O.N. Kazak, E.I. Vasil’eva Given a 3-polytope P , by h ( P ) we denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in P . In 1940, H. Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P 5 of 3-polytopes with minimum degree 5. In 1996, S. Jendrol’ and T. Madaras showed that if a polytope P in P 5 is allowed to have a 5-vertex adjacent to four 5-vertices (called a minor ( 5 , 5 , 5 , 5 , ∞ ) -star), then h ( P ) can be arbitrarily large. For each P ∗ in P 5 with neither vertices of degree 6 or 7 nor minor ( 5 , 5 , 5 , 5 , ∞ ) -star, it follows from Lebesgue’s theorem that h ( P ∗ ) ≤ 23 . We prove that every such polytope P ∗ satisfies h ( P ∗ ) ≤ 14 , which bound is sharp. Moreover, if 6-vertices are allowed but 7-vertices forbidden, or vice versa, then the height of minor 5-stars in P 5 under the absence of minor ( 5 , 5 , 5 , 5 , ∞ ) -stars can reach 15 or 17, respectively.

Authors:S.D. Adhikari; L. Boza; S. Eliahou; M.P. Revuelta; M.I. Sanz Pages: 287 - 298 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): S.D. Adhikari, L. Boza, S. Eliahou, M.P. Revuelta, M.I. Sanz Given k ≥ 1 , the Fox–Kleitman conjecture from 2006 states that there exists a nonzero integer b such that the 2 k -variable linear Diophantine equation ∑ i = 1 k ( x i − y i ) = b is ( 2 k − 1 ) -regular. This is best possible, since Fox and Kleitman showed that for all b ≥ 1 , this equation is not 2 k -regular. While the conjecture has recently been settled for all k ≥ 2 , here we focus on the case k = 3 and determine the degree of regularity of the corresponding equation for all b ≥ 1 . In particular, this independently confirms the conjecture for k = 3 . We also briefly discuss the case k = 4 .

Authors:Douglas R. Stinson Pages: 299 - 307 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Douglas R. Stinson In 1996, Jackson and Martin (Jackson and Martin, 1996) proved that a strong ideal ramp scheme is equivalent to an orthogonal array. However, there was no good characterization of ideal ramp schemes that are not strong. Here we show the equivalence of ideal ramp schemes to a new variant of orthogonal arrays that we term augmented orthogonal arrays. We give some constructions for these new kinds of arrays, and, as a consequence, we also provide parameter situations where ideal ramp schemes exist but strong ideal ramp schemes do not exist.

Authors:Jiafu Mi; Xiwang Cao Pages: 308 - 314 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Jiafu Mi, Xiwang Cao Generalizing the quasi-cyclic codes of index 1 1 3 introduced by Fan et al., we study a more general class of quasi-cyclic codes of fractional index generated by pairs of polynomials. The parity check polynomial and encoder of these codes are obtained. The asymptotic behaviours of the rates and relative distances of this class of codes are studied by using a probabilistic method. We prove that, for any positive real number δ such that the asymptotic GV-bound at k + l 2 δ is greater than 1 2 , the relative distance of the code is convergent to δ , while the rate is convergent to 1 k + l . As a result, quasi-cyclic codes of fractional index are asymptotically good.

Authors:Aras Erzurumluoğlu; C.A. Rodger Pages: 315 - 323 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Aras Erzurumluoğlu, C.A. Rodger Let G = K ( n 0 , … , n p − 1 ; λ 1 , λ 2 ) be the graph with p parts V 0 , V 1 , … , V p − 1 of n 0 , … , n p − 1 vertices, respectively, where there are λ 1 edges between each pair of vertices from the same part and λ 2 edges between each pair of vertices from distinct parts. A holey hamilton cycle of deficiency V i of G is a hamilton cycle of G − V i for some i satisfying 0 ≤ i ≤ p − 1 . A holey hamiltonian decomposition is a set of holey hamilton cycles whose edges partition E ( G ) . Representing each (holey) hamilton cycle as a color class in an edge-coloring, a (holey) hamiltonian decomposition of G is said to be fair if between each pair of (not necessarily distinct) parts the (permitted) color classes have size within one of each other—so the edges between a pair of parts are shared “evenly” among the (permitted) color classes. Similarly, a (holey) factorization of G is said to be internally fair if within each color class the edges between vertices of distinct parts are shared evenly among all pairs of distinct parts (for which that color class is permitted), and if within each color class the edges joining vertices from the same part are shared evenly among all parts (for which that color class is permitted). In this paper the existence of fair hamiltonian and fair holey hamiltonian decompositions of G are each settled except in a few cases. Simultaneously we settle the existence of internally fair and internally fair holey hamiltonian decompositions of G in a slightly more general setting.

Authors:Hai Q. Dinh; Yun Fan; Hualu Liu; Xiusheng Liu; Songsak Sriboonchitta Pages: 324 - 335 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Hai Q. Dinh, Yun Fan, Hualu Liu, Xiusheng Liu, Songsak Sriboonchitta The aim of this paper is to establish all self-dual λ -constacyclic codes of length p s over the finite commutative chain ring R = F p m + u F p m , where p is a prime and u 2 = 0 . If λ = α + u β for nonzero elements α , β of F p m , the ideal 〈 u 〉 is the unique self-dual ( α + u β ) -constacyclic codes. If λ = γ for some nonzero element γ of F p m , we consider two cases of γ . When γ = γ − 1 , i.e., γ = 1 or − 1 , we first obtain the dual of every cyclic code, a formula for the number of those cyclic codes and identify all self-dual cyclic codes. Then we use the ring isomorphism φ to carry over the results about cyclic accordingly to negacyclic codes. When γ ≠ γ − 1 , it is shown that 〈 u 〉 is the unique self-dual γ -constacyclic code. Among other results, the number of each type of self-dual constacyclic code is obtained.

Authors:Ken Kamano Pages: 341 - 349 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Ken Kamano A lonesum matrix is a ( 0 , 1 ) -matrix that is uniquely determined by its row and column sum vectors. In this paper, we introduce lonesum decomposable matrices and study their properties. We provide a necessary and sufficient condition for a matrix A to be lonesum decomposable, and give a generating function for the number D k ( m , n ) of m × n lonesum decomposable matrices of order k . Moreover, by using this generating function we prove some congruences for D k ( m , n ) modulo a prime.

Authors:Yan Liu; Minjia Shi; Patrick Solé Pages: 350 - 357 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Yan Liu, Minjia Shi, Patrick Solé We construct an infinite family of two-Lee-weight and three-Lee-weight codes over the non-chain ring F p + u F p + v F p + u v F p , where u 2 = 0 , v 2 = 0 , u v = v u . These codes are defined as trace codes. They have the algebraic structure of abelian codes. Their Lee weight distribution is computed by using Gauss sums. With a linear Gray map, we obtain a class of abelian three-weight codes and two-weight codes over F p . In particular, the two-weight codes we describe are shown to be optimal by application of the Griesmer bound. We also discuss their dual Lee distance. Finally, an application to secret sharing schemes is given.

Authors:Yan Zhuang Pages: 358 - 379 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Yan Zhuang The Goulden–Jackson cluster method is a powerful tool for obtaining generating functions counting words in a free monoid by occurrences of a set of subwords. We introduce a generalization of the cluster method for monoid networks, which generalize the combinatorial framework of free monoids. As a sample application of the generalized cluster method, we compute bivariate and multivariate generating functions counting Motzkin paths – both with height bounded and unbounded – by statistics corresponding to the number of occurrences of various subwords, yielding both closed-form and continued fraction formulas.

Authors:Vasilis Chasiotis; Stratis Kounias; Nikos Farmakis Pages: 380 - 387 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Vasilis Chasiotis, Stratis Kounias, Nikos Farmakis This paper attempts to prove the D-optimality of the saturated designs X ∗ and X ∗ ∗ of order 22, already existing in the current literature. The corresponding non-equivalent information matrices M ∗ =(X ∗ ) T X ∗ and M ∗ ∗ =(X ∗ ∗ ) T X ∗ ∗ have the maximum determinant. Within the application of a specific procedure, all symmetric and positive definite matrices M of order 22 with determinant the square of an integer and ≥ det(M ∗ ) are constructed. This procedure has indicated that there are 26 such non-equivalent matrices M, for 24 of which the non-existence of designs X such that X T X =M is proved. The remaining two matrices M are the information matrices M ∗ and M ∗ ∗ .

Authors:Rui Duarte; António Guedes de Oliveira Pages: 388 - 399 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Rui Duarte, António Guedes de Oliveira We introduce a new family of hyperplane arrangements in dimension n ≥ 3 that includes both the Shi arrangement and the Ish arrangement. We prove that all the members of a given subfamily have the same number of regions – the connected components of the complement of the union of the hyperplanes – which can be bijectively labeled with the Pak–Stanley labeling. In addition, we show that, in the cases of the Shi and the Ish arrangements, the number of labels with reverse centers of a given length is equal, and conjecture that the same happens with all of the members of the family.

Authors:Xiaofeng Gu; Hong-Jian Lai Pages: 400 - 404 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Xiaofeng Gu, Hong-Jian Lai Suppose that H is a simple uniform hypergraph satisfying E ( H ) = k ( V ( H ) − 1 ) . A k -partition π = ( X 1 , X 2 , … , X k ) of E ( H ) such that X i = V ( H ) − 1 for 1 ≤ i ≤ k is a uniform k -partition. Let P k ( H ) be the collection of all uniform k -partitions of E ( H ) and define ε ( π ) = ∑ i = 1 k c ( H ( X i ) ) − k , where c ( H ) denotes the number of maximal partition-connected sub-hypergraphs of H . Let ε ( H ) = min π ∈ P k ( H ) ε ( π ) . Then ε ( H ) ≥ 0 with equality holds if and only if H is a union of k edge-disjoint spanning hypertrees. The parameter ε ( H ) is used to measure how close H is being from a union of k edge-disjoint spanning hypertrees. We prove that if H is a simple uniform hypergraph with E ( H ) = k ( V ( H ) − 1 ) and ε ( H ) > 0 , then there exist e ∈ E ( H ) and e ′ ∈ E ( H c ) such that ε ( H −... PubDate: 2017-12-26T18:12:52Z DOI: 10.1016/j.disc.2017.09.007

Authors:A.A. Taranenko Pages: 405 - 420 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): A.A. Taranenko An n -ary quasigroup f of order q is an n -ary operation over a set of cardinality q such that the Cayley table of the operation is an n -dimensional latin hypercube of order q . A transversal in a quasigroup f (or in the corresponding latin hypercube) is a collection of q ( n + 1 ) -tuples from the Cayley table of f , each pair of tuples differing at each position. The problem of transversals in latin hypercubes was posed by Wanless in 2011. An n -ary quasigroup f is called reducible if it can be obtained as a composition of two quasigroups whose arity is at least 2, and it is completely reducible if it can be decomposed into binary quasigroups. In this paper we investigate transversals in reducible quasigroups and in quasigroups of order 4. We find a lower bound on the number of transversals for a vast class of completely reducible quasigroups. Next we prove that, except for the iterated group Z 4 of even arity, every n -ary quasigroup of order 4 has a transversal. Also we obtain a lower bound on the number of transversals in quasigroups of order 4 and odd arity and count transversals in the iterated group Z 4 of odd arity and in the iterated group Z 2 2 . All results of this paper can be regarded as those concerning latin hypercubes.

Authors:Kai Fender; Hadi Kharaghani; Sho Suda Pages: 421 - 426 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Kai Fender, Hadi Kharaghani, Sho Suda We introduce a class of regular unit Hadamard matrices whose entries consist of two complex numbers and their conjugates for a total of four complex numbers. We then show that these matrices are contained in the Bose–Mesner algebra of an association scheme arising from skew Paley matrices.

Authors:John Asplund; N. Bradley Fox Pages: 427 - 438 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): John Asplund, N. Bradley Fox The graph of overlapping permutations is a directed graph that is an analogue to the De Bruijn graph. It consists of vertices that are permutations of length n and edges that are permutations of length n + 1 in which an edge a 1 ⋯ a n + 1 would connect the standardization of a 1 ⋯ a n to the standardization of a 2 ⋯ a n + 1 . We examine properties of this graph to determine where directed cycles can exist, to count the number of directed 2 -cycles within the graph, and to enumerate the vertices that are contained within closed walks and directed cycles of more general lengths.

Authors:Seyyed Aliasghar Hosseini; Bojan Mohar Pages: 439 - 450 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Seyyed Aliasghar Hosseini, Bojan Mohar The integer grid Z □ Z has four typical orientations of its edges which make it a vertex-transitive digraph. In this paper we analyze the game of Cops and Robbers on arbitrary finite quotients of these directed grids.

Authors:Henri Perret du Cray; Ignasi Sau Pages: 451 - 462 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Henri Perret du Cray, Ignasi Sau Very recently, Thomassé et al. (2017) have given an FPT algorithm for Weighted Independent Set in bull-free graphs parameterized by the weight of the solution, running in time 2 O ( k 5 ) ⋅ n 9 . In this article we improve this running time to 2 O ( k 2 ) ⋅ n 7 . As a byproduct, we also improve the previous Turing-kernel for this problem from O ( k 5 ) to O ( k 2 ) . Furthermore, for the subclass of bull-free graphs without holes of length at most 2 p − 1 for p ≥ 3 , we speed up the running time to 2 O ( k ⋅ k 1 p − 1 ) ⋅ n 7 . As p grows, this running time is asymptotically tight in terms of k , since we prove that for each integer p ≥ 3 , Weighted Independent Set cannot be solved in time 2 o ( k ) ⋅ n O ( 1 ) in the class of { bull , C 4 , … , C 2 p − 1 } -free graphs unless the ETH fails.

Authors:Kathie Cameron; Murilo V.G. da Silva; Shenwei Huang; Kristina Vušković Pages: 463 - 473 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Kathie Cameron, Murilo V.G. da Silva, Shenwei Huang, Kristina Vušković A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph G has a vertex of degree at most 3 2 ω ( G ) − 1 , and hence χ ( G ) ≤ 3 2 ω ( G ) , where ω ( G ) denotes the size of a largest clique in G and χ ( G ) denotes the chromatic number of G . We give an O ( n m ) algorithm for q -coloring these graphs for fixed q and an O ( n m ) algorithm for maximum weight stable set, where n is the number of vertices and m is the number of edges of the input graph. We also give a polynomial-time algorithm for minimum coloring. Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs G without clique cutsets have treewidth at most 6 ω ( G ) − 1 and clique-width at most 48.

Authors:József Balogh; Alexandr Kostochka; Xujun Liu Pages: 474 - 483 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): József Balogh, Alexandr Kostochka, Xujun Liu A packing k -coloring of a graph G is a partition of V ( G ) into sets V 1 , … , V k such that for each 1 ≤ i ≤ k the distance between any two distinct x , y ∈ V i is at least i + 1 . The packing chromatic number, χ p ( G ) , of a graph G is the minimum k such that G has a packing k -coloring. Sloper showed that there are 4 -regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed k and g ≥ 2 k + 2 , almost every n -vertex cubic graph of girth at least g has the packing chromatic number greater than k .

Authors:Sebastian Milz; Lutz Volkmann Pages: 484 - 491 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Sebastian Milz, Lutz Volkmann Let D be a finite and simple digraph with vertex set V ( D ) . For a vertex v ∈ V ( D ) , the degree d ( v ) of v is defined as the minimum value of its out-degree d + ( v ) and its in-degree d − ( v ) . If D is a graph or a digraph with minimum degree δ and edge-connectivity λ , then λ ≤ δ . A graph or a digraph is maximally edge-connected if λ = δ . A graph or a digraph is called super-edge-connected if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree. In this note we present degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number of the underlying graph.

Authors:Jessica De Silva; Kristin Heysse; Adam Kapilow; Anna Schenfisch; Michael Young Pages: 492 - 496 Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): Jessica De Silva, Kristin Heysse, Adam Kapilow, Anna Schenfisch, Michael Young For two graphs G and H , the Turán number ex ( G , H ) is the maximum number of edges in a subgraph of G that contains no copy of H . Chen, Li, and Tu determined the Turán numbers ex ( K m , n , k K 2 ) for all k ≥ 1 Chen et al. (2009). In this paper we will determine the Turán numbers ex ( K a 1 , … , a r , k K r ) for all r ≥ 3 and k ≥ 1 .

Authors:Bojan Abstract: Publication date: March 2018 Source:Discrete Mathematics, Volume 341, Issue 3 Author(s): Bojan Vučković Let G be a graph without isolated edges, and let c : E ( G ) → { 1 , … , k } be a coloring of the edges, where adjacent edges may be colored the same. The color code of a vertex v is the ordered k -tuple ( a 1 , a 2 , … , a k ) , where a i is the number of edges incident with v that are colored i . If every two adjacent vertices of G have different color codes, such a coloring is called multi-set neighbor distinguishing. In this paper, we prove that three colors are sufficient to produce a multi-set neighbor distinguishing edge coloring for every graph without isolated edges.

Authors:Petrov Abstract: Publication date: February 2018 Source:Discrete Mathematics, Volume 341, Issue 2 Author(s): F. Petrov Divided symmetrization of a function f ( x 1 , … , x n ) is symmetrization of the ratio D S G ( f ) = f ( x 1 , … , x n ) ∏ ( x i − x j ) , where the product is taken over the set of edges of some graph G . We concentrate on the case when G is a tree and f is a polynomial of degree n − 1 , in this case D S G ( f ) is a constant function. We give a combinatorial interpretation of the divided symmetrization of monomials for general trees and probabilistic game interpretation for a tree which is a path. In particular, this implies a result by Postnikov originally proved by computing volumes of special polytopes, and suggests its generalization.