Hopkins, Sam
Published in
Discrete Mathematics

We present a new proof of the monomial case of Wilmes’ conjecture, which gives a formula for the coarsely-graded Betti numbers of the G-parking function ideal in terms of maximal parking functions of contractions of G. Our proof is via poset topology and relies on a theorem of Gasharov, Peeva, and Welker (1999) that connects the Betti numbers of a ...

Ille, P. Villemaire, R.
Published in
Discrete Mathematics

Given a graph G, a subset M of V(G) is a module of G if for each v∈V(G)∖M, v is adjacent to all the elements of M or to none of them. A graph G is prime if |V(G)|≥4 and the only modules of G are V(G), 0̸, and singleton vertex sets. Given a prime induced subgraph G[X], we introduce a digraph that yields a necessary and sufficient condition for G to ...

Rudolph-Lilith, Michelle Muller, Lyle E.
Published in
Discrete Mathematics

One of the simplest polynomial recursions exhibiting chaotic behavior is the logistic map xn+1=axn(1−xn) with xn,a∈Q:xn∈[0,1]∀n∈N and a∈(0,4], the discrete-time model of the differential growth introduced by Verhulst almost two centuries ago (Verhulst, 1838) [12]. Despite the importance of this discrete map for the field of nonlinear science, expli...

Bonamy, Marthe Bousquet, Nicolas
Published in
Discrete Mathematics

We prove that for k≥3, the chromatic number of k-th powers of graphs of maximum degree Δ≥3 can be bounded in a more refined way than with Brooks’ theorem, even in the case of online list coloring.

Meunier, Frédéric
Published in
Discrete Mathematics

We show how to prove combinatorially the Splitting Necklace Theorem by Alon for any number of thieves. Such a proof requires developing a combinatorial theory for abstract simplotopal complexes and simplotopal maps, which generalizes the theory of abstract simplicial complexes and abstract simplicial maps. Notions like orientation, subdivision, and...

Bacher, Axel Bernini, Antonio Ferrari, Luca Gunby, Benjamin Pinzani, Renzo West, Julian
Published in
Discrete Mathematics

We introduce the notion of pattern in the context of lattice paths, and investigate it in the specific case of Dyck paths. Similarly to the case of permutations, the pattern-containment relation defines a poset structure on the set of all Dyck paths, which we call the Dyck pattern poset. Given a Dyck path P, we determine a formula for the number of...

Amos, David Davila, Randy Pepper, Ryan
Published in
Discrete Mathematics

The k-residue of a graph, introduced by Jelen in a 1999 paper, is a lower bound on the k-independence number for every positive integer k. This generalized earlier work by Favaron, Mahéo, and Saclé, by Griggs and Kleitman, and also by Triesch, who all showed that the independence number of a graph is at least as large as its Havel–Hakimi residue, d...

Mattila, Mika Haukkanen, Pentti
Published in
Discrete Mathematics

In this paper we study the positive definiteness of meet and join matrices using a novel approach. When the set Sn is meet closed, we give a necessary and sufficient condition for the positive definiteness of the matrix (f(Sn)). From this condition we obtain some sufficient conditions for positive definiteness as corollaries. We also use graph theo...

Fitzpatrick, Shannon L.
Published in
Discrete Mathematics

The problem is to determine the number of ‘cops’ needed to capture a ‘robber’ in a game in which the cops always know the location of the robber, and the cops and robber move alternately along edges of a reflexive graph. The cops capture the robber if one of them occupies the same vertex as the robber at any time in the game. A cop-win graph is one...

Hamann, Matthias
Published in
Discrete Mathematics

We call a 2-partite digraph Dhomogeneous if every isomorphism between finite induced subdigraphs that respects the 2-partition of D extends to an automorphism of D that does the same. In this note, we classify the homogeneous 2-partite digraphs.