Let \(r(a)\) be the replication number of the vertex \(a\) of a path design \(P(v,k, 1)\), \(k \geq 3\). Let \(\bar{r}(v,k) = \text{min}\{\text{max}_{a\in V} \,r(a) | (V,\mathcal{B}) \text{ is a } P(v,k, 1)\}\). A path design \(P(v,k,1)\), \((W,\mathcal{D})\), is said to be \emph{almost balanced} if \(\bar{r}(v,k) – 1 \leq r(y) \leq \bar{r}(v,k)\) for each \(y \in W\). Let \(v \equiv 0 \text{ or } 1 \pmod{2(k-1)}\) (for each odd \(k\), \(k \geq 3\)) and let \(v_y \equiv 0 \text{ or } 1 \pmod{k-1}\) (for each even \(k\), \(k \geq 4\)). In this note, we determine the spectrum \(\mathcal{B}\mathcal{S}\mathcal{A}\mathcal{B}\mathcal{P}(v,k,1)\) of integers \(x\) such that there exists an almost balanced path design \(P(v,k, 1)\) with a blocking set of cardinality \(x\).

A border of a string \(x\) is a proper (but possibly empty) prefix of \(x\) that is also a suffix of \(x\). The \emph{border array} \(\beta = \beta[1..n]\) of a string \(x = x[1..n]\) is an array of nonnegative integers in which each element \(\beta(i)\), \(1 \leq i \leq n\), is the length of the longest border of \(x[1..i]\). In this paper, we first present a simple linear-time algorithm to determine whether or not a given array \(y = y[1..n]\) of integers is a border array of some string on an alphabet of unbounded size, and then a slightly more complex linear-time algorithm for an alphabet of any given (bounded) size \(\alpha\). We then consider the problem of generating all possible distinct border arrays of given length \(n\) on a bounded or unbounded alphabet, and doing so in time proportional to the number of arrays generated. A previously published algorithm that claims to solve this problem in constant time per array generated is shown to be incorrect, and new algorithms are proposed. We conclude with an equally efficient on-line algorithm for this problem.

In developing an observation made by the author concerning a class of expansions of the sine function, M. Xinrong has recently analysed the question of a generalised form through a succinct use of linear operator theory. This paper constitutes an extension of his work, in which the current problem is solved completely by examining the generating function of a finite sequence central to the formulation.

For graphs \(G\) and \(H\), the Ramsey number \(R(G, H)\) is the least integer \(n\) such that every 2-coloring of the edges of \(K_n\) contains a subgraph isomorphic to \(G\) in the first color or a subgraph isomorphic to \(H\) in the second color. Graph \(G\) is a \((C_4, K_n)\)-graph if \(G\) doesn’t contain a cycle \(C_4\) and \(G\) has no independent set of order \(n\). Jayawardene and Rousseau showed that \(21 \leq R(C_4, K_7) \leq 22\). In this work, we determine \(R(C_4, K_7) = 22\) and \(R(C_4, K_8) = 26\), and enumerate various families of \((C_4, K_n)\)-graphs. In particular, we construct all \((C_4, K_n)\)-graphs for \(n < 7\), and all \((C_4, K_n)\)-graphs on at least 19 vertices. Most of the results are based on computer algorithms.

For \(\text{k}>0\), we call a graph G=(V,E) as \underline{\(\text{Z}_\text{k}\)-magic} if there exists an edge labeling \(\text{I: E(G)} \rightarrow \text{Z}_\text{k}^*\) such that the induced vertex set labeling \(\text{I}^+: \text{V(G)} \rightarrow \text{Z}_\text{k}\) defined by

\[\text{I}^+(\text{v}) = \Sigma \{(\text{I(u,v)) : (u,v)} \in \text{E(G)}\}\]

is a constant map. We denote the set of all k such that G is k-magic by IM(G). We call this set as the \textbf{integer-magic spectrum} of G. This paper deals with determining the integer-magic spectra of powers of paths \(\text{P}\text{n}^\text{k}\) for k=2 and 3. We also show that IM(\(\text{P}_{2\text{k}}^\text{k}) = \text{N}\setminus\{2\}\) for all odd integers \(\text{k}>1\). Finally, a conjecture for IM\((\text{P}_\text{n}^\text{k})\) for \(\text{k}\geq4\) is proposed.

A new graph labeling problem on simple graphs called edge-balanced labeling is introduced by Kong and Lee [11]. They conjectured that all trees except \(K_{1,n}\) where \(n\) is odd, and all connected regular graphs except \(K_2\) are edge-balanced. In this paper, we extend the concept of edge-balanced labeling to multigraphs and completely characterize the edge-balanced multigraphs. Thus, we proved that the above two conjectures are true. A byproduct of this result is a proof that the problem of deciding whether a graph is edge-balanced does not belong to NP-hard.

Let \(\Gamma\) be a finite group and let \(X\) be a subset of \(\Gamma\) such that \(X^{-1} = X\) and \(1 \notin X\). The conjugacy graph \(\text{Con}(\Gamma; X)\) has vertex set \(\Gamma\) and two vertices \(g, h \in \Gamma\) are adjacent in \(\text{Con}(\Gamma; X)\) if and only if there exists \(x \in X\) with \(g = xhx^{-1}\). The components of a conjugacy graph partition the vertices into conjugacy classes (with respect to \(X\)) of the group. Sufficient conditions for a conjugacy graph to have either vertex-transitive or arc-transitive components are provided. It is also shown that every Cayley graph is the component of some conjugacy graph.

By definition, the vertices of a de Bruijn graph are all strings of length \(n-1\) (\(n>1\)) over a fixed finite alphabet. The edges are all strings of length \(n\) over the same alphabet. The directed edge \(a_1\ldots a_n\) joins vertex \(a_1\ldots a_{n-1}\) to vertex \(a_2\ldots a_n\). A block code over an alphabet of \(\sigma\) elements is comma-free if it does not contain any overlap of codewords. Representing the codewords of comma-free codes as directed edges of the de Bruijn graph, we give sufficient conditions that a bipartite subgraph of the de Bruijn graph whose underlying undirected graph is connected is a comma-free code.

Given two graphs \(G\) and \(H\), the composition of \(G\) with \(H\) is the graph with vertex set \(V(G) \times V(H)\) in which \((u_1, v_1)\) is adjacent to \((u_2, v_2)\) if and only if \(u_1u_2 \in E(G)\) or \(u_1 = u_2\) and \(v_1v_2 \in E(H)\). In this paper, we prove that the composition of a regular supermagic graph with a null graph is supermagic. With the help of this result, we show that the composition of a cycle with a null graph is always supermagic.

In this paper, we discuss a self-adjusting and self-improving combinatorial optimization algorithm. Variations of this algorithm have been successfully applied in recent research in Design Theory. The approach is simple but general and can be applied in any instance of a combinatorial optimization problem.

Let \(n, x\) be positive integers satisfying \(1 < x < n\). Let \(H_{n,x}\) be a group admitting a presentation of the form \(\langle a, b \mid a^n = b^2 = (ba)^x = 1 \rangle\). When \(x = 2\) the group \(H_{n,x}\) is the familiar dihedral group, \(D_{2n}\). Groups of the form \(H_{n,x}\) will be referred to as generalized dihedral groups. It is possible to associate a cubic Cayley graph to each such group, and we consider the problem of finding the isoperimetric number, \(i(G)\), of these graphs. In section two we prove some propositions about isoperimetric numbers of regular graphs. In section three the special cases when \(x = 2, 3\) are analyzed. The former case is solved completely. An upper bound, based on an analysis of the cycle structure of the graph, is given in the latter case. Generalizations of these results are provided in section four. The indices of these graphs are calculated in section five, and a lower bound on \(i(G)\) is obtained as a result. We conclude with several conjectures suggested by the results from earlier sections.

Let \(G\) be a transitive permutation group on a set \(Q\). The orbit decompositions of the actions of \(G\) on the sets of ordered \(n\)-tuples with elements repeated at most three times are studied. The decompositions involve Stirling numbers and a new class of related numbers, the so-called tri-restricted numbers. The paper presents exponential generating functions for the numbers of orbits, and examines relationships between various powers of the \(G\)-set involving Stirling numbers, the tri-restricted numbers, and the coefficients of Bessel polynomials.

Let \(\Gamma\) be a finite group and let \(\Delta\) be a generating set for \(\Gamma\). A Cayley map associated with \(\Gamma\) and \(\Delta\) is an oriented 2-cell embedding of the Cayley graph \(G_\Delta(\Gamma)\) such that the rotation of arcs emanating from each vertex is determined by a unique cyclic permutation of generators and their inverses. A formula for the average Cayley genus is known for the dihedral group with generating set consisting of all the reflections. However, the known formula involves sums of certain coefficients of a generating function and its format does not specifically indicate the Cayley genus distribution. We determine a simplified formula for this average Cayley genus as well as provide improved understanding of the Cayley genus distribution.

A (p,q) graph G is \emph{total edge-magic} if there exists a bijection \(\text{f}: \text{V} \cup \text{E} \rightarrow \{1,2, \ldots, \text{p+q}\}\) such that \(\forall\, \text{e} = \text{(u,v)} \in \text{E}\), f(u) + f(e) + f(v) = constant. A total edge-magic graph is a \emph{super edge-magic graph} if \(\text{f(V(G))} = \{1,2, \ldots, \text{p}\}\). For \(\text{n} \geq 2\), let \(\text{a}_1, \text{a}_2, \text{a}_3, \ldots, \text{a}_\text{n}$ be a sequence of increasing non-negative integers. A n-star \(S(\text{a}_1, \text{a}_2, \text{a}_3, \ldots, \text{a}_\text{n})\) is a disjoint union of n stars \(\text{St}(\text{a}_1),\text{ St}(\text{a}_2), \ldots, \text{St}(\text{a}_\text{n})\). In this paper, we investigate several classes of n-stars that are super edge-magic.

For \(k>0\), we call a graph \(G=(V,E)\) as \underline{\(Z_k\)-magic} if there exists a labeling \(I: E(G) \rightarrow {Z}_k^*\) such that the induced vertex set labeling \(I^+: V(G) \rightarrow {Z}_k\)
\[I^+(v) = \Sigma \{I(u,v) : (u,v) \in E(G)\}\]
is a constant map. We denote the set of all \(k\) such that \(G\) is \(k\)-magic by \(IM(G)\). We call this set as the integer-magic spectrum of \(G\). We investigate these sets for general graphs.

Several \(q\)-polynomial identities are derived from a consideration of classical finite polar spaces. One class of identities is obtained by sorting maximal singular spaces with respect to a given one. Another class is derived from sorting sesquilinear and quadratic forms according to their radicals.

We describe a concrete data structure, called a sequence-tree, that represents sequences of arbitrary elements, along with associated algorithms that allow single element access and assignment, subsequence extraction (slicing), and concatenation to be done in logarithmic time relative to sequence length. These operations are functional, in the sense that they leave their operand sequences unchanged. For a single sequence, space is linear in the sequence length. Where a set of multiple sequences have been computed by these algorithms, space may be sublinear, because of node sharing. Sequence-trees use immutable, shared, dynamically allocated nodes and thus may require garbage collection, if some of the sequences in a set are abandoned. However, the interconnection of nodes is non-cyclic, so explicitly programmed collection using reference counting is reasonable, should a general-purpose garbage collector be unavailable. Other sequence representations admit only to linear-time algorithms for one or more of the aforementioned operations. Thus sequence-trees give improved performance in applications where all the operations are needed.

This paper is an expository treatment of the Leftover Hash Lemma and some of its applications in cryptography and complexity theory.