Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
Canonical functions: a proof via topological dynamics
Get PDFCanonical functions are a powerful concept with numerous applications in the study of groups, monoids, and clones on countable structures with Ramsey-type properties. In this short note, we present a proof of the existence of canonical functions in certain sets using topological dynamics, providing a shorter alternative to the original combinatorial argument. We moreover present equivalent algebraic characterisations of canonicity
Oriented unicyclic graphs with minimal skew Randić energy
Get PDFLet be a simple graph with vertex set , and be an orientation of . Denote by the degree of the vertex for . The skew Randić matrix of , denoted by , is the real skew-symmetric matrix , where and if is an arc of , otherwise . The skew Randi\\u27{c} energy of is defined as the sum of the norms of all the eigenvalues of . In this paper, the oriented unicyclic graphs with minimal skew Randić energy are determined
New cyclic Kautz digraphs with optimal diameter
Get PDFWe obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree, there is no other digraph with a smaller diameter. This new family of digraphs are called `modified cyclic digraphs\u27 , and it is derived from the Kautz digraphs and from the so-called cyclic Kautz digraphs . The cyclic Kautz digraphs were defined as the digraphs whose vertices are labeled by all possible sequences of length , such that each character is chosen from an alphabet of distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and also requiring that . Their arcs are between vertices and , with and . Since do not have minimal diameter for their number of vertices, we construct the modified cyclic Kautz digraphs to obtain the same diameter as in the Kautz digraphs, and we also show that are -out-regular. Moreover, for , we compute the number of vertices of the iterated line digraphs
Homotopy Type of Independence Complexes of Certain Families of Graphs
Get PDFWe show that the independence complexes of generalised Mycielskian of complete graphs are homotopy equivalent to a wedge sum of spheres, and determine the number of copies and the dimensions of these spheres. We also prove that the independence complexes of categorical product of complete graphs are wedge sum of circles, upto homotopy. Further, we show that if we perturb a graph in a certain way, then the independence complex of this new graph is homotopy equivalent to the suspension of the independence complex of
On the real roots of domination polynomials
Get PDFA dominating set of a graph of order is a subset of the vertices of such that every vertex is either in or adjacent to a vertex of . The domination polynomial is defined by where is the number of dominating sets in with cardinality . In this paper we show that the closure of the real roots of domination polynomials is
Bounds on r-identifying codes in q-ary Lee space
Get PDFIdentifying codes are used to locate malfunctioning processors in multiprocessor systems. In this paper, we study identifying codes in a -ary hypercube which is used in parallel processing. Computing upper and lower bounds of the smallest cardinality among all -identifying codes in with respect to the Lee metric, is an important research problem in this area. Using our constructions, we produce tables for upper and lower bounds for . The upper and the lower bounds of known only when but using our results, we compute the bounds for for all . Also we improve upon the currently known upper bounds of due to J. L. Kim and S. J. Kim. Upper bounds of for q>4 are known previously for some cases of . We improve some of these bounds and we also compute bounds for all by using our results
Bailey and Daum\u27s q-Kummer Theorem and Extensions
Get PDFBy means of the linearization method, we establish four analytical formulae for the -Kummer sum extended by two integer parameters. Ten closed formulae are presented as examples
Polytopal balls arising in optimization
Get PDFWe study a family of polytopes and their duals, that appear in various optimization problems as the unit balls for certain norms. These two families interpolate between the hypercube, the unit ball for the -norm, and its dual cross-polytope, the unit ball for the -norm. We give combinatorial and geometric properties of both families of polytopes such as their -vector, their volume, and the volume of their boundary
Schröder partitions, Schröder tableaux and weak poset patterns
No full textWe introduce the notions of Schröder shapes and Schröder tableaux, which provide an analog of the classical notions of Young shapes and Young tableaux. We investigate some properties of the partial order given by containment of Schröder shapes. Then we propose an algorithm that is the natural analog of the well-known RS correspondence for Young tableaux, and we characterize those permutations whose insertion tableaux have some special shapes. The last part of the article relates the notion of the Schröder tableau with those of interval order and weak containment (and strong avoidance) of posets. We end our paper with several suggestions for possible further work
Symmetric association schemes arising from abstract regular polytopes
Get PDFThis article investigates the question of when every double coset of a string -group relative to its vertex stabilizer subgroup is represented by an involution. We show that this is the case for every finite string Coxeter group except in the case of type , and for the infinite Coxeter groups of Schläfli type and . From this it is immediate that, for every string -group of these types, the double coset algebra is commutative and all of its characters are realizable over . In particular, the abstract regular polytopes with these automorphism groups have a polyhedral realization cone