Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
Latin Squares and their Bruhat Order
Get PDFIn this paper we investigate the Bruhat order on the class of Latin squares. We study its cover relation and minimal elements. We prove that the class of Latin squares of order , with , has at least two minimal elements, and we present a process to construct some minimal Latin squares for this relation
Hyperball packings related to truncated cube and octahedron tilings in hyperbolic space
Get PDFIn this paper, we study congruent and noncongruent hyperball (hypersphere) packings to the truncated regular cube and octahedron tilings. These are derived from the Coxeter truncated orthoscheme tilings (6< p \in \mathbb{N}) and (4< p \in \mathbb{N}), respectively, by their Coxeter reflection groups in hyperbolic space . We determine the densest hyperball packing arrangement and its density with congruent and noncongruent hyperballs.
We prove that the locally densest (noncongruent half) hyperball configuration belongs to the truncated cube with a density of approximately if we allow 6< p \in \mathbb{R} for the dihedral angle . This local density is larger than the B\"or\"oczky--Florian density upper bound for balls and horoballs. But our locally optimal noncongruent hyperball packing configuration cannot be extended to the entire hyperbolic space . We determine the extendable densest noncongruent hyperball packing arrangement to the truncated cube tiling with a density of approximately
On the first two entries of the f-vectors of 6-polytopes
Get PDFIn 1906, Steinitz gave a complete characterization of the first two entries of the -vectors of -polytopes, while Grünbaum obtained a similar result for -polytopes in his well-known book published in 1967. Recently, Kusunoki and Murai and independently Pineda-Villavicencio, Ugon, and Yost completely determined the first two entries of the -vectors of -polytopes. This paper can be regarded as a continuation of their works for -polytopes. To be more precise, let denote the number of vertices of a -polytope. The aim of this paper is to show that, when the number of edges is greater than or equal to and , we can completely characterize the first two entries of the -vectors of -polytopes. As a consequence, for we also give a complete characterization of the first two entries of the -vectors of -polytopes except for three cases , , and
Further generalizations of the parallelogram law
Get PDFIn a recent work of Alessandro Fonda, a generalization of the parallelogram law in any dimension was given by considering the ratio of the quadratic mean of the measures of the -dimensional diagonals to the quadratic mean of the measures of the faces of a parallelotope. In this paper, we provide a further generalization considering not only -dimensional diagonals and faces, but the -dimensional ones for every
Degree sequence of the generalized Sierpiński graph
Get PDFSierpiński graphs are studied in fractal theory and have applications in diverse areas including dynamic systems, chemistry, psychology, probability, and computer science. Polymer networks and WK-recursive networks can be modeled by generalized Sierpiński graphs. The degree sequence of (ordinary) Sierpi\\u27nski graphs and Hanoi graphs (and some of their topological indices) are determined in the literature. The number of leaves (vertices of degree one) of the generalized Sierpiński graph of any tree was determined in 2017 and in terms of , , and the number of leaves of the base graph . In this paper, we generalize these results. More precisely, for every simple graph of order , we completely determine the degree sequence of the generalized Sierpiński graph of in terms of , and the degree sequence of . By using it, we determine the exact value of the general first Zagreb index of in terms of the same parameters of
Triple product sums of Catalan triangle numbers
Get PDFBy means of quadratic transformations for the well-poised hypergeometric series, several reduction and transformation formulae are derived for the triple product sums of Catalan triangle numbers. One of them confirms a conjecture made recently by Miana, Ohtsuka and Romero [18, 2017]
Equality Perfect Graphs and Digraphs
Get PDFIn the graph colouring game introduced by Bodlaender [7], two players, Alice and Bob, alternately colour uncoloured vertices of a given graph with one of colours so that adjacent vertices receive different colours. Alice wins if every vertex is coloured at the end. The game chromatic number of is the smallest such that Alice has a winning strategy.
In Bodlaender\u27s original game, Alice begins. We also consider variants of this game where Bob begins or skipping turns is allowed [1] and their generalizations to digraphs [2]. By means of forbidden induced subgraphs (resp.\ forbidden induced subdigraphs), for several pairs of such graph (resp.\ digraph) colouring games and~, which define game chromatic numbers and~, we characterise the classes of graphs (resp.\ digraphs) such that, for any induced subgraph (resp.\ subdigraph)~, the game chromatic numbers and of~ are equal
Factorizations of complete graphs into cycles and 1-factors
Get PDFIn this paper, we consider factorizations of complete graph into cycles and --factors. We will focus on the existence of factorizations of containing two nonisomorphic factors. We obtain all possible solutions for uniform factors involving --cycles and --factors with a few possible exceptions when is odd
Two properties of maximal antichains in strict chain product posets
Get PDFWe present two results on maximal antichains in the strict chain product poset . First, we prove that these maximal antichains are also maximum. Second, we prove that there is a bijection between maximal antichains in the strict chain product poset and antichains in the nonstrict chain product poset
On the uniformity of the approximation for -associated Stirling numbers of the second Kind
Get PDFThe -associated Stirling numbers of the second kind are a natural extension of Stirling numbers of the second kind. A combinatorial interpretation of -associated Stirling numbers of the second kind is the number of ways to partition elements into subsets such that each subset contains at least elements. Calculating the associated Stirling numbers is typically done with a recurrence relation or a generating function that are computationally expensive or alternatively with a closed-form that is practical for only a limited parameter range. In 1994 Hennecart proposed an approximation for the -associated Stirling numbers that is fast to compute, is amenable to analysis over a wide range of parameters, and is conjectured to be asymptotically tight. There are a few other approximations for the associated Stirling numbers, but none of them are as general as Hennecart\u27s. However, until this work, Hennecart\u27s approximation had been utilized without a proper justification due to the absence of a rigorous proof. This work provides a proof of the uniformity of the Hennecart approximation