Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Dean Crnković, Vedrana Mikulić Crnković, Andrea Švob In this paper we classify 2 -designs and 3 -designs with 28 or 36 points admitting a transitive action of the unitary group U ( 3 , 3 ) on points and blocks. We also construct 2 -designs and 3 -designs with 56 or 63 points and strongly regular graphs on 36, 63 or 126 vertices having U ( 3 , 3 ) as a transitive automorphism group. Further, we show that this completes the classification of 3 -designs admitting a transitive action of the group U ( 3 , 3 ) , in terms of parameters. A number of the 3 -designs and 2 -designs obtained in this paper have not been known before up to our best knowledge.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): David Rolnick, Pablo Soberón We show quantitative versions of classical results in discrete geometry, where the size of a convex set is determined by some non-negative function. We give versions of this kind for the selection theorem of Bárány, the existence of weak epsilon-nets for convex sets and the ( p , q ) theorem of Alon and Kleitman. These methods can be applied to functions such as the volume, surface area or number of points of a discrete set. We also give general quantitative versions of the colorful Helly theorem for continuous functions.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Michael Kopreski, Gexin Yu We say a graph is ( d , d , … , d , 0 , … , 0 ) -colorable with a of d ’s and b of 0 ’s if V ( G ) may be partitioned into b independent sets O 1 , O 2 , … , O b and a sets D 1 , D 2 , … , D a whose induced graphs have maximum degree at most d . The maximum average degree, m a d ( G ) , of a graph G is the maximum average degree over all subgraphs of G . In this note, for nonnegative integers a , b , we show that if m a d ( G ) < 4 3 a + b , then G is ( 1 1 , 1 2 , … , 1 a , 0 1 , … , 0 b ) -colorable.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Minglong Qi, Shengwu Xiong, Jingling Yuan, Wenbi Rao, Luo Zhong Difference system of sets (DSS), introduced by Levenshtein, has an interesting connection with the construction of comma-free codes. In this paper, we construct two new families of DSS from the cyclotomic classes of order 12.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Boris Brimkov, Jennifer Edmond, Robert Lazar, Bernard Lidický, Kacy Messerschmidt, Shanise Walker An injective coloring of a graph G is an assignment of colors to the vertices of G so that any two vertices with a common neighbor have distinct colors. A graph G is injectively k -choosable if for any list assignment L , where L ( v ) ≥ k for all v ∈ V ( G ) , G has an injective L -coloring. Injective colorings have applications in the theory of error-correcting codes and are closely related to other notions of colorability. In this paper, we show that subcubic planar graphs with girth at least 6 are injectively 5-choosable. This strengthens the result of Lužar, Škrekovski, and Tancer that subcubic planar graphs with girth at least 7 are injectively 5-colorable. Our result also improves several other results in particular cases.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Jean-Luc Baril, Sergey Kirgizov We introduce a new statistic based on permutation descents which has a distribution given by the Stirling numbers of the first kind, i.e., with the same distribution as for the number of cycles in permutations. We study this statistic on the sets of permutations avoiding one pattern of length three by giving bivariate generating functions. As a consequence, new classes of permutations enumerated by the Motzkin numbers are obtained. Finally, we deduce results about the popularity of the pure descents in all these restricted sets.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Denis S. Krotov An extended 1 -perfect trade is a pair ( T 0 , T 1 ) of two disjoint binary distance- 4 even-weight codes such that the set of words at distance 1 from T 0 coincides with the set of words at distance 1 from T 1 . Such trade is called primary if any pair of proper subsets of T 0 and T 1 is not a trade. Using a computer-aided approach, we classify nonequivalent primary extended 1 -perfect trades of length 10 , constant-weight extended 1 -perfect trades of length 12 , and Steiner trades derived from them. In particular, all Steiner trades with parameters ( 5 , 6 , 12 ) are classified.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Christina Graves, Stephen J. Graves, L.-K. Lauderdale Let D 2 n denote the dihedral group of order 2 n , where n ≥ 3 . In this article, we build upon the findings of Haggard and McCarthy who, for certain values of n , produced a vertex-minimal graph with dihedral symmetry. Specifically, Haggard considered the situation when n 2 or n is a prime power, and McCarthy investigated the case when n is not divisible by 2 , 3 or 5 . In this article, we assume n is not divisible by 4 and construct a vertex-minimal graph whose automorphism group is isomorphic to D 2 n .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): P. Charbit, L. Hosseini, P. Ossona de Mendez The notion of left convergent sequences of graphs introduced by Lovász et al. (in relation with homomorphism densities for fixed patterns and Szemerédi’s regularity lemma) got increasingly studied over the past 10 years. Recently, Nešetřil and Ossona de Mendez introduced a general framework for convergence of sequences of structures. In particular, the authors introduced the notion of Q F -convergence, which is a natural generalization of left-convergence. In this paper, we initiate study of Q F -convergence for structures with functional symbols by focusing on the particular case of tree semi-lattices. We fully characterize the limit objects and give an application to the study of left convergence of m -partite cographs, a generalization of cographs.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Makoto Nishina, Yusuke Suzuki We shall determine exactly two ( P , Q ) -irreducible even triangulations of the projective plane. This result is a new generating theorem of even triangulations of the projective plane, that is, every even triangulation of the projective plane can be obtained from one of those two ( P , Q ) -irreducible even triangulations by a sequence of two expansions called a P -expansion and a Q -expansion, which were used in Batagelj (1984, 1989), Drapal and Lisonek (2010). Furthermore, we prove that for any closed surface F 2 there are finitely many ( P , Q ) -irreducible even triangulations of F 2 .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Niranjan Balachandran, Sajith Padinhatteeri The distinguishing chromatic number of a graph G , denoted χ D ( G ) , is defined as the minimum number of colors needed to properly color G such that no non-trivial automorphism of G fixes each color class of G . In this paper, we consider random Cayley graphs Γ defined over certain abelian groups A with A = n , and show that with probability at least 1 − n − Ω ( log n ) , χ D ( Γ ) ≤ χ ( Γ ) + 1 .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Aubrey Blecher, Charlotte Brennan, Arnold Knopfmacher, Toufik Mansour We define [ k ] = { 1 , 2 , … , k } to be a (totally ordered) alphabet on k letters. A word w of length n on the alphabet [ k ] is an element of [ k ] n . A word can be represented by a bargraph (i.e., by a column-convex polyomino whose lower edges lie on the x -axis) in which the height of the i th column equals the size of the i th part of the word. Thus these bargraphs have heights which are less than or equal to k . We consider the perimeter, which is the number of edges on the boundary of the bargraph. By way of Cramer’s method and the kernel method, we obtain the generating function that counts the perimeter of words. Using these generating functions we find the average perimeter of words of length n over the alphabet [ k ] . We also show how the mean and variance can be obtained using a direct counting method.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Masaaki Harada In this note, we demonstrate that every binary doubly even self-dual code of length 40 can be realized as the residue code of some extremal Type II Z 4 -code. As a consequence, it is shown that there are at least 94356 inequivalent extremal Type II Z 4 -codes of length 40 .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Binzhou Xia The covering radius of a subset C of the symmetric group S n is the maximal Hamming distance of an element of S n from C . This note determines the covering radii of the finite 2 -dimensional projective general linear groups. It turns out that the covering radius of PGL 2 ( q ) is q − 2 if q is even, and is q − 3 if q is odd.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Tanja Gologranc, Polona Repolusk Toll convexity is a variation of the so-called interval convexity. A tolled walk T between two non-adjacent vertices u and v in a graph G is a walk, in which u is adjacent only to the second vertex of T and v is adjacent only to the second-to-last vertex of T . A toll interval between u , v ∈ V ( G ) is a set T G ( u , v ) = { x ∈ V ( G ) : x lies on a tolled walk between u and v } . A set S ⊆ V ( G ) is toll convex, if T G ( u , v ) ⊆ S for all u , v ∈ S . A toll closure of a set S ⊆ V ( G ) is the union of toll intervals between all pairs of vertices from S . The size of a smallest set S whose toll closure is the whole vertex set is called a toll number of a graph G , t n ( G ) . The first part of the paper reinvestigates the characterization of convex sets in the Cartesian product of two graphs. It is proved that the toll number of the Cartesian product of two graphs equals 2. In the second part, the toll number of the lexicographic product of two graphs is studied. It is shown that if H is not isomorphic to a complete graph, t n ( G ∘ H ) ≤ 3 ⋅ t n ( G ) . We give some necessary and sufficient conditions for t n ( G ∘ H ) = 3 ⋅ t n ( G ) . Moreover, if G has at least two extreme vertices, a complete characterization is given. Furthermore, graphs with t n ( G ∘ H ) = 2 are characterized. Finally, the formula for t n ( G ∘ H ) is given — it is described in terms of the so-called toll-dominating triples or, if H is complete, toll-dominating pairs.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Isabel Beckenbach, Robert Scheidweiler We prove characterizations of the existence of perfect f -matchings in uniform mengerian and perfect hypergraphs. Moreover, we investigate the f -factor problem in balanced hypergraphs. For uniform balanced hypergraphs we prove two existence theorems with purely combinatorial arguments, whereas for non-uniform balanced hypergraphs we show that the f -factor problem is NP -hard.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Tien Chih, Demitri Plessas Directed graphs have long been used to gain an understanding of the structure of semigroups, and recently the structure of directed graph semigroups has been investigated resulting in a characterization theorem and an analog of Frucht’s Theorem. We investigate two inverse semigroups defined over undirected graphs constructed from the notions of subgraph and vertex set induced subgraph. We characterize the structure of the semilattice of idempotents and lattice of ideals of these inverse semigroups. We prove a characterization theorem that states that every graph has a unique associated inverse semigroup up to isomorphism allowing for an algebraic restatement of the Edge Reconstruction Conjecture.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Cunsheng Ding, Chengju Li The interplay between coding theory and t -designs started many years ago. While every t -design yields a linear code over every finite field, the largest t for which an infinite family of t -designs is derived directly from a linear or nonlinear code is t = 3 . Sporadic 4 -designs and 5 -designs were derived from some linear codes of certain parameters. The major objective of this paper is to construct many infinite families of 2 -designs and 3 -designs from linear codes. The parameters of some known t -designs are also derived. In addition, many conjectured infinite families of 2 -designs are also presented.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): David Bevan We present families of large undirected and directed Cayley graphs whose construction is related to butterfly networks. One approach yields, for every large k and for values of d taken from a large interval, the largest known Cayley graphs and digraphs of diameter k and degree d . Another method yields, for sufficiently large k and infinitely many values of d , Cayley graphs and digraphs of diameter k and degree d whose order is exponentially larger in k than any previously constructed. In the directed case, these are within a linear factor in k of the Moore bound.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Masashi Kosuda, Manabu Oura The purpose of this paper is to investigate the finite group which appears in the study of the Type II Z 4 -codes. To be precise, it is characterized in terms of generators and relations, and we determine the structure of the centralizer algebras of the tensor representations of this group.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Andrea Munaro We show that f ( x ) = ⌊ 3 2 x ⌋ is a θ -bounding function for the class of subcubic graphs and that it is best possible. This generalizes a result by Henning et al. (2012), who showed that θ ( G ) ≤ 3 2 α ( G ) for any subcubic triangle-free graph G . Moreover, we provide a θ -bounding function for the class of K 4 -free graphs with maximum degree at most 4 . Finally, we study the problem Clique Cover for subclasses of planar graphs and graphs with bounded maximum degree: in particular, answering a question of Cerioli et al. (2008), we show it admits a PTAS for planar graphs.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Meysam Alishahi, Hossein Hajiabolhassan For a graph G and a family of graphs F , the general Kneser graph KG ( G , F ) is a graph with the vertex set consisting of all subgraphs of G isomorphic to some member of F and two vertices are adjacent if their corresponding subgraphs are edge disjoint. In this paper, we introduce some generalizations of Turán number of graphs. In view of these generalizations, we give some lower and upper bounds for the chromatic number of general Kneser graphs KG ( G , F ) . Using these bounds, we determine the chromatic number of some family of general Kneser graphs KG ( G , F ) in terms of generalized Turán number of graphs. In particular, we determine the chromatic number of every Kneser multigraph KG ( G , F ) where G is a multigraph each of whose edges has the multiplicity at least 2 and F is an arbitrary family of simple graphs. Moreover, the chromatic number of general Kneser graph KG ( G , F ) is exactly determined where G is a dense graph and F = { K 1 , 2 } .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Pedro J. Miana, Hideyuki Ohtsuka, Natalia Romero In this paper, we consider combinatorial numbers ( C m , k ) m ≥ 1 , k ≥ 0 , mentioned as Catalan triangle numbers where C m , k ≔ m − 1 k − m − 1 k − 1 . These numbers unify the entries of the Catalan triangles B n , k and A n , k for appropriate values of parameters m and k , i.e., B n , k = C 2 n , n − k and A n , k = C 2 n + 1 , n + 1 − k . In fact, these numbers are suitable rearrangements of the known ballot numbers and some of these numbers are the well-known Catalan numbers C n that is C 2 n , n − 1 = C 2 n + 1 , n = C n . We present identities for sums (and alternating sums) of C m , k , squares and cubes of C m , k and, consequently, for B n , k and A n , k . In particular, one of these identities solves an open problem posed in Gutiérrez et al. (2008). We also give some identities between ( C m , k ) m ≥ 1 , k ≥ 0 and harmonic numbers ( H n ) n ≥ 1 . Finally, in the last section, new open problems and identities involving ( C n ) n ≥ 0 are conjectured.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Song-Tao Guo, Hailong Hou, Yong Xu A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. In this paper, we classify hexavalent symmetric graphs of order 9 p for each prime p .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Boštjan Brešar A long-standing Vizing’s conjecture asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers; one of the most significant results related to the conjecture is the bound of Clark and Suen, γ ( G □ H ) ≥ γ ( G ) γ ( H ) ∕ 2 , where γ stands for the domination number, and G □ H is the Cartesian product of graphs G and H . In this note, we improve this bound by employing the 2-packing number ρ ( G ) of a graph G into the formula, asserting that γ ( G □ H ) ≥ ( 2 γ ( G ) − ρ ( G ) ) γ ( H ) ∕ 3 . The resulting bound is better than that of Clark and Suen whenever G is a graph with ρ ( G ) < γ ( G ) ∕ 2 , and in the case G has diameter 2 reads as γ ( G □ H ) ≥ ( 2 γ ( G ) − 1 ) γ ( H ) ∕ 3 .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Jakub Przybyło Consider a positive integer r and a graph G = ( V , E ) with maximum degree Δ and without isolated edges. The least k so that a proper edge colouring c : E → { 1 , 2 , … , k } exists such that ∑ e ∋ u c ( e ) ≠ ∑ e ∋ v c ( e ) for every pair of distinct vertices u , v at distance at most r in G is denoted by χ Σ , r ′ ( G ) . For r = 1 , it has been proved that χ Σ , 1 ′ ( G ) = ( 1 + o ( 1 ) ) Δ . For any r ≥ 2 in turn an infinite family of graphs is known with χ Σ , r ′ ( G ) = Ω ( Δ r − 1 ) . We prove that, on the other hand, χ Σ , r ′ ( G ) = O ( Δ r − 1 ) for r ≥ 2 . In particular, we show that χ Σ , r ′ ( G ) ≤ 6 Δ r − 1 if r ≥ 4 .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Jiuqiang Liu, Xiaodong Liu In this paper, we derive a best possible k -wise extension to the well-known Snevily theorem on set systems (Snevily, 2003) which strengthens the well-known theorem by Füredi and Sudakov (2004). We also provide a conjecture which gives a common generalization to all existing non-modular L -intersection theorems.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Shangwei Lin, Ya’nan Jin, Chunfang Li The k -restricted arc connectivity of digraphs is a common generalization of the arc connectivity and the restricted arc connectivity. An arc subset S of a strong digraph D is a k -restricted arc cut if D − S has a strong component D ′ with order at least k such that D − V ( D ′ ) contains a connected subdigraph with order at least k . The k -restricted arc connectivity λ k ( D ) of a digraph D is the minimum cardinality over all k -restricted arc cuts of D . Let D be a strong digraph with order n ≥ 6 and minimum degree δ ( D ) . In this paper, we first show that λ 3 ( D ) exists if δ ( D ) ≥ 3 and, furthermore, λ 3 ( D ) ≤ ξ 3 ( D ) if δ ( D ) ≥ 4 , where ξ 3 ( D ) is the minimum 3-degree of D . Next, we prove that λ 3 ( D ) = ξ 3 ( D ) if δ ( D ) ≥ n + 3 2 . Finally, we give examples showing that these results are best possible in some sense.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Michael A. Henning, Anders Yeo A transversal in a hypergraph H is a subset of vertices that has a nonempty intersection with every edge of H . A transversal family F of H is a family of (not necessarily distinct) transversals of H . The effective transversal-ratio of the family F is the ratio of the number of sets in F over the maximum times r F any element appears in F . The fractional disjoint transversal number FDT ( H ) is the supremum of the effective transversal-ratio taken over all transversal families. That is, FDT ( H ) = sup F F ∕ r F . Using a connection with not-all-equal 3 -SAT, we prove that if H is a 3 -regular 3 -uniform hypergraph, then FDT ( H ) ≥ 2 , which proves a known conjecture. Using probabilistic arguments, we prove that for all k ≥ 3 , if H is a k -regular k -uniform hypergraph, then FDT ( H ) ≥ 1 ∕ ( 1 − ( k − 1 k ) 1 k 1 k − 1 ) , and that this bound is essentially best possible.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Artem Napov We establish a divide-and-conquer bound for the aggregate’s quality and algebraic connectivity measures, as defined for weighted undirected graphs. Aggregate’s quality is defined on a set of vertices and, in the context of aggregation-based multigrid methods, it measures how well this set of vertices is represented by a single vertex. On the other hand, algebraic connectivity is defined on a graph, and measures how well this graph is connected. The considered divide-and-conquer bound for aggregate’s quality relates the aggregate’s quality of a union of two disjoint sets of vertices to the aggregate’s quality of the two sets. Likewise, the bound for algebraic connectivity relates the algebraic connectivity of the graph induced by a union of two disjoint sets of vertices to the algebraic connectivity of the graphs induced by the two sets.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Li Liu, Lanqiang Li, Liqi Wang, Shixin Zhu In this paper, we explicitly determine the generator polynomials of all repeated-root constacyclic codes of length n l p s over F q and their dual codes, where l is an odd prime different from p , and n is an odd prime different from both l and p such that n = 2 h + 1 for some prime h or h = 1 . Moreover, we give all self-dual cyclic codes of length n l p s over F q and their enumeration. All linear complementary dual (LCD) cyclic codes of length n l p s over F q and their enumeration are also obtained.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Hengjia Wei, Gennian Ge A uniformly resolvable design (URD) is a resolvable design in which each parallel class contains blocks of only one block size k . Such a class is denoted k -pc and for a given k the number of k -pcs is denoted r k . The number of points of the URD is denoted by v . In the literature, the existence of URDs of block sizes k 1 and k 2 with { k 1 , k 2 } ∈ { { 2 , 3 } , { 2 , 4 } , { 3 , 4 } } has been studied with much efforts. For { k 1 , k 2 } = { 2 , 3 } or { 3 , 4 } , the existence spectra have been determined completely, while for { k 1 , k 2 } = { 2 , 4 } there are still 1338 undetermined pairs of ( v , r 2 ) . In this paper we continue the study on the existence of URDs of block sizes 2 and 4. We improve the known results by reducing the number of open cases from 1338 to 16 . In addition, we prove that there exist 4 -RGDDs of types 2178, 2250 and 2334.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Jiangmin Pan, Bo Ling, Suyun Ding A graph is called symmetric if its automorphism group is transitive on its arcs. In this paper, we classify symmetric graphs of order four times an odd square-free integer and valency seven. It is shown that, either the graph is isomorphic to one of 9 specific graphs or its full automorphism group is isomorphic to PSL ( 2 , p ) , PGL ( 2 , p ) , PSL ( 2 , p ) × Z 2 or PGL ( 2 , p ) × Z 2 with p ≡ ± 1 ( mod 7 ) a prime.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): João Carvalho, Bruna S. Souza, Vilmar Trevisan, Fernando C. Tura We develop an algorithm for computing the characteristic polynomial of matrices related to threshold graphs. We use this as tool to exhibit, for any natural number n ≥ 4 , 2 n − 4 graphs with n vertices that have a non isomorphic pair with the same signless Laplacian spectrum. We also show how to construct infinite families of pairs of non isomorphic graphs having the same Q -spectrum.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): M.H. Shirdareh Haghighi, F. Motialah, B. Amini A graph G of order 2 n is called equipartite if for every n -element set A ⊆ V ( G ) , there exists an automorphism of G that maps the induced subgraph G [ A ] onto G [ V ( G ) ∖ A ] . In this paper, we show that a graph G of order 2 n is equipartite if and only if for every such partition of V ( G ) , the induced subgraphs G [ A ] and G [ V ( G ) ∖ A ] have the same Laplacian spectra.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Sen-Peng Eu, Seunghyun Seo, Heesung Shin In this paper we enumerate and give bijections for the following four sets of vertices among rooted ordered trees of a fixed size: (i) first-children of degree k at level ℓ , (ii) non-first-children of degree k at level ℓ − 1 , (iii) leaves having k − 1 elder siblings at level ℓ , and (iv) non-leaves of outdegree k at level ℓ − 1 . Our results unite and generalize several previous works in the literature.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Lifeng Dai, Yingqian Wang, Jinghan Xu Let d 1 , d 2 , … , d k be k non-negative integers. A graph G is ( d 1 , d 2 , … , d k ) -colorable, if the vertex set of G can be partitioned into subsets V 1 , V 2 , … , V k such that the subgraph G [ V i ] induced by V i has maximum degree at most d i for i = 1 , 2 , … , k . In this paper, we prove that every planar graph without cycles of length 4 or 9 is ( 1 , 1 , 0 ) -colorable.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Fabrício S. Benevides, Carlos Hoppen, Rudini M. Sampaio Given a graph F and an integer r ≥ 2 , a partition F ̂ of the edge set of F into at most r classes, and a graph G , define c r , F ̂ ( G ) as the number of r -colorings of the edges of G that do not contain a copy of F such that the edge partition induced by the coloring is isomorphic to the one of F . We think of F ̂ as the pattern of coloring that should be avoided. The main question is, for a large enough n , to find the (extremal) graph G on n vertices which maximizes c r , F ̂ ( G ) . This problem generalizes a question of Erdős and Rothschild, who originally asked about the number of colorings not containing a monochromatic clique (which is equivalent to the case where F is a clique and the partition F ̂ contains a single class). We use Hölder’s Inequality together with Zykov’s Symmetrization to prove that, for any r ≥ 2 , k ≥ 3 and any pattern K k ̂ of the clique K k , there exists a complete multipartite graph that is extremal. Furthermore, if the pattern K k ̂ has at least two classes, with the possible exception of two very small patterns (on three or four vertices), every extremal graph must be a complete multipartite graph. In the case that r = 3 and F ̂ is a rainbow triangle (that is, where F = K 3 and each part is a singleton), we show that an extremal graph must be an almost complete graph. Still for r = 3 , we extend a result about monochromatic patterns of Alon, Balogh, Keevash and Sudakov to some patterns that use two of the three colors, finding the exact extremal graph. For the later two results, we use the Regularity and Stability Method.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Stefaan De Winter, Eric Neubert, Zeying Wang In this note we prove the non-existence of two types of partial difference sets in Abelian groups of order 216 . This completes the classification of parameters for which a partial difference set of size at most 100 exists in an Abelian group.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Fenix W.D. Huang, Christian M. Reidys In this paper, we present a topological framework for studying signed permutations and their reversal distance. This framework is based on a presentation of orientable and non-orientable fatgraphs via sectors. As an application, we give an alternative approach and interpretation of the Hannenhalli–Pevzner formula for the reversal distance of sorting signed permutations. This is obtained by constructing a bijection between signed permutations and certain equivalence classes of fatgraphs, called π -maps. We study the action of reversals and show that they either splice, glue or half-flip external vertices, which implies that any reversal changes the topological genus by at most one. We show that the lower bound of the reversal distance of a signed permutation equals the topological genus of its π -maps. We then discuss how the new topological model connects to other sorting problems.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Katarzyna Rybarczyk, Dudley Stark Random intersection graphs are characterised by three parameters: n , m and p , where n is the number of vertices, m is the number of objects, and p is the probability that a given object is associated with a given vertex. Two vertices in a random intersection graph are adjacent if and only if they have an associated object in common. When m = ⌊ n α ⌋ for constant α , we provide a condition, called strictly α -balanced, for the Poisson convergence of the number of induced copies of a fixed subgraph.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Derek Garton Fix an odd prime ℓ and let G be the poset of isomorphism classes of finite abelian ℓ -groups, ordered by inclusion. If ξ : G → R ≥ 0 is a discrete probability distribution on G and A ∈ G , define the A th moment of ξ to be ∑ B ∈ G Surj ( B , A ) ξ ( B ) . The question of determining conditions that ensure ξ is completely determined by its moments has been of recent interest in many problems of Cohen–Lenstra type. Furthermore, recovering ξ from its moments requires a new Möbius-type inversion formula on G . In this paper, we define this function, relate it to the classical Möbius function on the poset of subgroups of a fixed group, and prove two theorems about when it vanishes. As one corollary of these theorems, we obtain an analog of Hall’s theorem on the vanishing of the classical Möbius function. As another, we obtain an infinite family of pairs of groups on which the classical Möbius function vanishes; obtaining such pairs is a group-theoretic topic of recent interest.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Mircea Merca A relationship between the general linear group G L ( n , m ) and integer partitions was investigated by Macdonald in order to calculate the number of conjugacy classes in G L ( n , m ) . In this paper, the author introduced two different factorizations for a special case of Lambert series in order to prove that the number of conjugacy classes in the general linear group G L ( n , m ) and the number of partitions of n into k different magnitudes are related by a finite discrete convolution. New identities involving overpartitions, partitions into k different magnitudes and other combinatorial objects are discovered and proved in this context.