Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
Canonical cuts of path powers
Full text linkThe MaxCut problem aims to find a bipartition of vertices in a given graph such that the number of edges with one end vertex in each part is maximum among all bipartitions. NP-hardness when restricted to interval graphs has been recently announced. Surprisingly, all previously published attempts at polynomial-time algorithms for unit interval graphs turned out to be wrong, which justifies the search for subclasses where MaxCut can be handled. We introduce canonical cuts whose pattern allows an easy computation of the cut size for the power of paths . Using canonical cuts, we calculate the structure and the size of maximum cuts for and for . We prove that the known size for a maximum cut for reduced co-bipartite chain graphs can be achieved by a canonical cut. We perform computational experiments on each graph with and show that most of them allow a canonical cut that is maximum. We display a table with the found cases where there is no canonical cut which is a maximum cut. In these graphs, the difference between the maximum cut and some canonical is at most 3 units. This indicates canonical cuts as a good approach to tackle the maximum cut on graphs
Reflexible covers of prisms
Full text linkThe Tomotope provided the first well understood example of an abstract 4-polytope whose connection (monodromy) group was not a string C-group, and which also did not have a unique minimal regular cover. Conversely, we know that if the connection group of a polytope is a string C-group (if the polytope is C-connected), then the polytope will have a unique minimal regular cover. Since the discovery of the Tomotope, an active area of investigation has been determining which abstract -polytopes are C-connected and the ways various constructions for abstract polytopes result in polytopes that do or do not possess unique minimal regular covers. In the current work we show that the prism over every abstract polyhedron is C-connected, or equivalently, that it has a unique minimal regular cover. We also describe a conjecture positing a general condition on the C-connectedness of prisms over polytopes that is independent of rank
Combinatorial results for order-preserving partial injective contraction mappings
Full text linkLet be the symmetric inverse semigroup on . Let be the subsemigroup of consisting of all order-preserving injective partial contraction mappings, and let be the subsemigroup of consisting of all order-preserving and order-decreasing injective partial contraction mappings of . In this paper, we investigate the cardinalities of some equivalences on and which lead naturally to obtaining the order of these semigroups. Then, we relate the formulae obtained to Fibonacci numbers. Similar results about , the semigroup of order-preserving or order-reversing injective partial contraction mappings, are deduced
The Lifting Properties for A-Homotopy Theory
Full text linkIn classical homotopy theory, two spaces are considered homotopy equivalent if one space can be continuously deformed into the other. This theory, however, does not respect the discrete nature of graphs. For this reason, a discrete homotopy theory that recognizes the difference between the vertices and edges of a graph was invented, called A-homotopy theory \cite{Atkin1, Atkin2, BabsonHomotopy, BarceloFoundations, BarceloPerspectives}. In classical homotopy theory, covering spaces and lifting properties are often used to compute the fundamental group of the circle. In this paper, we develop the lifting properties for A-homotopy theory. Using a covering graph and these lifting properties, we compute the fundamental group of the cycle , giving an alternate approach to [4]
A note on total co-independent domination in trees
Full text linkA set of vertices of a graph is a total dominating set if every vertex of is adjacent to at least one vertex in . The total dominating set is called a total co-independent dominating set if is an independent set and has at least one vertex. The minimum cardinality of any total co-independent dominating set is denoted by . In this paper, we show that, for any tree of order and diameter at least three, where is the maximum cardinality of any independent set and is the set of leaves of . We also characterize the families of trees attaining the extremal bounds above and show that the differences between the value of and these bounds can be arbitrarily large for some classes of trees
A new trigonometric identity with applications
Full text linkIn this paper we obtain a new curious identity involving trigonometric functions. Namely, for any positive odd integer , we prove that which is equivalent to the identity where stands for the th Chebyshev polynomial of the second kind. As a consequence, for any positive odd integer and positive integer , we obtain the identity where denotes the Bernoulli polynomial of degree
Resolvability in Hypergraphs
Full text linkThis article presents an extension of the study of metric and partition dimension to hypergraphs. We give sharp lower bounds for the metric and partition dimension of hypergraphs in general and give exact values under specified conditions
Further Rogers-Ramanujan type identities for modified lattice paths
Full text linkRecently, the authors introduced the modified lattice paths which generalize Agarwal-Bressoud weighted lattice paths. Using these new objects they interpreted combinatorially two basic series identities which led to two new combinatorial Rogers-Ramanujan type identities. In this paper we obtain three more Rogers-Ramanujan type identities for modified lattice paths. This also leads to three new 3-way combinatorial identities
Structural theory of trees I. Branching and condensations of trees
Full text linkTrees are partial orders in which every element has a linearly ordered set of predecessors. Here we initiate the exploration of the structural theory of trees with the study of different notions of branching in trees and of condensed trees, which are trees in which every node is a branching node. We then introduce and investigate two different constructions of tree condensations-one shrinking, and the other expanding, the tree to a condensed tree
The localization number and metric dimension of graphs of diameter 2
Full text linkWe consider the localization number and metric dimension of certain graphs of diameter , focusing on families of Kneser graphs and graphs without 4-cycles. For the Kneser graphs with a diameter of , we find upper and lower bounds for the localization number and metric dimension, and in many cases these parameters differ only by an additive constant. Our results on the metric dimension of Kneser graphs improve on earlier ones, yielding exact values in infinitely many cases. We determine bounds on the localization number and metric dimension of Moore graphs of diameter and polarity graphs