Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
Combinatorial interpretations of two identities of Guo and Yang
Get PDFThe restricted partitions in which the largest part is less than or equal to and the number of parts is less than or equal to were investigated by Andrews. These partitions were extended recently by the author to partitions into parts of two kinds. In this paper, we use a new class of restricted partitions into parts of two kinds to provide new combinatorial interpretations for two identities of Guo and Yang
A neighborhood condition for graphs to have restricted fractional (g,f)-factors
Get PDFLet be a function defined on with for any . Set . If for every , then we call the graph with vertex set and edge set a fractional -factor of with indicator function , where E_h=\{e:e\in E(G),h(e)>0\}. Let and be two sets of independent edges of with , and . If admits a fractional -factor such that for any and for any , then we say that has a fractional -factor with the property . In this paper, we present a neighborhood condition for the existence of a fractional -factor with the property in a graph. Furthermore, it is shown that the neighborhood condition is sharp
Geometric polynomials and integer partitions
Get PDFIn this paper, we show that the geometric polynomials can be expressed as sums over integer partitions in two different ways. New formulas involving geometric numbers, Bernoulli numbers, and Genocchi numbers are derived in this context
Lengths of extremal square-free ternary words
Get PDFA square-free word over a fixed alphabet is extremal if every word obtained from by inserting a single letter from (at any position) contains a square. Grytczuk et al. recently introduced the concept of extremal square-free word and demonstrated that there are arbitrarily long extremal square-free ternary words. We find all lengths which admit an extremal square-free ternary word. In particular, we show that there is an extremal square-free ternary word of every sufficiently large length. We also solve the analogous problem for circular words
Graphs where each spanning tree has a perfect matching
Get PDFAn edge subset of a connected graph is called an anti-Kekul\\u27{e} set if is connected and has no perfect matching. We can see that a connected graph has no anti-Kekul\\u27{e} set if and only if each spanning tree of has a perfect matching. In this note, we characterize all graphs where each spanning tree has a perfect matching. In addition, we show that if is a connected graph of order for a positive integer and size whose each spanning tree has a perfect matching, then , with equality if and only if
Coloring permutation-gain graphs
Get PDFCorrespondence colorings of graphs were introduced in 2018 by Dvořák and Postle as a generalization of list colorings of graphs which generalizes ordinary graph coloring. Kim and Ozeki observed that correspondence colorings generalize various notions of signed-graph colorings which again generalizes ordinary graph colorings. In this note we state how correspondence colorings generalize Zaslavsky\u27s notion of gain-graph colorings and then formulate a new coloring theory of permutation-gain graphs that sits between gain-graph coloring and correspondence colorings. Like Zaslavsky\u27s gain-graph coloring, our new notion of coloring permutation-gain graphs has well defined chromatic polynomials and lifts to colorings of the regular covering graph of a permutation-gain graph
Problems Section BIRS Proceedings
No full textThe workshop ”Homogeneous Structures, A Workshop inHonour of Norbert Sauer‘s 70th Birthday” took place at the Banff International Research Station from November 8th to November 13th,2015. The purpose of the following note is to gather the list of openproblems that were posed during the problem sessions. Contributionsappear in alphabetical order, according to the name of their auth
Reconstructing the topology on monoids and polymorphism clones of reducts of the rationals
Get PDFWe extend results from an earlier paper giving reconstruction results for the endomorphism monoid of the rational numbers under the strict and reflexive relations to the first order reducts of the rationals and the corresponding polymorphism clones. We also give some similar results about the coloured rationals
A subspace based subspace inclusion graph on vector space
Get PDFLet be a fixed -dimensional subspace of an -dimensi\-onal vector space such that In this paper, we introduce a graph structure, called the subspace based subspace inclusion graph where the vertex set is the collection of all subspaces of such that and i.e., and any two distinct vertices and of are adjacent if and only if either or The diameter, girth, clique number, and chromatic number of are studied. It is shown that two subspace based subspace inclusion graphs and are isomorphic if and only if and are isomorphic. Further, some properties of are obtained when the base field is finite
Bounds of characteristic polynomials of regular matroids
Get PDFA regular chain group is the set of integral vectors orthogonal to rows of a matrix representing a regular matroid, i.e., a totally unimodular matrix. Introducing canonical forms of an equivalence relation generated by and a special basis of , we improve several results about polynomials counting elements of and find new bounds and formulas for these polynomials