An independent set of a graph \( G \) is a set of vertices of \( G \) which are pairwise non-adjacent. There are many applications for which the input is a graph \( G \) with a large symmetry group and the goal is to generate up to isomorphism all of the independent sets, all of the maximal independent sets, or all of the maximum independent sets. This paper presents a very fast practical algorithm for these problems. The tactic can also be applied to many other problems: some examples are generation of all dominating sets, colorings, or matchings of a graph up to isomorphism.

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 \).