Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
Some notes on generic rectangulations
Full text linkA rectangulation is a subdivision of a rectangle into rectangles. A generic rectangulation is a rectangulation that has no crossing segments. We explain several observations and pose some questions about generic rectangulations. In particular, we show how one may "centrally invert" a generic rectangulation about any given rectangle, analogous to reflection across a circle in classical geometry. We also explore 3-dimensional orthogonal polytopes related to "marked" rectangulations and drawings of planar maps. These observations arise from viewing a generic rectangulation as topologically equivalent to a sphere
Kn(λ) is fully {P5,C6}-decomposable
Full text linkLet denote a path of length , denote a cycle of length , and denote the complete multigraph on vertices in which every edge is taken times. In this paper, we have obtained the necessary conditions for a -decomposition of and proved that the necessary conditions are also sufficient when and
Some relational structures with polynomial growth and their associated algebras II. Finite generation.
Full text linkThe profile of a relational structure is the function which counts for every nonnegative integer the number, possibly infinite, of substructures of induced on the -element subsets, isomorphic substructures being identified. If takes only finite values, this is the Hilbert function of a graded algebra associated with , the age algebra introduced by P. J. Cameron. In a previous paper, we studied the relationship between the properties of a relational structure and those of its age algebra, particularly when admits a finite monomorphic decomposition. This setting still encompasses well-studied graded commutative algebras like invariant rings of finite permutation groups or the rings of quasisymmetric polynomials.
The main theorem of this paper characterizes combinatorially when the age algebra is finitely generated in this setting. For tournaments, this boils down to the profile being bounded. We further investigate how far the well known algebraic properties of invariant rings and quasisymmetric polynomials extend to age algebras; notably, we explore the Cohen-Macaulay property in the special case of invariants of permutation groupoids. Finally, we exhibit sufficient conditions on the relational structure that make naturally the age algebra into a Hopf algebra.
For a homogeneous structure with a profile bounded by a polynomial, Cameron conjectured in the early eighties that the profile is asymptotically polynomial; Macpherson further conjectured that the age algebra is finitely generated. This was proven recently by Falque and the second author. The combined results support the conjecture that---assuming finite kernel---profiles bounded by a polynomial are asymptotically polynomial, and give hope for a complete characterization of when the age algebra is finitely generated
A note on the fully degenerate Bell polynomials of the second kind
Full text linkIn the paper, the authors study new degenerating approach to the Bell polynomials which are called fully degenerate Bell polynomials of the second kind. We establish some identities from the fully degenerate Bell polynomials of the second kind, and give explicit relations to special numbers and polynomials
Degree conditions of nearly induced matching extendable graphs
Full text linkA graph is induced matching extendable (shortly, IM-extendable) if every induced matching of is included in a perfect matching of . The IM-extendable graph was first introduced by Yuan. A graph is nearly IM-extendable if is IM-extendable. We show in this paper that: (1) Let be a graph with vertices, where . If for each pair of nonadjacent vertices and in , , then is nearly IM-extendable. (2) Let be a claw-free graph with vertices, where . If for each pair of nonadjacent vertices and in , , then is nearly IM-extendable. Minimum degree conditions of nearly IM-extendable graphs and nearly IM-extendable claw-free graphs are also obtained in this paper. It is also shown that all these results are best possible
Flag vector pairs, fatness, and their bounds for 4-polytopes
Full text linkRecently Sjoberg and Ziegler showed a remarkable result that completely characterizes the flag vector pair of any -dimensional polytopes. Motivated by their results and techniques, in this paper we show some necessary conditions for other remaining flag vector pairs such as , , , and to be flag vector pairs of -dimensional convex polytopes. Results of this paper give some partial answers to the questions posed by Sj\" oberg and Ziegler. As an application of the bounds for flag vector pairs , in this paper we also provide some bounds of fatness function for certain -polytopes as well as -polytopes
Note on group distance magicness on product graphs
Full text linkIf is a bijection from the vertex set of a graph to an additive abelian group of elements such that for any vertex of , the weight is , where , then is a -distance magic labeling of . A graph that admits such an is -distance magic and if is -distance magic for every such , then is a group distance magic graph.
In this paper, we provide some results on the group distance magicness of the lexicographic and direct product of two graphs. By proving a few necessary conditions, we characterize the group distance magicness of a tree. In addition, we find three techniques to construct group distance magic graphs recursively from the existing ones and with respect to any abelian group with one involution, we determine infinitely many nongroup distance magic graphs
Completing graphs to metric spaces
Full text linkWe prove that certain classes of metrically homogeneous graphs omitting triangles of odd short perimeter as well as triangles of long perimeter have the extension property for partial automorphisms and we describe their Ramsey expansions
Equivalent classes of degree sequences for triangulated polyhedra and their convex realization
Full text linkWe define an equivalence on the set of all degree sequences of a triangulated polyhedron with a fixed number of vertices and compute them and their cardinal via an algorithm. We also prove that each class is realizable as a convex polyhedron
The estimation of the zeros of some counting polynomials
No full textIn this work we study the zeros of the Eulerian and Bell polynomials and their generalizations. More concretely, lower estimates for the leftmost zeros of these polynomials will be given, complementing earlier results where upper estimations were presented