Source author record

P. Mark Kayll

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Egerváry graphs: Deming decompositions and independence structure

We leverage an algorithm of Deming [R.W. Deming, Independence numbers of graphs -- an extension of the Koenig-Egervary theorem, Discrete Math., 27(1979), no. 1, 23--33; MR534950] to decompose a matchable graph into subgraphs with a precise structure: they are either spanning even subdivisions of blossom pairs, spanning even subdivisions of the complete graph $K_4$ , or a Kőnig-Egerváry graph. In each case, the subgraphs have perfect matchings; in the first two cases, their independence numbers are one less than their matching numbers, while the independence number of the KE subgraph equals its matching number. This decomposition refines previous results about the independence structure of an arbitrary graph and leads to new results about $α$ -critical graphs.

preprint2021arXiv

On random digraphs and cores

An acyclic homomorphism of a digraph $C$ to a digraph $D$ is a function $ρ\colon V(C)\to V(D)$ such that for every arc $uv$ of $C$ , either $ρ(u)=ρ(v)$ , or $ρ(u)ρ(v)$ is an arc of $D$ and for every vertex $v\in V(D)$ , the subdigraph of $C$ induced by $ρ^{-1}(v)$ is acyclic. A digraph $D$ is a core if the only acyclic homomorphisms of $D$ to itself are automorphisms. In this paper, we prove that for certain choices of $p(n)$ , random digraphs $D\in D(n,p(n))$ are asymptotically almost surely cores. For digraphs, this mirrors a result from [A. Bonato and P. Prałat, The good, the bad, and the great: homomorphisms and cores of random graphs, Discrete Math., 309 (2009), no. 18, 5535-5539; MR2567955] concerning random graphs and cores.

preprint2021arXiv

Uniquely $D$ -colourable digraphs with large girth II: simplification via generalization

We prove that for every digraph $D$ and every choice of positive integers $k$ , $\ell$ there exists a digraph $D^*$ with girth at least $\ell$ together with a surjective acyclic homomorphism $ψ\colon D^*\to D$ such that: (i) for every digraph $C$ of order at most $k$ , there exists an acyclic homomorphism $D^*\to C$ if and only if there exists an acyclic homomorphism $D\to C$ ; and (ii) for every $D$ -pointed digraph $C$ of order at most $k$ and every acyclic homomorphism $φ\colon D^*\to C$ there exists a unique acyclic homomorphism $f\colon D\to C$ such that $φ=f\circψ$ . This implies the main results in [A. Harutyunyan et al., Uniquely $D$ -colourable digraphs with large girth, Canad. J. Math., 64(6) (2012), 1310-1328; MR2994666] analogously with how the work [J. Nešetřil and X. Zhu, On sparse graphs with given colorings and homomorphisms, J. Combin. Theory Ser. B, 90(1) (2004), 161-172; MR2041324] generalizes and extends [X. Zhu, Uniquely $H$ -colorable graphs with large girth, J. Graph Theory, 23(1) (1996), 33-41; MR1402136].

preprint2020arXiv

On lengths of burn-off chip-firing games

We continue our studies of burn-off chip-firing games from [Discrete Math. Theor. Comput. Sci. 15 (2013), no. 1, 121-132; MR3040546] and [Australas. J. Combin. 68 (2017), no. 3, 330-345; MR3656659]. The latter article introduced randomness by choosing successive seeds uniformly from the vertex set of a graph $G$ . The length of a game is the number of vertices that fire (by sending a chip to each neighbor and annihilating one chip) as an excited chip configuration passes to a relaxed state. This article determines the probability distribution of the game length in a long sequence of burn-off games. Our main results give exact counts for the number of pairs $(C,v)$ , with $C$ a relaxed legal configuration and $v$ a seed, corresponding to each possible length. In support, we give our own proof of the well-known equicardinality of the set $\mathcal{R}$ of relaxed legal configurations on $G$ and the set of spanning trees in the cone $G^*$ of $G$ . We present an algorithmic, bijective proof of this correspondence.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

P. Mark Kayll

Research overview

Is this your work?

4 publications

Egerváry graphs: Deming decompositions and independence structure

On random digraphs and cores

Uniquely $D$ -colourable digraphs with large girth II: simplification via generalization

On lengths of burn-off chip-firing games

See the researcher in context

Building this map preview

P. Mark Kayll

Research overview

Is this your work?

4 publications

Egerváry graphs: Deming decompositions and independence structure

On random digraphs and cores

Uniquely DDD-colourable digraphs with large girth II: simplification via generalization

On lengths of burn-off chip-firing games

See the researcher in context

Building this map preview

Uniquely $D$ -colourable digraphs with large girth II: simplification via generalization