Search

Abstract: Došlić and Måløy (2010) obtained the extremal 6-cactus chains with respect to the number of matchings and of independent sets. Motivated by the prior paper, in this paper we give recurrences for matching polynomials of ortho-chains and meta-chains, and show that they are the -cactus chains with the most matchings. [Copyright &y& Elsevier]

Let δ ( P ) be the δ -vector of a reflexive polytope P ⊂ R d of dimension d and δ ( P ∨ ) the δ -vector of the dual polytope P ∨ ⊂ R d . In general, δ ( P ) = δ ( P ∨ ) does not hold. In this paper, we give a higher-dimensional construction of a reflexive polytope whose δ -vector equals the δ -vector of the dual polytope. In particular, we consider the case that the reflexive polytope and the dual polytope are unimodularly equivalent. [ABSTRACT FROM AUTHOR]

In this paper we present an explicit formula for the number of permutations with a given number of alternating descents. As an application, we obtain an interlacing property for the zeros of alternating Eulerian polynomials. [ABSTRACT FROM AUTHOR]

Let F r be a finite field with r = q m elements and θ a primitive element of F r . Suppose that h 1 ( x ) and h 2 ( x ) are the minimal polynomials over F q of g 1 − 1 and g 2 − 1 , respectively, where g 1 , g 2 ∈ F r ∗ . Let C be a reducible cyclic code over F q with check polynomial h 1 ( x ) h 2 ( x ) . In this paper, we investigate the complete weight enumerators of the cyclic codes C in the following two cases: (1) g 1 = θ q − 1 h , g 2 = β g 1 , where h > 1 is a divisor of q − 1 , e > 1 is a divisor of h , and β = θ r − 1 e ; (2) g 1 = θ 2 , g 2 = θ p k + 1 , where q = p is an odd prime and k is a positive integer. Moreover, we explicitly present the complete weight enumerators of some cyclic codes. [ABSTRACT FROM AUTHOR]

The complete cd -index of a Bruhat interval is a non-commutative polynomial in the variables c and d , which was introduced by Billera and Brenti and conjectured to have non-negative coefficients. For a cd -monomial M containing at most one d , i.e., M = c i or M = c i d c j ( i , j ≥ 0 ) , Karu showed that the coefficient of M is non-negative. In this paper, we show that when M = d c i d c j ( i , j ≥ 0 ) , the coefficient of M is non-negative. [ABSTRACT FROM AUTHOR]

Abstract: In Gaussian elimination it is often desirable to preserve existing zeros (sparsity). This is closely related to perfect elimination schemes on graphs. Such schemes can be found in polynomial time. Gaussian elimination uses a pivot for each column, so opportunities for preserving sparsity can be missed. In this paper we consider a more flexible process that selects a pivot for each nonzero to be eliminated and show that recognizing matrices that allow such perfect partial elimination schemes is NP-hard. [Copyright &y& Elsevier]

Abstract: Let be an arbitrary simple graph. Godsil and Gutman in 1978 and Yan et al. in 2005 established different expressions for the matching polynomial in terms of for some families of matrices . This paper improves their results and simplifies the computation of . [Copyright &y& Elsevier]

Abstract: A recent breakthrough in the theory of (type ) Macdonald polynomials is due to Haglund, Haiman and Loehr, who exhibited a combinatorial formula for these polynomials in terms of a pair of statistics on fillings of Young diagrams. The inversion statistic, which is the more intricate one, suffices for specializing a closely related formula to one for the type Hall–Littlewood -polynomials (spherical functions on -adic groups). An apparently unrelated development, at the level of arbitrary finite root systems, led to Schwer’s formula (rephrased and rederived by Ram) for the Hall–Littlewood -polynomials of arbitrary type. The latter formula is in terms of so-called alcove walks, which originate in the work of Gaussent–Littelmann and of the author with Postnikov on discrete counterparts to the Littelmann path model. In this paper, we relate the above developments, by deriving a Haglund–Haiman–Loehr type formula for the Hall–Littlewood -polynomials of type from Ram’s version of Schwer’s formula via a “compression” procedure. [Copyright &y& Elsevier]

Abstract: In [G. Lunardon, Semifields and linear sets of , Quad. Mat., Dept. Math., Seconda Univ. Napoli, Caserta (in press)], G. Lunardon has exhibited a construction method yielding a theoretical family of semifields of order and odd, with left nucleus , middle and right nuclei both and center . When this method gives an alternative construction of a family of semifields described in [N.L. Johnson, G. Marino, O. Polverino, R. Trombetti, On a generalization of cyclic semifields, J. Algebraic Combin. 26 (2009), 1–34], which generalizes the family of cyclic semifields obtained by Jha and Johnson in [V. Jha, N.L. Johnson, Translation planes of large dimension admitting non-solvable groups, J. Geom. 45 (1992), 87–104]. For , no example of a semifield belonging to this family is known. In this paper we first prove that, when , any semifield belonging to the family introduced in the second work cited above is not isotopic to any semifield of the family constructed in the former. Then we construct, with the aid of a computer, a semifield of order 210 belonging to the family introduced by Lunardon, which turns out to be non-isotopic to any other known semifield. [Copyright &y& Elsevier]

Abstract: A word is a fixed point of a nontrivial morphism if and is not the identity on the alphabet of . The paper presents the first polynomial algorithm deciding whether a given finite word is such a fixed point. The algorithm also constructs the corresponding morphism, which has the smallest possible number of non-erased letters. [Copyright &y& Elsevier]

Abstract: Let be a nonempty closed set with . For and , define by and We call a super-stationary set if holds for any infinite subset of . Denoting the derived set (i.e. the set of accumulating points) of and with , it is known [T. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)] that for any nonempty closed subset of such that there exists an infinite subset of with , there exists an infinite subset such that is a super-stationary set. Moreover, if for any infinite subset of , then the maximal pattern complexity [T. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)] is . Thus, the uniform complexity functions are realized by the super-stationary sets [T. Kamae, Uniform set and complexity, preprint, (downloadable from http://www14.plala.or.jp/kamae/e-kamae.htm)]. We call a super-subword of if there exists with such that . Let be the set of having no super-subword . Denote where . In this paper, we prove that the class of super-stationary sets other than coincides with the class of for nonempty finite sets . Moreover, it also coincides with the class of for nonempty finite sets , where is the set of minimal covers of . Using these expressions, we can calculate the complexity of super-stationary sets and prove that the complexity function of a super-stationary set in is either or a polynomial function of for large . We also discuss the word problems related to the super-subwords. [Copyright &y& Elsevier]

Abstract: For a graph , we denote by the adjoint polynomial of . Let denote the minimum real root of . In this paper, we characterize all the connected graphs with . [Copyright &y& Elsevier]

Abstract: Let be the chromatic polynomial of a graph . A graph is chromatically unique if for any graph , implies H is isomorphic to . For integers , , denote by the complete -partite graph that has partite sets of size and one partite set of size . Let be the set of graphs obtained from by adding a set of edges to the partite set of size such that is bipartite. If , denote the only graph in by . In this paper, we shall prove that for and , each graph is chromatically unique if and only if is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph is chromatically unique for and . [Copyright &y& Elsevier]

Abstract: A clique-transversal of a graph is a subset of vertices that meets all the cliques of . A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of . The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc () graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect graphs. [Copyright &y& Elsevier]

Abstract: In this paper, the authors investigate the question of when a partition of is an -core and also a -core when and are not relatively prime. A characterization of all such -cores is given, as well as a generating function dependent upon the polynomial generating functions for -cores when and are relatively prime. Furthermore, characterizations and generating functions are given for -cores which are self-conjugate and also for -cores. [Copyright &y& Elsevier]

Abstract: In this paper, we study exponential partial Bell polynomials and Sheffer sequences. Two new characterizations of Sheffer sequences are presented, which indicate the relations between Sheffer sequences and Riordan arrays. Several general identities involving Bell polynomials and Sheffer sequences are established, which reduce to some elegant identities for associated sequences and cross sequences. [Copyright &y& Elsevier]

Abstract: A graph is called -unique if any other graph having the same Tutte polynomial as is isomorphic to . Recently, there has been much interest in determining -unique graphs and matroids. For example, de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomials, Graphs Combin. 20 (2004) 105–119; A. de Mier, M. Noy, Tutte uniqueness of line graphs, Discrete Math. 301 (2005) 57–65] showed that wheels, ladders, Möbius ladders, square of cycles, hypercubes, and certain class of line graphs are all -unique. In this paper, we prove that the twisted wheels are also -unique. [Copyright &y& Elsevier]

Abstract: In this paper we present an algorithm to generate all minimal 3-vertex connected spanning subgraphs of an undirected graph with vertices and edges in incremental polynomial time, i.e., for every we can generate (or all) minimal 3-vertex connected spanning subgraphs of a given graph in time, where and are the number of vertices and edges of the input graph, respectively. This is an improvement over what was previously available and is the same as the best known running time for generating 2-vertex connected spanning subgraphs. Our result is obtained by applying the decomposition theory of 2-vertex connected graphs to the graphs obtained from minimal 3-vertex connected graphs by removing a single edge. [Copyright &y& Elsevier]

Abstract: In this paper, the first five sharp upper bounds on the spectral radii of unicyclic graphs with fixed matching number are presented. The first ten spectral radii over the class of unicyclic graphs on a given number of vertices and the first four spectral radii of unicyclic graphs with perfect matchings are also given, respectively. [Copyright &y& Elsevier]

Abstract: Transition polynomials for 4-regular graphs were defined by Jaeger [On transition polynomials of 4-regular graphs, in: Hahn et al. (Eds.), Cycles and Rays, Kluwer Academic Publishers, Dordrecht, 1990, pp. 123–150.]. Many polynomials with a wide range of applications in mathematics and physics are transition polynomials. Such is the case for Penrose, Martin and Kauffman bracket polynomials. The Tutte polynomial of a plane graph is also a transition polynomial (in the case ). The authors in [J.A. Ellis-Monaghan, I. Sarmiento, Medical graphs and the Penrose polynomial, Congr. Numer. 150 (2001) 211–222.] generalized Jaeger''s transition polynomials to a class of graphs including planar drawings of non-planar graphs. A further generalization was obtained in [J.A. Ellis-Monaghan, I. Sarmiento, Generalized transition polynomials, Congr. Numer. 150 (2003) 211–222.] where the authors defined transition polynomials for all Eulerian graphs. In [J.A. Ellis-Monaghan, I. Sarmiento, Medical graphs and the Penrose polynomial, Congr. Numer. 150 (2001) 211–222.] and [J.A. Ellis-Monaghan, I. Sarmiento, Generalized transition polynomials, Congr. Numer. 150 (2003) 211–222.] transition polynomials were seen as homomorphisms of Hopf algebras. Following a different approach, Aigner and Mielke [The Penrose polynomial of binary matroids, Monatsh. Math. 131 (2000) 1–13.] defined a transition polynomial for isotropic systems associated to binary matroids. In this paper we will present an overview of the very rich world of transition polynomials. [Copyright &y& Elsevier]

Abstract: In this expository paper we collect some combinatorial problems in the additive theory that can be easily solved in ordered Abelian groups. We study how such results, obtained by simple combinatorial arguments, can be extended to other Abelian groups. In many cases, best results can be obtained with the help of the so-called polynomial method that has evolved to a very powerful tool in the additive theory during the last decade. [Copyright &y& Elsevier]

Let G be a spanning subgraph of the complete bipartite graph Kn,n. In this paper, we obtain a formula relating Gc to &Gmacr;c by a integral formula of the σ-polynomial of Gc (where Gc is the complement of G, and &Gmacr; is the complement of G in Kn,n). It shows that letting G,H be the spanning subgraphs of Kn,n, then Gc and Hc are chromatically equivalent if and only if &Gmacr;c and &Hmacr;c are chromatically equivalent. [Copyright &y& Elsevier]