Let G = (V, E) be a graph and k a positive integer such that k ≤ | V | . The k -token graph of G is the graph F k (G) having the set of all k -sets of V as vertex set, and such that two k -sets of V , say A and B , are adjacent if and only if the symmetric difference of A and B is an edge of G. In this work we study the cop number of token graphs of graphs in some classic families, such as paths, stars, and subdivided stars. We obtain the exact cop number for k -token graphs of paths and stars. We also obtain the exact cop number for subdivided stars when the number of branches is large enough. Probably more interesting than the aforementioned results, we introduce a variant of the Cops and Robbers game where R controls a team of robbers and C controls some teams of cops. A game of Cops and Robbers with this new variant played on a graph G is equivalent to a classic game of Cops and Robbers played on F k (G). This turns out to be very useful, as F k (G) is usually very large and complex when compared to G .

Abstract In the context of the Firefighter problem, a deterministic model of the spread of a fire or virus on a graph, SFIRE is the decision problem that asks if a specified set of vertices can be prevented from burning. We show SFIRE remains NP‐complete even when restricted to graphs with maximum degree 3 even when the fire starts at a vertex of degree 2.

Let H be a graph and $k \geq 3$. A near-unanimity function of arity k is a mapping g from the k-tuples over $V(H)$ to $V(H)$ such that $g(x_1, x_2, \dots, x_k)$ is adjacent to $g(x'_1, x'_2, \dots, x'_k)$ whenever $x_i x'_i \in E(H)$ for each $i = 1, 2, \dots, k$, and $g(x_1, x_2, \dots, x_k) = a$ whenever at least $k-1$ of the $x_i$'s equal a. Feder and Vardi proved that, if a graph H admits a near-unanimity function, then the homomorphism extension (or retraction) problem for H is polynomial time solvable. We focus on near-unanimity functions on reflexive graphs. The best understood are reflexive chordal graphs H: they always admit a near-unanimity function. We bound the arity of these functions in several ways related to the size of the largest clique and the leafage of H, and we show that these bounds are tight. In particular, it will follow that the arity is bounded by $n -\sqrt{n}+1$, where $n = |V(H)|$. We investigate substructures forbidden for reflexive graphs that admit a near-unanimity function. It will follow, for instance, that no reflexive cycle of length at least four admits a near-unanimity function of any arity. However, we exhibit nonchordal graphs which do admit near-unanimity functions. Finally, we characterize graphs which admit a conservative near-unanimity function. This characterization has been predicted by the results of Feder, Hell, and Huang. Specifically, those results imply that, if P $\neq$ NP, the graphs with conservative near-unanimity functions are precisely the so-called bi-arc graphs. We give a proof of this statement without assuming P $\neq$ NP.

Abstract A graph G is vertex domination‐critical if for any vertex v of G the domination number of G ‐ v is less than the domination number of G. If such a graph G has domination number γ, it is called γ‐critical. Brigham et al. studied γ‐critical graphs and posed the following questions: (1) If G is a γ‐critical graph, is |V| ≥ (δ + 1)(γ ‐ 1) + 1?(2) If a γ‐critical graph G has (Δ + 1)(γ ‐ 1) + 1 vertices, is G regular? (3) Does i = γ for all γ‐critical graphs? (4) Let d be the diameter of the γ‐critical graph G. Does d ≤ 2(γ ‐ 1) always hold? We show that the first and third questions have a negative answer and the others have a positive answer.

Let H be a fixed directed graph whose vertices are called colours. An H-colouring of a digraph G is an assignment of these colours to the vertices of G such that if x is adjacent to y in G, then colour$( x )$ is adjacent to colour$( y )$ in H (i.e., a homomorphism$G \to H$). In this paper the complexity of the H-colouring problem, when the directed graph H is vertex-transitive or arc-transitive, is investigated. In both instances a complete classification is obtained.

The following problem, known as the H-colouring problem, is studied. An H-colouring of a directed graph D is a mapping $f:V( D ) \to V( H )$ such that $( f( x ),f( y ) )$ is an edge of H whenever $( x,y )$ is an edge of D. The H-colouring problem is the following. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In this paper it is shown that for semicomplete digraphs T the T-colouring problem is NP-complete when T has more than one directed cycle, and polynomially decidable otherwise.