In this paper, we introduce the concept of node expansion. Node expansion is a generalization of edge subdivision and an inverse of subgraph contraction. A graph $G_1=(V_1,E_1)$ is an $H$-node expansion of $G=(V,E)$ if and only if $G_1$ contains a subgraph $H=(V_H,E_H)$ such that $V=V_1–V_H\cup \{v\}$ and $E=E_1–E_H\cup \{vw|wh\in E_1\text{and}h\in V_H\}\cup \{v\}$. The concept of node expansion is of considerable importance in modernization of networks.

We consider the node expansion problem of transforming a graph to a bipartite graph with a minimum number of node expansions using $K_2$. We show that the $K_2$-node expansion problem is NP-Complete for general graphs and remains so if the input graph has maximum degree 3. However, we present a $O(n^2\log n+mn+p^3)$ algorithm for the case when the input graph is restricted to be planar $3$-connected and output graph is required to be planar bipartite.

An algorithm is presented for finding all $(0,1)$-solutions to the matrix problem $AX=J$, where $A$ is a $(0,1)$-matrix and $J$ is the all $1$’s column vector. It is applied to the problem of enumerating distinct cyclic Steiner systems and five new values are obtained. Specifically, the number of distinct solutions to $S(2,3,55),S(2,3,57),S(2,3,61),S(2,3,63)$, and $S(3,4,22)$ are $121,098,240,84,672,512,2,542,203,904,1,782,918,144$, and $1140$, respectively.

Let $g_k(n)=\sum _{\underset{\_}{v}\in C_k(n)}(\genfrac{}{}{0ex}{}{n}{v})2^{v_1{v}_2+v_2{v}_3+v_3{v}_4+\dots +v_{k-1}{v}_k}$ where $C_k(n)$ denote the set of $k$-compositions of $n$. We show that

1. $g_k(n+p-1)\equiv g_k(n)(\mathrm{mod}p)$ for all $k,n\ge 1$, prime $p$;
2. $g_k(n)$ is a polynomial in $k$ of degree $n$ for $k\ge n+1$;

and, moreover, that these properties hold for wider classes of functions which are sums involving multinomial coefficients.

A connected graph $G$ is unicentered if $G$ has exactly one central vertex. It is proved that for integers $r$ and $d$ with $1\le r<d\le 2r$, there exists a unicentered graph $G$ such that rad$(G)=r$ and diam$(G)=d$. Also, it is shown that for any two graphs $F$ and $G$ with rad$(F)=n\ge 4$ and a positive integer $d$ ($4\le d\le n$), there exists a connected graph $H$ with diam$(H)=d$ such that the periphery and the center of $H$ are isomorphic to $F$ and $G$, respectively.

In this paper we obtain some inequalities on the existence of balanced arrays ($B$-arrays) of strength four in terms of its parameter by using Minkowski’s inequality.

Let $q$ be a prime power, $F_{q^2}$ the finite field with $q^2$ elements, $U_n(F_{q^2})$ the finite unitary group of degree $n$ over $F_{q^2}$, and $U{V}_n(F_{q^2})$ the $n$-dimensional unitary geometry over $F_{q^2}$. It is proven that the subgroup consisting of the elements of $U_n(F_{q^2})$ which fix a given $(m,s)$-type subspace of $U{V}_n(F_{q^2})$, acts transitively on some subsets of subspaces of $U{V}_n(F_{q^2})$. This observation gives rise to a number of Partially Balanced Incomplete Block Designs (PBIBD’s).

There are two criteria for optimality of weighing designs. One, which has been widely studied, is that the determinant of $X{X}^T$ should be maximal, where $X$ is the weighing matrix. The other is that the trace of $(X{X}^T{)}^{-1}$ should be minimal. We examine the second criterion. It is shown that Hadamard matrices, when they exist, are optimal with regard to the second criterion, just as they are for the first one.

In 1988, Sarvate and Seberry introduced a new method of construction for the family of weighing matrices $W(n^2(n-1),n^2)$, where $n$ is a prime power. We generalize this result, replacing the condition on $n$ with the weaker assumption that a generalized Hadamard matrix $GH(n;G)$ exists with $|G|=n$, and give conditions under which an analogous construction works for $|G|<n$. We generalize a related construction for a $W(13,9)$, also given by Sarvate and Seberry, producing a whole new class. We build further on these ideas to construct several other classes of weighing matrices.

For an integer $\ell \ge 2$, the $\ell$-connectivity ($\ell$-edge-connectivity) of a graph $G$ of order $p$ is the minimum number of vertices (edges) that need to be deleted from $G$ to produce a disconnected graph with at least $\ell$ components or a graph with at most $\ell -1$ vertices. Let $G$ be a graph of order $p$ and $\ell$-connectivity ${\kappa }_{\ell }$. For each $k\in \{0,1,\dots ,{\kappa }_{\ell }\}$, let $s_k$ be the minimum $\ell$-edge-connectivity among all graphs obtained from $G$ by deleting $k$ vertices from $G$. Then $f_{\ell }=\{(0,s_0),\dots ,({\kappa }_{\ell },s_{{\kappa }_{\ell }})\}$ is the $\ell$-connectivity function of $G$. The $\ell$-connectivity functions of complete multipartite graphs and caterpillars are determined.