Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
The Tutte Polynomial of Complex Reflection Groups
Get PDFThe story ”Tutte Polynomial of Reflection Group” begins in 2007 when Ardila computed the Tutte polynomials of the hyperplane arrangements associated to the symmetric groups Sym(n), and to the imprimitive groups and . One year later, De Concini and Procesi computed the Tutte polynomials associated to the primitive groups , as well as Geldon in 2009. Then, we computed those associated to the imprimitive groups in 2017. This article aims to close the chapter on the complex reflection groups by computing the Tutte polynomials associated to the primitive groups
Starred Italian domination in graphs
Get PDFAn Italian dominating function on a graph is a function such that for every vertex , where and represents the open neighbourhood of . A starred Italian dominating function on is an Italian dominating function such that is not a dominating set of . The starred Italian domination number of , denoted , is the minimum weight among all starred Italian dominating functions on .
In this article, we initiate the study of the starred Italian domination in graphs. For instance, we give some relationships that exist between this parameter and other domination invariants in graphs. Also, we present tight bounds and characterize the extreme cases. In addition, we obtain exact formulas for some particular families of graphs. Finally, we show that the problem of computing the starred Italian domination number of a graph is NP-hard
Fraïssé theory and the Poulsen simplex
No full textWe present a Fraïssé-theoretic perspective on the study of the Poulsen simplex and its properties
H-absorbence and H-independence in 3-quasi-transitive H-coloured digraphs.
Get PDFIn this paper we prove that if is a loopless asymmetric 3-quasi-transitive arc-coloured digraph having its arcs coloured with the vertices of a given digraph , and if in every is an -cycle and every is a quasi--cycle, then has an -kernel
On the homotopy type of complexes of graphs with bounded domination number
Get PDFLet be the complex of graphs on vertices and domination number at least~. We prove that has the homotopy type of a finite wedge of 2-spheres. This is done by using discrete Morse theory techniques. Acyclicity of the needed matching is proved by introducing a relativized form of a well known method for constructing acyclic matchings on suitable chunks of simplices. Our approach allows us to extend our results to the realm of infinite graphs. In addition, we give evidence supporting the assertion that the homotopy equivalences and do not seem to generalize for with
Conant\u27s generalised metric spaces are Ramsey
Get PDFWe give Ramsey expansions of classes of generalised metric spaces where distances come from a linearly ordered commutative monoid. This complements results of Conant about the extension property for partial automorphisms and extends an earlier result of the first and the last author giving the Ramsey property of convexly ordered -metric spaces. Unlike Conant\u27s approach, our analysis does not require the monoid to be semiarchimedean
k-Forcing number for Cartesian product of some graphs
No full text-Forcing is an iterative graph coloring process based on a color change rule that describes how to color the vertices. -Forcing is a generalization of zero forcing that is useful in multiple scientific branches, such as quantum control. In this paper, we investigate the -forcing number of the Cartesian product of some graphs. The main contribution of this paper is to determine the -forcing number of the Cartesian product of two complete bipartite graphs using a new representation of this graph
A survey of graph burning
Get PDFGraph burning is a deterministic, discrete-time process that models how influence or contagion spreads in a graph. Associated to each graph is its burning number, which is a parameter that quantifies how quickly the influence spreads. We survey results on graph burning, focusing on bounds, conjectures, and algorithms related to the burning number. We will discuss state-of-the-art results on the burning number conjecture, burning numbers of graph classes, and algorithmic complexity. We include a list of conjectures, variants, and open problems on graph burning
Direct and inverse problems for restricted signed sumsets in integers
Get PDFLet be a nonempty finite subset of an additive abelian group . For a positive integer , we let
be the -fold restricted signed sumset of . The direct problem for the restricted signed sumset is to find the minimum number of elements in in terms of , where is the cardinality of . The {\it inverse problem} for the restricted signed sumset is to determine the structure of the finite set for which the minimum value of is achieved. In this article, we solve some cases of both direct and inverse problems for in the group of integers. In this connection, we also mention some conjectures in the remaining cases
Siblings of an ℵ0-categorical relational structure
Get PDFA sibling of a relational structure is any structure which can be embedded into and, vice versa, such that can be embedded into . Let be the number of siblings of , these siblings being counted up to isomorphism. Thomassé conjectured that for countable relational structures made of at most countably many relations, is either one, countably infinite, or the size of the continuum; but even showing the special case is one or infinite is unsettled when is a countable tree.
We prove that if is countable and -categorical, then indeed is one or infinite. Furthermore, is one if and only if is finitely partitionable in the sense of Hodkinson and Macpherson [14]. The key tools in our proof are the notion of monomorphic decomposition of a relational structure introduced in [35] and studied further in [23], [24], and a result of Frasnay [11]