Source author record

Nancy E. Clarke

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

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Complexity of injective homomorphisms to small tournaments, and of injective oriented colourings

Several possible definitions of local injectivity for a homomorphism of an oriented graph $G$ to an oriented graph $H$ are considered. In each case, we determine the complexity of deciding whether there exists such a homomorphism when $G$ is given and $H$ is a fixed tournament on three or fewer vertices. Each possible definition leads to a locally-injective oriented colouring problem. A dichotomy theorem is proved in each case.

preprint2022arXiv

Hamilton Paths in Dominating Graphs of Trees and Cycles

The dominating graph of a graph $H$ has as its vertices all dominating sets of $H$ , with an edge between two dominating sets if one can be obtained from the other by the addition or deletion of a single vertex of $H$ . In this paper we prove that the dominating graph of any tree has a Hamilton path. We also show how a result about binary strings leads to a proof that the dominating graph of a cycle on $n$ vertices has a Hamilton path if and only if $n\not\equiv 0 \pmod 4$ .

preprint2022arXiv

Obstructions to some injective oriented colourings

Each of several possible definitions of local injectivity for a homomorphism of an oriented graph $G$ to an oriented graph $H$ leads to an injective oriented colouring problem. For each case in which such a problem is solvable in polynomial time, we identify a set $\mathcal{F}$ of oriented graphs such that an oriented graph $G$ has an injective oriented colouring with the given number of colours if and only if there is no $F \in \mathcal{F}$ for which there is a locally-injective homomorphism of $F$ to $G$ .

preprint2011arXiv

A note on the Cops & Robber game on graphs embedded in non-orientable surfaces

The Cops and Robber game is played on undirected finite graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges. The cops win if they can catch the robber. The minimum number of cops needed to win on a graph is called its cop number. It is known that the cop number of a graph embedded on a surface $X$ of genus $g$ is at most $3g/2 + 3$ , if $X$ is orientable (Schroeder 2004), and at most $2g+1$ , otherwise (Nowakowski & Schroeder 1997). We improve the bounds for non-orientable surfaces by reduction to the orientable case using covering spaces. As corollaries, using Schroeder's results, we obtain the following: the maximum cop number of graphs embeddable in the projective plane is 3; the cop number of graphs embeddable in the Klein Bottle is at most 4, and an upper bound is $3g/2 + 3/2$ for all other $g$ .

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.

Nancy E. Clarke

Research overview

Is this your work?

4 publications

Complexity of injective homomorphisms to small tournaments, and of injective oriented colourings

Hamilton Paths in Dominating Graphs of Trees and Cycles

Obstructions to some injective oriented colourings

A note on the Cops & Robber game on graphs embedded in non-orientable surfaces

See the researcher in context

Building this map preview