Given a connected graph $G$ with $n$ vertices, a routing $R$ is a collection of $n(n-1)$ paths, one path $R(x,y)$ for each ordered pair $x,y$ of vertices. A routing is said to be vertex/edge-antisymmetric if for every pair $x,y$ of vertices, the paths $R(x,y)$ and $R(y,x)$ are internally vertex/edge-disjoint. Compared to other types of routing found in the literature, antisymmetric routing is interesting from a practical point of view because it ensures greater network reliability.

For a given graph $G$ and routing $R$, the vertex/edge load of $G$ with respect to $R$ is the maximum number of paths passing through any vertex/edge of $G$. The $vertex/edge-forwarding-index$ of a graph is the minimum vertex/edge load taken over all routings. If routing $R$ is vertex/edge-antisymmetric, we talk about $antisymmetric-indices$.

Several results exist in the literature for the forwarding-indices of graphs. In this paper, we derive upper and lower bounds for the antisymmetric-indices of graphs in terms of their connectivity or minimum degree. These bounds are often the best possible. Whenever this is the case, a network that meets the corresponding bound is described. Several related conjectures are proposed throughout the paper.

A tree $R$ such that after deleting all leaves we obtain a path $P$ is called a $caterpillar$. The path $P$ is called the $spine$ of the caterpillar $R$. If the spine has length 3 and $R$ on $2n$ vertices contains vertices of degrees $r$, $s$, $t$, $2$, where $2<r,s,t<n$, then we say that $R$ is an $(r,s,t,2)$-$caterpillar$ of diameter 5. We completely characterize $(r,s,t,2)$-caterpillars of diameter 5 on $4k+2$ vertices that factorize the complete graph $K_{4k+2}$.

This paper studies convex geometric graphs in which no path of length 3 self-intersects. A main result gives a decomposition of such graphs into induced outerplanar graph drawings. The resulting structure theorem is then used to compute a sharp, linear upper bound on the size of the edge set in terms of the number of vertices and the number and type of graphs in the decomposition. The paper also shows that though locally outerplanar graphs have hereditary properties, no graph property that is closed under the taking of minors can hold for all locally outerplanar graphs. Each of these results is generalized to convex geometric graphs in which no path of length $k$ self-intersects.

By means of the partial fraction method, we investigate the decomposition of rational functions. Several striking identities on harmonic numbers and generalized Apéry numbers will be established, including the binomial-harmonic number identity associated with Beukers’ conjecture on Apéry numbers.

Previous work on a certain class of non-terminating expansions of the sine function leads directly to a new result for associated infinite series by straightforward integration. A general identity is established, particular cases verified and two proofs of its hypergeometric form given.

An oriented graph is 2-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let $H$ be a 2-stratified oriented graph rooted at some blue vertex. An $H$-coloring of an oriented graph $D$ is a red-blue coloring of the vertices of $D$ in which every blue vertex $v$ belongs to a copy of $H$ rooted at $v$ in $D$. The $H$-domination number ${\gamma }_H(D)$ is the minimum number of red vertices in an $H$-coloring of $D$. We investigate $H$-colorings in oriented graphs where $H$ is the red-red-blue directed path of order 3. Relationships between the $H$-domination number ${\gamma }_H$ and both the domination number $\gamma$ and open domination ${\gamma }_o$, in oriented graphs are studied. It is shown that $\gamma (D)\le {\gamma }_H(D)\le {\gamma }_o(D)\le \lfloor \frac{3{\gamma }_H(D)}{2}\rfloor$ for every oriented graph $D$. All pairs of positive integers that can be realized as (1) domination number and $H$-domination number and (2) the $H$-domination number and open domination number of some oriented graph are determined. Sharp bounds are established for the $H$-domination number of an $r$-regular oriented graph in terms of $r$ and its order.

Defining sets of balanced incomplete block designs (BIBDs) were introduced by Ken Gray. Various authors have since identified minimal defining sets of particular BIBDs or classes of BIBDs, usually among those with small values of $\lambda$.

Here we present results based on defining sets of full designs, that is, designs comprising all $k$-tuples on a given set of $v$ elements. These defining sets are useful, despite their relatively large $\lambda$ values, since we show that a defining set of any simple BIBD can often be derived from a defining set of the corresponding full design. This leads to an upper bound on the number of simple designs with given parameters, provided that a $(v,k,\lambda )$ BIBD exists for minimum feasible $\lambda$.

A backtracking over near parallel classes with an early isomorph rejection is carried out to enumerate all the near resolvable $(2k+1,k,k-1)$ balanced incomplete block designs for $3\le k\le 13$. We first prove some results which enable us to restrict the search space of near parallel classes. The number of nonisomorphic designs is equal to 1 for each $3\le k\le 8$ and there are respectively 2, 0, 19, 8, and 374 nonisomorphic designs for $k=9,10,11,12$, and $13$.

Let ${\gamma }_t(G)$ denote the total domination number of the graph $G$. A graph $G$ is said to be total domination edge critical, or simply ${\gamma }_t$-critical, if ${\gamma }_t(G+e)<{\gamma }_t(G)$ for each edge $e\in E(\overline{G})$. We show that, for $4_t$-critical graphs $G$, that is, ${\gamma }_t$-critical graphs with ${\gamma }_t(G)=4$, the diameter of $G$ is either $2$, $3$, or $4$. Further, we characterize structurally the $4_t$-critical graphs $G$ with $\text{diam}(G)=4$.

In the Shamir $(k,n)$ threshold scheme, if one or more of the $n$ shares are fake, then the secret may not be reconstructed correctly by some sets of $k$ shares. Supposing that at most $t$ of the $n$ shares are fake, Rees et al. (1999) described two algorithms to determine consistent sets of shares so that the secret can be reconstructed correctly from $k$ shares in any of these consistent sets. In their algorithms, no honest participant can be absent and at least $n–t$ shares should be pooled during the secret reconstruction phase. In this paper, we propose a modified algorithm for this problem so that the number of participants taking part in the secret reconstruction can be reduced to $k+2t$ and the shares need to be pooled can be reduced to, in the best case, $k+t$, and less than or equal to $k+2t$ in the others. Its performance is evaluated. A construction for $t$-coverings, which play key roles in these algorithms, is also provided.

A linear $k$-forest is a graph whose components are paths with lengths at most $k$. The minimum number of linear $k$-forests needed to decompose a graph $G$ is the linear $k$-arboricity of $G$ and is denoted by $l{a}_k(G)$. In this paper, we study the linear $3$-arboricity of balanced complete multipartite graphs and we obtain some substantial results.

Let $m_2(N,q)$ denote the size of the largest caps in $PG(N,q)$ and let $m_2\prime (N,q)$ denote the size of the second-largest complete caps in $PG(N,q)$. Presently, it is known that $m_2(4,5)\le 111$ and that $m_2(4,7)\le 316$. Via computer searches for caps in $PG(4,5)$ using the result of Abatangelo, Larato, and Korchmáros that $m_2\prime (3,5)=20$, we improve the first upper bound to $m_2(4,5)\le 88$. Computer searches in $PG(3,7)$ show that $m_2\prime (3,7)=32$, and this latter result then improves the upper bound on $m_2(4,7)$ to $m_2(4,7)\le 238$. We also present the known upper bounds on $m_2(N,5)$ and $m_2(N,7)$ for $N>4$.

A sum of disjoint products (SDP) representation of a Boolean function is useful because it provides readily available information about the function; however, a typical SDP contains many more terms than an equivalent ordinary sum of products. We conjecture the existence of certain particular SDP forms of $x_1+\cdots +x_t$, which could be used as patterns in creating relatively economical SDP forms of other Boolean functions.