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.