For some fixed $n_0\ge 0$, we study the minimum number of vertices or edges that have to be removed from a graph such that no component of the rest has more than $n_0$ vertices.

An $[r,s,n,t]$-configuration is a collection $C$ of $r$-sets in $\{1,\dots ,n\}$ such that every $s$-set in $\{1,\dots ,n\}$ contains at most $t$ of the $r$-sets in $C$. Studying this generalization of the Steiner system was suggested by a theorem of Poonen on union-closed families of sets. In this paper, we consider only $[3,4,n,2]$-configurations, and refer to them as $n$-configurations; by an $(n,k)$-configuration we mean an $n$-configuration containing exactly $k$ $3$-sets. An $(n,k)$-configuration is maximal if it is not contained in any $(n,k+1)$-configuration; finally, $L(n)$ is the largest integer $k$ for which an $(n,k)$-configuration exists. In this paper, we determine $L(n)$ for $4\le n\le 9$, and characterize all the maximal $n$-configurations for $n=4,5,$ and $6$, as well as the $(n,L(n))$-configurations for $n=7,8,$ and $9$.

Let $G$ be a simple graph with vertex set $V$ and edge set $E$. A vertex labeling $f:V\to \{0,1,2\}$ induces an edge labeling $\overline{f}:E\to \{0,1,2\}$ defined by $\overline{f}(uv)=|f(u)–f(v)|$. Let $u_f(i)$ denote the number of vertices $v$ with $f(v)=i$, $i=0,1,2$. Similarly, $e_f(i)$ denotes the number of edges $uv$ with $\overline{f}(uv)=i$, $i=0,1,2$. A graph is said to be $3$-equitable if there exists a vertex labeling $f$ such that $|v_f(i)–v_f(j)|\le 1$ and $|e_f(i)–e_f(j)|\le 1$ for all $i\ne j$, $i,j=0,1,2$. In which case, $f$ is called a $3$-equitable labeling.

In this paper, we prove that the following graphs are three equitable: (1) Helm graph $H_n$ ($n\ge 4$), (2) A Flower graph $F{L}_n$, (3) One point union $H_n^{(k)}$ of $k$-copies of $H_n$, $k\ge 1$, (4) One point union $K_4^{(k)}$ of $k$ copies of $K_4$, (5) A $K_4$-snake of $n$ blocks, each equal to $K_4$, (6) A $C_t$-snake of $n$ blocks, $t=4,6$ and $t=5$ with $n$ not congruent to $3$ modulo $6$.

A defensive alliance in a graph $G=(V,E)$ is a set of vertices $S\subseteq V$ satisfying the condition that every vertex $v\in S$ has at most one more neighbor in $V–S$ than it has in $S$. Because of such an alliance, the vertices in $S$, agreeing to mutually support each other, have the strength of numbers to be able to defend themselves from the vertices in $V–S$. In this paper, we introduce this new concept, together with a variety of other kinds of alliances, and initiate the study of their mathematical properties.

The distance-$k$ domination number of graph $G$, ${\gamma }_{\le k}(G)$, is the cardinality of a smallest set of vertices, $S$, such that every vertex not in $S$ is no more than distance $k$ from at least one vertex of $S$. Carrington, Harary, and Haynes showed $|V^0|\ge 2|V^{+}|$ where $V^0=\{u\in V:{\gamma }_{\le 1}(G-v)={\gamma }_{\le 1}(G)\}$ and $V^{+}=\{v\in V:{\gamma }_{\le 1}(G-v)>{\gamma }_{\le 1}(G)\}$. This paper extends the result to distance-$k$ domination, with the obvious change in definition of $V^0$ and $V^{+}$, to show $|V^0|\ge \frac{2}{2k-1}|V^{+}|$. Extremal graphs are characterized when $k=1$ and some progress is mentioned on the characterization problem when $k>1$.

We investigate constraints in finite Boolean lattices $⟨\mathcal{P}(X),\subseteq ⟩$ where $X$ is a finite set. The constraints studied here are of the form $⟨Z,k⟩$ where $Z\subseteq X$, $1\le k\le |Z|$. A set $I\subseteq X$ $satisfies$ $⟨Z,k⟩$ if $|I\cap Z|\ge k$. We characterize the sets satisfying collections of such constraints as filters (final segments) in $⟨\mathcal{P}(X)⟩$. We find yet other characterizations of filters including one by means of families of sets indexed by elements of $X$ so that the elements of the filter correspond to subfamilies with an empty intersection. Our characterizations are supported for algorithms. We also study the families of negated constraints and mixed families and find their characterizations. In the positive case, formulas built of constraints can be used to measure the complexity of filters (and thus also of antichains of their minimal elements). We find pathological filters with very simple descriptions when the disjunctions are allowed, but extremely complex descriptions when only conjunctions are allowed.

The number $g_3^{(4)}(v)$ represents the minimum cardinality of a pairwise balanced design on $v$ elements in which the largest block size is four and every pair occurs exactly three times. We give a survey of the results for this quantity.

Let $G_1$ and $G_2$ be any two 2-regular graphs, each with $n$ vertices. Let $G$ be any cubic graph obtained from $G_1$ and $G_2$ by adding $n$ edges, each of which joins a vertex in $G_1$ to a vertex in $G_2$. We show that $G$ has a myriad of vertex-magic total labelings, with at least three different magic constants. This class of cubic graphs includes all generalized Petersen graphs.

Let $[n,k,d{]}_q$ codes be linear codes of length $n$, dimension $k$, and minimum Hamming distance $d$ over $GF(q)$. In this paper, the existence of the following codes is proven: $[42,6,30{]}_8,[49,6,36{]}_8,[78,6,60{]}_8,[84,6,65{]}_8,[91,6,71{]}_8,[96,6,75{]}_8,[102,6,80{]}_8,[108,6,85{]}_8,[114,6,90{]}_8,$$\text{and}[48,6,35{]}_9,[54,6,40{]}_9,[60,6,45{]}_9,[96,6,75{]}_9,[102,6,81{]}_9,[108,6,85{]}_9,[114,6,90{]}_9,[126,6,100{]}_9,[132,6,105{]}_9.$ The nonexistence of five codes over $GF(9)$ is also proven. All of these results improve the respective upper and lower bounds in Brouwer’s table [2].

In this paper, we obtain some necessary existence conditions for bi-level balanced arrays of strength six by using some classical inequalities and by expressing the moments of the weights of the columns of such arrays in terms of its parameters. We present some illustrative examples to compare these results with the earlier known results.

This paper describes a comprehensive approach to the analysis and synthesis of tree-structured communication networks. First, a class of models for tree-structured communication networks is proposed. Then, performance parameters such as communication delays and network reliability are defined, and efficient algorithms for calculating these parameters are provided. Subsequently, an application of a powerful tree-generating algorithm to the synthesis of optimal communication networks is described. The universal approach of this algorithm allows for its use in conjunction with the proposed model and the algorithms for calculating values of performance parameters. The paper shows sample optimal tree-structured networks resulting from applying the synthesis algorithm for various optimization parameters.

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)\le 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\ge 0$ and $n\ge 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\ge 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\le g^{(4)}(18)\le 33.$In this note, we show that $31\le 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\le n\le 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.