Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
Combinatorial settlement planning
Full text linkIn this article, we consider a combinatorial settlement model on a rectangular grid where at least one side (east, south, or west) of each house must be exposed to sunlight without obstructions. We are interested in maximal configurations, where no additional houses can be added. For a fixed grid, we explicitly calculate the lowest number of houses, and give close to optimal bounds on the highest number of houses that a maximal configuration can have. Additionally, we provide an integer programming formulation of the problem and solve it explicitly for small values of and
Structural theory of trees II. Completeness and completions of trees
Full text linkTrees are partial orderings where every element has a linearly ordered set of smaller elements. We define and study several natural notions of completeness of trees, extending Dedekind completeness of linear orders and Dedekind-MacNeille completions of partial orders. We then define constructions of tree completions that extend any tree to a minimal one satisfying the respective completeness property
On a generalized basic series and Rogers-Ramanujan type identities
Full text linkIn this paper, we give the generalization of MacMahon\u27s type combinatorial identities. A generalized -series is interpreted as the generating function of two different combinatorial objects, viz., restricted -color partitions and weighted lattice paths which give entirely new Rogers–Ramanujan–MacMahon type combinatorial identities. This result yields an infinite class of 2-way combinatorial identities which further extends the work of Agarwal and Goyal. We also discuss the bijective proof of the main result. Forbye, eight particular cases are also discussed which give a combinatorial interpretation of eight entirely new Rogers–Ramanujan type identities
On signs of certain Toeplitz-Hessenberg determinants whose elements involve Bernoulli numbers: On negativity and positivity of Hessenberg determinants
No full textIn the paper, by virtue of Wronski\u27s formula and Kaluza\u27s theorem related to a power series and its reciprocal, by means of Cahill and Narayan\u27s recursive relation, and with the aid of the logarithmic convexity of the sequence of the Bernoulli numbers, the author presents the signs of certain Toeplitz-Hessenberg determinants whose elements involve the Bernoulli numbers and combinatorial numbers. Moreover, with the help of a derivative formula for the ratio of two differentiable functions, the author provides an alternative proof of Wronski\u27s formula
Beck-type companion identities for Franklin\u27s identity
Full text linkIn 2017, Beck conjectured that the difference in the number of parts in all partitions of into odd parts and the number of parts in all strict partitions of is equal to the number of partitions of whose set of even parts has one element, and also to the number of partitions of with exactly one part repeated. Andrews proved the conjecture using generating functions. Beck\u27s identity is a companion identity to Euler\u27s identity. The theorem has been generalized (with a combinatorial proof) by Yang to a companion identity to Glaisher\u27s identity. Franklin generalized Glaisher\u27s identity, and in this article, we provide a Beck-type companion identity to Franklin\u27s identity and prove it both analytically and combinatorially. Andrews\u27 and Yang\u27s respective theorems fit naturally into this very general frame. We also discuss how Franklin\u27s identity and the companion Beck-type identities can be further generalized to Euler pairs of any order
Total dominator total coloring of a graph
Full text linkHere, we initiate to study the total dominator total coloring of a graph which is a total coloring of the graph such that each object of the graph is adjacent or incident to every object of some color class. In more details, while in section 2 we present some tight lower and upper bounds for the total dominator total chromatic number of a graphs in terms of some parameters such as order, size, the total dominator chromatic and total domination numbers of the graph and its line graph, in section 3 we restrict our to trees and present a Nordhaus-Gaddum-like relation for trees. Finally in last section we show that there exist graphs that their total dominator total chromatic numbers are equal to their orders
Hamilton cycles in bidirected complete graphs
Full text linkZaslavsky observed that the topics of directed cycles in directed graphs and alternating cycles in edge 2-colored graphs have a common generalization in the study of coherent cycles in bidirected graphs. There are classical theorems by Camion, Harary and Moser, Häggkvist and Manoussakis, and Saad which relate strong connectivity and Hamiltonicity in directed "complete" graphs and edge 2-colored "complete" graphs. We prove two analogues to these theorems for bidirected "complete" signed graphs
Heesch numbers of unmarked polyforms
Full text linkA shape\u27s Heesch number is the number of layers of copies of the shape that can be placed around it without gaps or overlaps. Experimentation and exhaustive searching have turned up examples of shapes with finite Heesch numbers up to six, but nothing higher. The computational problem of classifying simple families of shapes by Heesch number can provide more experimental data to fuel our understanding of this topic. I present a technique for computing Heesch numbers of nontiling polyforms using a SAT solver, and the results of exhaustive computation of Heesch numbers up to 19-ominoes, 17-hexes, and 24-iamonds
Spirals in Periodic Tilings
Full text linkSpiral tilings, as appealing as they are for their aesthetics, have not been studied well mathematically. One of the difficulties in this area of tiling theory is providing a mathematical definition of spiral tilings. A recently published attempt at providing a formal definition distinguishes a so-called L-spiral tiling (L-tiling) and an S-spiral tiling (S-tiling), with the two types being characterized by special properties of tile set partitions. Based on these existing definitions, we investigate the spiral structure in periodic tilings. Unlike spiral tilings, periodic tilings lend themselves easily to a definition and have been well studied. We first prove that it is not possible for periodic tilings to be S-tilings. We then study a subset of periodic tilings that can be L-tilings. In particular, we demonstrate that there exist examples for each type of isohedral tilings (a subset of periodic monohedral tilings) that are L-spirable
Refining overpartitions by properties of non-overlined parts
Full text linkWe study new classes of overpartitions of numbers based on the properties of non-overlined parts. Several combinatorial identities are established by means of generating functions and bijective proofs. We show that our enumeration function satisfies a pair of infinite Ramanujantype congruences modulo 3. Lastly, by conditioning on the overlined parts of overpartitions,we give a seemingly new identity between the number of overpartitions and a certain class of ordinary partition functions. A bijective proof for this theorem also includes a partial answer to a previous request for a bijection on partitions doubly restricted by divisibility and frequency