A vertex \( v \) of a connected graph \( G \) is an eccentric vertex of a vertex \( u \) if \( v \) is a vertex at greatest distance from \( u \); while \( v \) is an eccentric vertex of \( G \) if \( v \) is an eccentric vertex of some vertex of \( G \). The subgraph of \( G \) induced by its eccentric vertices is the eccentric subgraph of \( G \).

A vertex \( v \) of \( G \) is a boundary vertex of a vertex \( u \) if \( d(u,w) \leq d(u,v) \) for each neighbor \( w \) of \( v \). A vertex \( v \) is a boundary vertex of \( G \) if \( v \) is a boundary vertex of some vertex of \( G \). The subgraph of \( G \) induced by its boundary vertices is the boundary of \( G \). A vertex \( v \) is an interior vertex of \( G \) if for every vertex \( u \) distinct from \( v \), there exists a vertex \( w \) distinct from \( v \) such that \( d(u,w) = d(u,v) + d(v,w) \). The interior of \( G \) is the subgraph of \( G \) induced by its interior vertices. A vertex \( v \) is a boundary vertex of a connected graph if and only if \( v \) is not an interior vertex. For every graph \( G \), there exists a connected graph \( H \) such that \( G \) is both the center and interior of \( H \).

Relationships between the boundary and the periphery, center, and eccentric subgraph of a graph are studied. The boundary degree of a vertex \( v \) in a connected graph \( G \) is the number of vertices \( u \) in \( G \) having \( v \) as a boundary vertex. We study, for each pair \( r,n \) of integers with \( r \geq 0 \) and \( n \geq 3 \), the existence of a connected graph \( G \) of order \( n \) such that every vertex of \( G \) has boundary degree \( r \). We also study the boundary vertices of a connected graph from different points of view.

Let \( G \) be a simple graph having a maximum matching \( M \). The deficiency \( \text{def}(G) \) of \( G \) is the number of vertices unsaturated by \( M \). A bridge in a connected graph \( G \) is an edge \( e \) of \( G \) such that \( G-e \) is disconnected. A graph is said to be almost cubic (or almost 3-regular) if one of its vertices has degree \( 3 + e \), \( e \geq 0 \), and the others have degree 3. In this paper, we find the minimum number of bridges of connected almost cubic graphs with a given deficiency.

The cardinality of the minimal pairwise balanced designs on \( v \) elements with largest block size \( k \) is denoted by \( g^{(k)}(v) \). It is known that \(30 \leq g^{(4)}(18) \leq 33.\)In this note, we show that \(31 \leq g^{(4)}(18).\)

In this paper, we introduce two new classes of critical sets, \( t \)-uniform and \( T \)-uniform (where \( t \) is a positive integer and \( T \) is a partial Latin square). We identify, up to isomorphism, all \( t \)-uniform critical sets of order \( n \), where \( 2 \leq n \leq 6 \). We show that the completable product of two \( T \)-uniform critical sets is a \( T \)-uniform critical set for certain partial Latin squares \( T \), and then apply this theorem to small examples to generate infinite families of \( T \)-uniform critical sets.

In the paper [3], the theorem that at least \( \frac{n – 1}{2} \) queens are required to dominate the \( n \times n \) chessboard was attributed to P. H. Spencer, in [1]. A proof of this result appeared in the earlier work [2].

A set \( D \) of vertices in a graph \( G \) is irredundant if every vertex \( v \) in \( D \) has at least one private neighbour in \( N[v, G] \setminus N[D \setminus \{v\}, G] \). A set \( D \) of vertices in a graph \( G \) is a minimal dominating set of \( G \) if \( D \) is irredundant and every vertex in \( V(G) \setminus D \) has at least one neighbour in \( D \). Further, irredundant sets and minimal dominating sets of maximal cardinality are called \( IR \)-sets and \( \Gamma \)-sets, respectively. A set \( I \) of the vertex set of a graph \( G \) is independent if no two vertices in \( I \) are adjacent, and independent sets of maximal cardinality are called \( \alpha \)-sets.

In this paper, we prove that bipartite graphs and chordal graphs have a unique \( \alpha \)-set if and only if they have a unique \( \Gamma \)-set if and only if they have a unique \( IR \)-set. Some related results are also presented.

Static mastermind is like normal mastermind, except that the codebreaker must supply at one go a list of questions (candidate codes), the answers to which must uniquely determine the secret code. We confirm the minimum size list for some small values. Then we solve the game for up to 4 positions. In particular, we show that for \( k \) sufficiently large, the minimum size of a list for 4 positions and \( k \) colours is \( k – 1 \).

It is shown that for \( n \geq 16 \), the sum of cardinalities of open irredundant sets in an \( n \)-vertex graph and its complement is at most \( \frac{3n}{4} \).

The redundance \( R(G) \) of a graph \( G \) is the minimum, over all dominating sets \( S \), of \( \sum_{v \in S} (1 + \deg(v)) \), where \( \deg(v) \) is the degree of vertex \( v \). We use some dynamic programming algorithms to compute the redundance of complete grid graphs \( G_{m,n} \) for \( 1 \leq m \leq 21 \) and all \( n \), and to establish good upper and lower bounds on the redundance for larger \( m \). We conjecture that the upper bound is the redundance when \( m > 21 \).

Heinrich et al. [4] characterized those simple eulerian graphs with no Petersen-minor which admit a triangle-free cycle decomposition, a TFCD. If one permits Petersen minors then no such characterization is known even for \( {E}(4,2) \), the set of all the eulerian graphs of maximum degree 4. Let \( {EM}(4,2) \subset {E}(4,2) \) be the set of all graphs \( H \) such that all triangles of \( H \) are vertex disjoint, and each triangle contains a degree 2 vertex in \( H \). In the paper it is shown that to each \( G \in {E}(4,2) \) there exists a finite subset \( S \subset {EM}(4,2) \) so that \( G \) admits a TFCD if and only if some \( H \in S \) admits a TFCD. Further, some sufficient conditions for a graph \( G \in {E}(4,2) \) to possess a TFCD are given.