Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
The endomorphisms monoids of Helm graph and its generalization
Full text linkLet be a graph. Then is said to be End-regular if the set of all endomorphisms of forms a regular monoid. In this paper, we discuss the End-regularity of Helm graphs and our generalization. We also prove that the generalized Helm graph is End-orthodox if and only if it is End-regular. Moreover, we investigate the End-regularity of the join of two generalized Helm graphs
Pushes in words-a primitive sorting algorithm
Full text linkWe define the statistic of a push for words on an alphabet and use this to obtain a generating function measuring the degree to which an arbitrary word deviates from sorted order. Several subsidiary concepts are investigated: the number of cells that are not pushed, the number of already sorted columns, the number of cells that coincide before and after pushing, the fixed cells in words and finally, the frictionless pushes
On uniformly resolvable -designs
Full text linkIn this paper we consider the uniformly resolvable decompositions of the complete graph minus a 1-factor into subgraphs where each resolution class contains only blocks isomorphic to the same graph. We completely determine the spectrum for the case in which all the resolution classes consist of either 4-cycles or 3-stars
Coverings with congruent and non-congruent hyperballs generated by doubly truncated Coxeter orthoschemes
Full text linkAfter the investigation of the congruent and non-congruent hyperball packings related to doubly truncated Coxeter orthoscheme tilings [Acta Univ. Sapientiae, Mathematica, 11, 2 (2019), 437–459], we consider the corresponding covering problems. In Non-fundamental trunc-simplex tilings and their optimal hyperball packings and coverings in hyperbolic space the authors gave a partial classification of supergroups of some hyperbolic space groups whose fundamental domains will be integer parts of truncated tetrahedra, and determined the optimal congruent hyperball packing and covering configurations belonging to some of these classes.
In this paper, we complement these results with the investigation of the non-congruent covering cases and the remaining congruent cases. We prove, that between congruent and non-congruent hyperball coverings the thinnest belongs to the Coxeter tiling with density . This covering density is smaller than the conjectured lower bound density of L. Fejes Tóth for coverings with balls and horoballs.
We also study the local packing arrangements related to (6< u < 7, ~ u\in \mathbb{R}) doubly truncated orthoschemes and the corresponding hyperball coverings. We prove, that these coverings are achieved their minimum density at parameter with covering density which is smaller than the above record-small density, but this hyperball arrangement related to this locally optimal covering can not be extended to the entire .
Moreover, we see that in the hyperbolic plane the universal lower bound of the congruent circle, horocycle, hypercycle covering density can be approximated arbitrarily well also with non-congruent hypercycle coverings generated by doubly truncated Coxeter orthoschemes
On spectrum of connected graphs
No full textLet be a connected graph with , the -spectral radius of is defined to be the spectral radius of the matrix , defined as , where is a transmission diagonal matrix of and denotes the distance matrix of . In this paper, we give some sharp upper and lower bounds for the -spectral radius with respect to different graph parameters
The simplicity index of tournaments
Full text linkAn -tournament with vertex set is simple if there is no subset of such that and for every , either or . The simplicity index of an -tournament is the minimum number of arcs whose reversal yields a nonsimple tournament. Müller and Pelant (1974) proved that , and that equality holds if and only if is doubly regular. As doubly regular tournaments exist only if , s(T)<(n-1)/2 for . In this paper, we study the class of -tournaments with maximal simplicity index for
Metric properties of incomparability graphs with an emphasis on paths
Full text linkWe describe some metric properties of incomparability graphs. We consider the problem of the existence of infinite paths, either induced or isometric, in the incomparability graph of a poset. Among other things, we show that if the incomparability graph of a poset is connected and has infinite diameter, then it contains an infinite induced path. Furthermore, if the diameter of the set of vertices of degree at least is infinite, then the graph contains as an induced subgraph either a comb or a kite
Brooks\u27 theorem for 2-fold coloring
Full text linkThe two-fold chromatic number of a graph is the minimum number of colors needed to ensure that there is a way to color the graph so that each vertex gets two distinct colors, and adjacent vertices have no colors in common. The Ore degree is the maximum sum of degrees of an edge in a graph. We prove that, for 2-connected graphs, the two-fold chromatic number is at most the Ore degree, unless G is a complete graph or an odd cycle
Designs for graphs with six vertices and ten edges - II
Full text linkThe design spectrum has been determined for ten of the 15 graphs with six vertices and ten edges. In this paper, we solve the design spectrum problem for the remaining five graphs with three possible exceptions
Homothetic covering of convex hulls of compact convex sets
Full text linkLet be a compact convex set and be a positive integer. The covering functional of with respect to is the smallest such that can be covered by translates of . Estimations of the covering functionals of convex hulls of two or more compact convex sets are presented. It is proved that, if a three-dimensional convex body is the convex hull of two compact convex sets having no interior points, then the least number of smaller homothetic copies of needed to cover is not greater than and if and only if is a parallelepiped