A graph \( G \) is said to be 2-distinguishable if there is a labeling of the vertices with two labels so that only the trivial automorphism preserves the labels. The minimum size of a label class in such a labeling of \( G \) is called the cost of 2-distinguishing and is denoted by \( \rho(G) \). This paper shows that \( \rho(K_{2^m-1}:2^{m-1}-1) = m+1 \) — the only result so far on the cost of 2-distinguishing Kneser graphs. The result for Kneser graphs is adapted to show that \( \rho(Q_{2^m-2}) = \rho(Q_{2^m-1}) = \rho(Q_{2^m}) = m+2 \) — a significant improvement on previously known bounds for the cost of 2-distinguishing hypercubes.

We explore cops-and-robbers games in several directions, giving partial results in each and refuting two reasonable conjectures. We close with some open problems.

Given a set \( S \subseteq V \) in a graph \( G = (V, E) \), we say that a vertex \( v \in V \) is perfect if \( |N[v] \cap S| = 1 \), that is, the closed neighborhood \( N[v] = \{v\} \cup \{u \mid uv \in E\} \) of \( v \) contains exactly one vertex in \( S \). A vertex \( v \) is almost perfect if it is either perfect or is adjacent to a perfect vertex. Similarly, we can say that a set \( S \subset V \) is (almost) perfect if every vertex \( v \in S \) is (almost) perfect; \( S \) is externally (almost) perfect if every vertex \( u \in V – S \) is (almost) perfect; and \( S \) is completely (almost) perfect if every vertex \( v \in V \) is (almost) perfect. In this paper, we relate these concepts of perfection to independent sets, dominating sets, efficient and perfect dominating sets, distance-2 dominating sets, and to perfect neighborhood sets in graphs. The concept of a set being almost perfect also provides an equivalent definition of irredundance in graphs.

A graph \( G \) is \( k \)-edge-\( i \)-critical if it has independent domination number \( i(G) = k \), and \( i(G + xy) < i(G) \) whenever \( xy \notin E(G) \). The following results are obtained for \( 3 \)-edge-\( i \)-critical graphs \( G \):

1. If \( \delta \geq 3 \), then \( G \) is hamiltonian.
2. If \( \delta = 2 \), then there is exactly one family of non-hamiltonian graphs.
3. If \( |V(G)| > 6 \), then \( G \) has a Hamilton path.

The proofs of these results rely on a closure operation, a characterization of the \( 2 \)-connected, \( 3 \)-edge-\( i \)-critical graphs with \( \delta = 2 \), and a characterization of the \( 3 \)-edge-\( i \)-critical graphs with a cut vertex.

An identifying code in a graph \( G \) is a set \( D \) of vertices such that the closed neighborhood of each vertex of the graph has a nonempty, distinct intersection with \( D \). The minimum cardinality of an identifying code is denoted \( \gamma^{ID}(G) \). Building upon recent results of Gravier, Moncel, and Semri, we show for \( n \leq m \) that \( \gamma^{ID} (K_n \Box K_m) = \max\{2m – n, m + \lfloor n/2 \rfloor\} \). Furthermore, we improve upon the bounds for \( \gamma^{ID}(G \Box K_m) \) and explore the specific case when \( G \) is the Cartesian product of multiple cliques.

Mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on its vertices. The locations of the guards must induce a vertex cover at all times. We compare this new model of graph protection with other previously studied parameters, including such as the eternal domination number and the variation of the eternal vertex cover problem in which attacks occur at edges

Suppose each vertex in a graph \( G \) has a unit of information and that all the units must be collected at a vertex \( u \) in \( G \). Assuming that a vertex can receive (from its neighbors) an unlimited number of units at each discrete moment but can only send one at a time, find the shortest collection time, \( \operatorname{col}_u(G) \), needed to collect all the information at \( u \) and an optimal protocol that achieves this.

We derive lower and upper bounds for the problem, give a polynomial time algorithm in the general case, and a linear time algorithm for hypercubes.

A (di)graph \( G \) is \({homomorphically; full}\) if every homomorphic image of \( G \) is a sub(di)graph of \( G \). This class of (di)graphs arose in the study of whether a homomorphism from a given graph \( G \) to a fixed graph \( H \) can be factored through a fixed graph \( Y \). Brewster and MacGillivray proved that the homomorphically full irreflexive graphs are precisely the graphs that contain neither \( P_4 \) nor \( 2K_2 \) as an induced subgraph. In this paper, we show that the homomorphically full reflexive graphs are precisely threshold graphs, i.e., the graphs that contain none of \( P_4 \), \( 2K_2 \), and \( C_4 \) as an induced subgraph. We also characterize the reflexive semicomplete digraphs that are homomorphically full, and discuss the relationship of these digraphs and Ferrers digraphs.

The eternal domination number of graph \( G \) is the smallest set of mobile guards which can defend \( G \) against an infinite sequence of attacks on its vertices. In this paper we give results for the eternal domination numbers of \( P_4 \Box P_n \).

A red-blue coloring of a graph \( G \) is an edge coloring of \( G \) in which every edge of \( G \) is colored red or blue. Let \( F \) be a connected graph of size 2 or more with a red-blue coloring, at least one edge of each color, where some blue edge of \( F \) is designated as the root of \( F \). Such an edge-colored graph \( F \) is called a color frame. An \( F \)-coloring of a graph \( G \) is a red-blue coloring of \( G \) in which every blue edge of \( G \) is the root edge of a copy of \( F \) in \( G \). The \( F \)-chromatic index \( \chi’_F(G) \) of \( G \) is the minimum number of red edges in an \( F \)-coloring of \( G \). It has been shown that these concepts generalize both edge domination and matchings in graphs. In this paper, we consider the two color frames \( Y_1 \) and \( Y_2 \) that result from the claw \( K_{1,3} \), where \( Y_1 \) has exactly one red edge and \( Y_2 \) has exactly two red edges. An edge \( e \) in a graph \( G \) is a non-claw edge if \( e \) belongs to no claw in \( G \). It is shown that if \( G \) is a connected graph containing \( \ell \) non-claw edges, then \( \chi’_{Y_1}(G) \leq \chi’_{Y_2}(G) \leq 3\chi’_{Y_1}(G) – 2\ell \) and \( \chi’_{Y_1}(G) = \chi’_{Y_2}(G) \) if and only if \( G \) is a path or cycle. Furthermore, a pair \( a, b \) of positive integers can be realized as the \( Y_1 \)-chromatic index and \( Y_2 \)-chromatic index for some connected graph of order at least 4 if and only if \( a \leq b \leq 3a \) and \( b \geq 2 \).