In this paper we have investigated harmonious labelings of \(p\)-stars, where a \(p\)-star of length \(x\) is a star tree in which each edge is a path of length \(k\). We have also demonstrated an application of the labelings to \(k\) disjoint \(p\)-cycles.

We show that if a graph \(G\) has \(n\) non-isomorphic \(2\)-vertex deleted subgraphs then \(G\) has at most \(n\) distinct degrees. In addition, we prove that if \(G\) has \(3\) non-isomorphic \(3\)-vertex deleted subgraphs then \(G\) has at most \(3\) different degrees.

Observability of a graph is the least \(k\) admitting a proper coloring of its edges by \(k\) colors in such a way that each vertex is identifiable by the set of colors of its incident edges. It is shown that for \(p \geq 3\) and \(q \geq 2\) the complete \(p\)-partite graph with all parts of cardinality \(q\) has observability \((p-1)q+2\).

Let \(V\) be a finite set of order \(\nu\). A \((\nu,\kappa,\lambda)\) packing design of index \(\lambda\) and block size \(\kappa\) is a collection of \(\kappa\)-element subsets, called blocks, such that every \(2\)-subset of \(V\) occurs in at most \(\lambda\) blocks. The packing problem is to determine the maximum number of blocks, \(\sigma(\nu,\kappa,\lambda)\), in a packing design. It is well known that \(\sigma(\nu,\kappa,\lambda) < \left[ \frac{\nu}{\kappa}[\frac{(\nu-1)}{\kappa(\kappa-1)}] \right] = \psi(\nu,\kappa,\lambda)\), where \([x]\) is the largest integer satisfying \(x \ge [x]\). It is shown here that if \(v \equiv 2 \pmod{4}\) and \(\nu \geq 6\) then \(\sigma(\nu,5,3) = \psi(\nu,5,3)\) with the possible exception of \(v = 38\).

In this paper we obtain some new relations on generalized exponents of primitive matrices. Hence the multiexponent of primitive tournament matrices are evaluated.

The ranking and unranking problem of a Gray code \(C(n,k)\) for compositions of \(n\) into \(k\) parts is solved. This means that rules have been derived by which one can calculate in a non-recursive way the index of a given codeword, and vice versa, determine the codeword with a given index. A number system in terms of binomial coefficients is presented to formulate these rules.

In the definition of local connectivity, the neighbourhood of a vertex consists of the induced subgraph of all vertices at distance one from the vertex. In {[2]}, we introduced the concept of distance-\(n\) connectivity in which the distance-\(n\) neighbourhood of a vertex consists of the induced subgraph of all vertices at distance less or equal to \(n\) from that vertex. In this paper we present Menger-type results for graphs whose distance-\(n\) neighbourhoods are all \(k\)-connected, \(n \geq 1\).

A partially ordered set \(P\) is called a circle order if one can assign to each element \(a \in P\) a circular disk in the plane \({C_a}\), so that \(a < b\) iff \(C_a \subset C_b\). It is known that the dual of every finite circle order is a circle order. We show that this is false for infinite circle orders.

In [Discrete Math. 46 (1983) 191 – 198], the concept of inclusive edge connectivity was introduced and discussed. Given a vertex \(v \in V(G)\), the inclusive edge connectivity of \(v\), denoted by \(\lambda_i(v,G)\), is the minimum number of edges whose deletion results in a subgraph of \(G\) in which \(v\) is a cut-vertex. Define

\[\lambda_i(v,G) = \min\{\lambda_i(v,G) : v \in V(G), \text{ and } d_G(v) \geq 2\}\]

to be the inclusive edge connectivity of \(G\). Extremal problems on \(\lambda_i(G)\) are studied in this paper.

If the binding number of a graph \(G\) is more than \(1 + \frac{a-1}{b}\), does \(G\) have an \([a,b)\)-factor? The answers to this question for the case of either \(a = b\) or \(a \leq 3\) can be found in [1], [2], [4], and [7]. Here we give some more answers for \(4 \leq a \leq b\).

The design of de Bruijn sequences is equivalent to finding spanning trees in certain graphs. We give an algorithm which finds spanning
trees in these graphs using the universal circuit matrix defined in \([9]\).

In this note, we obtain nonexistence results for \((m,2,m-1,\frac{m-2}{2})\) relative difference sets. In particular, we obtain further restriction on the parameters of splitting \((m,2,m-1,\frac{m-2}{2})\) relative difference set under certain condition.

We define a new embedding invariant, namely \(n\)-polyhedrality, and we propose a program of research in which the objective is to enumerate the \(n\)-polyhedral embeddings of a given graph for various values of \(n\). We begin the program for the cartesian products of cycles by showing that \(C_3 \times C_n\) has exactly one \(3\)-polyhedral embedding.

A near \(d\)-angulation is a planar graph in which every region has degree \(d\) except for the boundary region. Let \(T\) be a spanning tree with all of its vertices of odd degree on the boundary. Then the interior regions can be 2-colored so that regions that share edges of \(T\) receive different colors and regions which share edges not in \(T\) receive the same color. The boundary region is given a third color. We prove that the number of regions of each color can be determined from only knowing the behavior on the boundary.

It is known that the boundary function \(\alpha\) on union-closed collections containing \(n\) sets has property \(\alpha(n) \leq \alpha(n)\), where \(\alpha(n)\) is Conway’s sequence. Herein a function \(f\) is defined on the positive integers and it is shown that for each value of \(n > 1\) a union-closed collection of \(n\) sets can be constructed with greatest element frequency \(\beta(n)\) and hence \(\alpha(n) \leq \beta(n)\); the inequality \(\beta(n) \leq \alpha(n)\) is proven for \(n \geq 1\) and so \(f\) is a closer approximation than \(\alpha\) to the boundary function \(\alpha\). It is also shown that \(\beta(n) \geq \frac{n}{2}\), thus incidentally providing an alternative proof to that of Mallows, that \(\alpha(n) \geq \frac{n}{2}\) for \(n \geq 1\).

Let \(G\) be a connected graph and \(T\) be a spanning tree of \(G\). (Here, trees and cycles are equated with their edge sets.) Then, the gi-pair \((G,T)\) is a dfs-pair if there exists a digraph \(D\) such that the underlying graph of \(D\) is \(G\), \(T\) is a rooted-ditree in \(D\), and every fundamental cycle of \((G,T)\) is a dicycle of \(D\). Two gi-pairs \((G,T)\) and \((G’,T)\) are cycle-isomorphic if there is a 1-1 mapping between \(Z(G)\) and \(Z(G’)\) so that \((G,T)\) and \((G’,T)\) have the same sets of fundamental cycles. Shinoda, Chen, Yasuda, Kajitani, and Mayeda [6] showed that a 2-connected graph \(G\) is series-parallel if and only if for every spanning tree \(T\) of \(G\), the gi-pair \((G,T)\) is cycle-isomorphic to a dfs-pair. In this paper, an alternate proof of this characterization is given. An efficient algorithm to find such a cycle-isomorphic dfs-pair is also described.

We determine the exact closure of all subsets \(K\) of \(\{3,\ldots,10\}\) which contain \(3\).

Let \(G\) be a simple graph on \(n\) vertices and an even number of edges. It was proved in [15] that the zero-sum (mod 2) Ramsey numbers are given by

\[R(G,\mathbb{Z}_2) =
\begin{cases}
n+2 & \text{if } G = K_{n}, n \equiv 0,1 \pmod{4} \\
n+1 & \text{if } G = K_{p} \cup K_q({\frac{p}{2}}) + (\frac{q}{2}) \equiv 0 \pmod{2} \\
n+1 & \text{if all degrees in } G \text{ are odd} \\
n & \text{otherwise}
\end{cases}
\]

The proof is rather long and based on complicated algebraic machinery. Here we shall prove that \(R(G,\mathbb{Z}_2) \leq n+2\) with equality holding iff \(G = K_{n,}n \equiv 0,1 \pmod{4}\).

The proof uses simple combinatorial arguments and it is also applied to the case, not considered before, when \(G\) has an odd number of edges. Some algorithmic aspects, which cannot be tackled using the methods of [1] and [15], are also considered.

In a previous paper [2] it was established that, up to isomorphism, there exist at least 112,000 symmetric \(2-(41,16,6)\) designs with a non-trivial automorphism of odd order. Using the underlying derived designs of just one of these and extending them to a \(2-(41,16,6)\) design we have found ten non-isomorphic symmetric \(2-(41,16,6)\) designs with trivial automorphism group (five pairs of non-selfdual designs).

A dominating function for a graph is a function from its vertex set into the unit interval so that the sum of function values taken ‘over the closed neighbourhood of each vertex is at least one. We prove that any graph has a positive minimal dominating function and begin an investigation of the question: When are convex combinations of minimal dominating functions themselves minimal dominating?

The author and N.K. Khachatrian proved that a connected graph \(G\) of order at least \(3\) is hamiltonian if for each vertex \(x\) the subgraph \(G_1(x)\) induced by \(x\) and its neighbors in \(G\) is an Ore graph.

We prove here that a graph \(G\) satisfying the above conditions is fully cycle extendible. Moreover, \(G\) is panconnected if and only if \(G\) is \(3\)-connected and \(G \neq K_n \lor \overline{K}_n\) for some \(n \geq 3\), where \(\lor\) is the join operation. The paper is concluded with two conjectures.

Let \(p,q\) denote primes, \(p \equiv 1 \pmod{4}\), \(g \equiv 3 \pmod{4}\), \(g \geq 7\). In an earlier study we established that if \(\gcd(q-1, p^{n-1}(p-1)) = 2\) and if a \(\mathbb{Z}\)-cyclic \(Wh(q+1)\) exists then a \(\mathbb{Z}\)-cyclic \(Wh(qp^n + 1)\) exists for all \(n \geq 0\). Here we consider \(\gcd(qg-1,p^{n-1}(p-1)) > 2\) and prove that if a \(\mathbb{Z}\)-cyclic \(Wh(q+1)\) exists then there exists a \(\mathbb{Z}\)-cyclic \(Wh(qp^n + 1)\) for all \(n \geq 0\). The proof employed depends on the existence of an appropriate primitive root of \(p\). Utilizing a theorem of S. D. Cohen we establish that such appropriate primitive roots always exist.

A 2-distant coloring of a graph is an assignment of positive integers to its vertices so that adjacent vertices cannot get either the same number or consecutive numbers. Given a 2-distant coloring of a graph \(G\), a hole of \(f\) is a finite maximal set of consecutive integers not used by \(f\), and \(h(f)\) is the number of holes of \(f\). In this paper we study the problem of minimizing the number of holes, i.e., we are interested in the number \(h(G) = \min_f h(f)\) where the minimum runs over all 2-distant colorings \(f\) of \(G\). Besides finding exact values for \(h(G)\) for particular graphs, we also relate \(h(G)\) to the path-covering number and the Hamiltonian completion number of \(G\).

For graph \(G\), a total dominating set \(S\) is a subset of the vertices in \(G\) such that every vertex in \(G\) is adjacent to at least one vertex in \(S\). The total domination number of \(G\) is the cardinality of a smallest total dominating set of \(G\). We consider the total domination number of graphs formed from an \(m\times n\) chessboard by letting vertices represent the squares, and letting two vertices be adjacent if a given chess piece can move between the associated squares. In particular, we bound from above and below the total domination numbers of the graphs induced by the movement of kings, knights, and crosses (a hypothetical piece that moves as does a king, except that it cannot move diagonally). We also provide some results of computer searches for the total domination numbers of small square boards.

A set of integers is \(k\)-multiple-free if it never contains two integers \(x\) and \(kx\), where \(k\) is a given integer greater than \(1\). Such a set \(S\) is maximal in \([1,n] = \{1,2,\dots,n\}\) if \(S \cup \{t\}\) is not \(k\)-multiple free for any \(t\) in \([1,n] \setminus S\). In this paper we investigate the size of maximal \(k\)-multiple-free subsets of \([1,n]\), prove that the smallest such set has \(\frac{(k^5-k^3+1)n}{k(k+1)(k^3-1)}+ 0(\log n)\) members, and show that given \(k\) and \(n\), if \(s\) is any integer between the minimum and maximum possible orders, there is a maximal \(k\)-multiple-free subset of \([1,n]\) with \(s\) elements.

Let \(G\) be a simple graph. A set \(D\) of vertices of \(G\) is dominating if every vertex not in \(D\) is adjacent to some vertex in \(D\). A set \(M\) of edges of \(G\) is called independent, or a matching, if no two edges of \(M\) are adjacent in \(G\). The domination number \(\gamma(G)\) is the minimum order of a dominating set in \(G\). The edge independence number \(\alpha_0(G)\) is the maximum size of a matching in \(G\). If \(G\) has no isolated vertices, then the inequality \(\gamma(G) \leq \alpha_0(G)\) holds. In this paper we characterize regular graphs, unicyclic graphs, block graphs, and locally connected graphs for which \(\gamma(G) = \alpha_0(G)\).

Let \(n \geq 1\) be an integer and let \(G\) be a graph of order \(p\). A set \(I_n\) of vertices of \(G\) is \(n\)-independent if the distance between every two vertices of \(I_n\) is at least \(n+1\). Furthermore, \(I_n\) is defined to be an \(n\)-independent dominating set of \(G\) if \(I_n\) is an \(n\)-independent set in \(G\) and every vertex in \(V(G) – I_nv is at distance at most \(n\) from some vertex in \(I_n\). The \(n\)-independent domination number, \(i_n(G)\), is the minimum cardinality among all \(n\)-independent dominating sets of \(G\). Hence \(i_n(G) = i(G)\) where \(i(G)\) is the independent domination number of \(G\). We establish the existence of a connected graph \(G\) every spanning tree \(T\) of which is such that \(i_n(T) < i_n(G)\). For \(n \in \{1,2\}\) we show that, for any tree \(T\) and any tree \(T’\) obtained from \(T\) by joining a new vertex to some vertex of \(T\), we have \(i_n(T) \geq i_n(T’)\). However, we show that this is not true for \(n \geq 3\). We show that the decision problem corresponding to the problem of computing \(i_n(G)\) is NP-complete, even when restricted to bipartite graphs. Finally, we obtain a sharp lower bound on \(i_n(G)\) for a graph \(G\).

In this paper, we consider symmetric and skew equivalence of Hadamard matrices of order \(28\) and present some computational results and some applications.

We consider a linear model for the comparison \(V \geq 2\) treatments (or one treatment at \(V\) levels) in a completely randomized statistical setup, making \(r\) (the replication number) observations per treatment level in the presence of \(K\) continuous covariates with values on the \(K\)-cube. The main interest is restricted to cyclic designs characterized by the property that the allocation matrix of each treatment level is obtained through cyclic permutation of the columns of the allocation matrix of the first treatment level. The \(D\)-optimality criterion is used for estimating all the parameters of this model.

By studying the nonperiodic autocorrelation function of circulant matrices, we develop an exhaustive algorithm for constructing \(D\)-optimal cyclic designs with even replication number. We apply this algorithm for \(r = 4, 16 \leq V \leq 24, N=rV \equiv 0 \mod 4\), for \(r=6, 12\leq V \leq 24, N =rV \equiv 0 \mod 4\), for \(r =6, V =m.n, m\) is a prime, \(N =rV \equiv 2 \mod 4\) and the corresponding cyclic designs are given.