The induced path number \( \rho(G) \) of a graph \( G \) is defined as the minimum number of subsets into which the vertex set of \( G \) can be partitioned so that each subset induces a path. A Nordhaus-Gaddum type result is a (tight) lower or upper bound on the sum (or product) of a parameter of a graph and its complement. If \( G \) is a subgraph of \( H \), then the graph \( H – E(G) \) is the complement of \( G \) relative to \( H \). In this paper, we consider Nordhaus-Gaddum type results for the parameter \( \rho \) when the relative complement is taken with respect to the complete bipartite graph \( K_{m,n} \).

Rado constructed a (simple) denumerable graph \( R \) with the positive integers as vertex set with the following edges: For given \( m \) and \( n \) with \( m < n \), \( m \) is adjacent to \( n \) if \( n \) has a \( 1 \) in the \( m \)'th position of its binary expansion. It is well known that \( R \) is a universal graph in the set \( \mathcal{I} \) of all countable graphs (since every graph in \( \mathcal{I} \) is isomorphic to an induced subgraph of \( R \)) and that \( R \) can be characterized using this notion and that of being homogeneous and having the extension property. In this paper, we extend these notions to arbitrary induced-hereditary properties (of graphs), relate them to the construction of a universal graph for any such property, and obtain results which remind one of some characterizations of \( R \).

In this note, we prove that for any tree \( T \), \( \gamma_{\leq2}(T) \leq \gamma_\gamma(T) \leq ir(T) \leq \gamma(T) \), where \( \gamma_{\leq2}(G) \) is the distance-2 domination number, \( ir(T) \) is the (lower) irredundance number, \( \gamma(T) \) is the domination number, and \( \gamma_\gamma(T) \), newly defined here, equals the minimum cardinality of a set of vertices that dominates a minimum dominating set of \( T \).

A graph is \((k, l)\)-colorable if its vertex set can be partitioned into \( k \) independent sets and \( l \) cliques. A graph is chordal if it does not contain any induced cycle of length at least four. A theorem by Hell et al. states that a chordal graph is \((k, l)\)-colorable if and only if it does not contain \((l+1)K_{k+1}\) as an induced subgraph. Presented here is a short alternative proof of this result, using the characterization of chordal graphs via perfect elimination orderings.

A subset \( X \) of the vertex set of a graph \( G \) is a secure dominating set of \( G \) if \( X \) is a dominating set of \( G \) and if, for each vertex \( u \) not in \( X \), there is a neighboring vertex \( v \) of \( u \) in \( X \) such that the swap set \( (X – \{v\}) \cup \{u\} \) is again a dominating set of \( G \). The secure domination number of \( G \), denoted by \( \gamma_s(G) \), is the cardinality of a smallest secure dominating set of \( G \). In this paper, we present two algorithms (a branch-and-reduce algorithm as well as a branch-and-bound algorithm) for determining the secure domination number of a general graph \( G \) of order \( n \). The worst-case time complexities of both algorithms are \( \mathcal{O}(2^{n-s-\sum_{i=1}^{k}(|\mathcal{R}_i|-1)}) \), where \( s \) is the number of support vertices in \( G \) and \( \mathcal{R}_i, \ldots, \mathcal{R}_k \) are the redundancy classes of \( G \) (two vertices are in the same redundancy class if they are adjacent and share the same closed neighborhood which forms a clique in \( G \)).

The distinguishing chromatic number of a graph \( G \) is the least integer, \( \chi_D(G) \), for which \( G \) has a coloring of its vertices so that adjacent vertices receive different colors, and the identity is the only automorphism of \( G \) that preserves vertex colors. Our focus is on determining the distinguishing chromatic numbers of wreath products of graphs, extending the work of Tang. We prove that if \( C_n \) is a cycle with \( n \) vertices and \( P_n \) is a path with \( n \) vertices, then \( \chi_D(C_n[G]) \) and \( \chi_D(P_n[G]) \) can be found for any connected graph \( G \). We also obtain an upper bound on \( \chi_D(T[G]) \) when \( T \) is a tree and \( G \) is any connected graph. Some of our results depend on the notion of inequivalent colorings. Cheng introduces inequivalent colorings and provides a formula for computing the number of inequivalent distinguishing \( k \)-colorings of a rooted tree. We add to this work by obtaining an expression for computing the number of inequivalent distinguishing \( k \)-colorings of a cycle.

A graph \( G \) is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a quadrilateral is called a (planar) quadrangulation. In the present paper, we characterize those planar quadrangulations which are well-covered.

Suppose \( V \) is a finite set and \( \mathcal{C} \) a collection of subsets of \( V \) that contains \( \emptyset \) and \( V \) and is closed under taking intersections. Then the ordered pair \( (V, \mathcal{C}) \) is called a \({convexity}\) and the elements of \( \mathcal{C} \) are referred to as \({convex\; sets}\). For a set \( S \subseteq V \), the \({convex\; hull}\) of \( S \) relative to \( \mathcal{C} \), denoted by \( CH_{\mathcal{C}}(S) \), is the smallest convex set containing \( S \). The \({Carathéodory\; number}\), relative to a given convexity, is the smallest integer \( c \) such that for any subset \( S \) of \( V \) and any point \( v \in CH_{\mathcal{C}}(S) \), there is a subset \( F \) of \( S \) with \( |F| \leq c \) such that \( v \in CH_{\mathcal{C}}(F) \). A subset \( X \) of \( V \) is said to admit a \({Radon \;partition}\) if \( X \) can be partitioned into two sets \( X_1 \) and \( X_2 \) such that \( CH_{\mathcal{C}}(X_1) \cap CH_{\mathcal{C}}(X_2) \neq \emptyset \). The \({Radon\; number}\) of a convexity is the smallest integer \( r \) (if it exists) such that every subset \( X \) of \( V \) with at least \( r \) elements admits a Radon partition.

A set \( S \) of vertices in a graph \( G \) with vertex set \( V \) is \({digitally}\) convex if for every vertex \( v \in V \), \( N[v] \subseteq N[S] \) implies \( v \in S \). A set \( X \) is \({irredundant}\) if \( N[X] – N[X – \{x\}] \neq \emptyset \) for all \( x \in X \). The maximum cardinality of an irredundant set is the \({upper\; irredundance\; number}\) of \( G \), denoted by \( IR(G) \). A set \( X \) of vertices in a graph \( G \) is a \({local\; irredundant}\) set for a vertex \( v \) of \( G \), if for each \( x \in X \), \( x \in N[v] – N[X – \{x\}] \) or \( x \) is adjacent to a vertex of \( N[v] – N[X – \{x\}] \). The \({upper\; local \;irredundance \;number}\) of \( v \), denoted by \( l_{IR}(v) \), is the maximum cardinality of a local irredundant set for \( v \). The \({upper\; local\; irredundance\; number}\) of a graph \( G \), denoted by \( l_{IR}(G) \), is defined as \( l_{IR}(G) = \max \{ l_{IR}(v) \mid v \in V \} \).

We show that for the digital convexity of a graph \( G \):
(i) The Carathéodory number equals \( l_{IR}(G) \).
(ii) The Radon number is bounded above by \( IR(G) + 1 \) and below by \( \beta(G) + 1 \) where \( \beta(G) \) is the independence number of \( G \). For the latter result, it is shown that there are classes of graphs for which the lower (respectively, upper) bound is attained, while the difference between the upper irredundance number and the independence number can be made as large as we wish. Moreover, there are graphs for which the Radon number of the digital convexity lies strictly between the bounds given in (ii) and does not equal one more than the upper domination number.

In this work, we study the structure of the null spaces of matrices associated with graphs. Our primary tool is utilizing Schur complements based on certain collections of independent vertices. This idea is applied in the case of trees, and seems to represent a unifying theory within the context of the support of the null space. We extend this idea and apply it to describe the null vectors and corresponding nullities of certain symmetric matrices associated with cycles.

A set of vertices in a graph \( G \) is a global dominating set of \( G \) if it dominates both \( G \) and its complement \( \overline{G} \). The minimum cardinality of a global dominating set of \( G \) is the global domination number of \( G \). We explore the effects of graph modifications (edge removal, vertex removal, and edge addition) on the global domination number. In particular, for each graph modification, we study the global domination stable trees, that is, the trees whose global domination number remains the same upon the modification. We characterize these stable trees having small global domination numbers.

A digraph is called \({homogeneous}\) if every connected induced sub-digraph with two or more vertices is either strong or acyclic. The class of homogeneous digraphs contains acyclic digraphs, round digraphs, and symmetric digraphs. Tournaments which are homogeneous have been studied by Guido, Moon, and others, and characterized by Moon. In this paper, we give a characterization of homogeneous digraphs. Our characterization reveals a nice structural property of this class of digraphs and shows that all homogeneous digraphs can be obtained from acyclic digraphs, round digraphs, and symmetric digraphs by the operation of substitution.

We analyze TIMBER, a game played on graphs. We find the \(\mathcal{P}\) positions for both normal and misère play on paths and show how to win the game. In passing, we also show a correspondence with Dyck paths, the Catalan, and Fine numbers. We present an algorithm for winning the Normal Play game on trees.

An edge ordering of a graph \( G \) is an injection \( f : E(G) \to \mathbb{Z} \), where \( \mathbb{Z} \) denotes the set of integers. A path in \( G \) for which the edge ordering \( f \) increases along its edge sequence is called an \( f \)-\({ascent}\); an \( f \)-ascent is maximal if it is not contained in a longer \( f \)-ascent. The \({depression}\) of \( G \) is the smallest integer \( k \) such that any edge ordering \( f \) has a maximal \( f \)-ascent of length at most \( k \). We apply the concept of ascents to edge colorings using possibly less than \( |E(G)| \) colors and consider the problem of determining the minimum number of colors required such that there exists an edge coloring \( c \) for which the length of a shortest maximal \( c \)-ascent is equal to the depression of \( G \).

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

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