Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
Induced Subgraphs of Bounded Degree and Bounded Treewidth
Full text linkWe prove that for all integers and , every graph with treewidth at most has a `large\u27 induced subgraph , where has treewidth at most and every vertex in has degree at most in . The order of depends on , , , and the order of . With , we obtain large sets of bounded degree vertices. With , we obtain large independent sets of bounded degree. In both these cases, our bounds on the order of are tight. For bounded degree independent sets in trees, we characterise the extremal graphs. Finally, we prove that an interval graph with maximum clique size has a maximum independent set in which every vertex has degree at most
Best Simultaneous Diophantine Approximations under a Constraint on the Denominator
Full text linkWe investigate the problem of best simultaneous Diophantine
approximation under a constraint on the denominator, as proposed by
Jurkat. New lower estimates for optimal approximation constants are
given in terms of critical determinants of suitable star bodies.
Tools are results on simultaneous Diophantine approximation of
rationals by rationals with smaller denominator. Finally, the
approximation results are applied to the decomposition of integer
vectors
On primitive symmetric association schemes with m_1=3
Full text linkWe classify primitive symmetric association schemes with
m_1 = 3. Namely, it is shown that the tetrahedron, i.e., the association scheme of the complete graph K_4, is the unique such association scheme. Our proof of this result is based on the spherical embeddings of association schemes and elementary three dimensional Euclidean geometry
Sum and product of different sets
Full text linkLet A and B be two finite sets of numbers.
The sum set and the product set of A, B are A + B = {a + b : a in A, b in B}, and
AB = {ab : a in A, b in B}. $ We prove that A+B is as large as
possible when AA is not too big. Similarly, AB is large when
A+A is not too big. The methods rely on the Lambda_p constant
of A, bound on the number of factorizations in a generalized
progression containing A, and the subspace theorem
N-free extensions of posets. Note on a theorem of P.A.Grillet
Full text linkLet be the poset obtained by adding a dummy vertex on each diagonal edge of the \u27s of a finite poset . We show that is -free. It follows that this poset is the smallest -free barycentric subdivision of the diagram of , poset whose existence was proved by P.A. Grillet. This is also the poset obtained by the algorithm starting with and consisting at step of adding a dummy vertex on a diagonal edge of some in , proving that the result of this algorithm does not depend upon the particular choice of the diagonal edge choosen at each step. These results are linked to drawing of posets
Uniquely circular colourable and uniquely fractional colourable graphs of large girth
Full text linkGiven any rational numbers and an integer , we
prove that there is a graph of girth at least , which is
uniquely -colourable and uniquely -fractional colourable