Bollobas posed the problem of finding the least number of edges, \(f(n)\), in a maximally nonhamiltonian graph of order \(n\). Clark, Entringer and Shapiro showed \(f(n) = \left\lceil \frac{3n}{2} \right\rceil\) for all even \(n \geq 36\) and all odd \(n \geq 53\). In this paper, we give the values of \(f(n)\) for all \(n \geq 3\) and show \(f(n) = \left\lceil \frac{3n}{2} \right\rceil\) for all even \(n \geq 20\) and odd \(n \geq 17\).

Three mutually orthogonal idempotent Latin squares of order \(18\) are constructed, which can be used to obtain \(3\) HMOLS of type \(5^{18}\) and type \(23^{18}\) and to obtain a \((90, 5, 1)\)-PMD.

A graph is well-covered if every maximal independent set is also a maximum independent set. A \(1\)-well-covered graph \(G\) has the additional property that \(G – v\) is also well-covered for every point \(v\) in \(G\). Thus, the \(1\)-well-covered graphs form a subclass of the well-covered graphs. We examine triangle-free \(1\)-well-covered graphs. Other than \(C_5\) and \(K_2\), a \(1\)-well-covered graph must contain a triangle or a \(4\)-cycle. Thus, the graphs we consider have girth \(4\). Two constructions are given which yield infinite families of \(1\)-well-covered graphs with girth \(4\). These families contain graphs with arbitrarily large independence number.

A \(d\)-dimensional Perfect Factor is a collection of periodic arrays in which every \(k\)-ary \((n_1, \ldots, n_d)\) matrix appears exactly once (periodically). The one-dimensional case, with a collection of size one, is known as a De Bruijn cycle. The \(1\)- and \(2\)-dimensional versions have proven highly applicable in areas such as coding, communications, and location sensing. Here we focus on results in higher dimensions for factors with each \(n_i = 2\).

It is shown that the existence of a semi-regular automorphism group of order \(m\) of a binary design with \(v\) points implies the existence of an \(n\)-ary design with \(v/m\) points. Several examples are described. Examples of other \(n\)-ary designs are considered which place such \(n\)-ary designs in context among \(n\)-ary designs generally.

Let \(G\) be a connected graph with \(v \geq 3\). Let \(v \in V(G)\). We define \(N_k(v) = \{u|u \in V(G) \text{ and } d(u,v) = k\}\). It is proved that if for each vertex \(v \in V(G)\) and for each independent set \(S \subseteq N_2(v)\), \(|N(S) \cap N(v)| \geq |S| + 1\), then \(G\) is hamiltonian. Several previously known sufficient conditions for hamiltonian graphs follow as corollaries. It is also proved that if for each vertex \(v \in V(G)\) and for each independent set \(S \subseteq N_2(v)\), \(|N(S) \cap N(v)| \geq |S| + 2\), then \(G\) is pancyclic.

We give recursive methods for enumerating the number of orientations of a tree which can be efficiently dominated. We also examine the maximum number, \(\eta_q\), of orientations admitting an efficient dominating set in a tree with \(q\) edges. While we are unable to give either explicit formulas or recursive methods for finding \(\eta_q\), we are able to show that the growth rate of the sequence \(\langle\eta_q\rangle\) stabilizes by showing that \(\lim_{q\to\infty}\eta^\frac{1}{q}_q \) exists.

Let \(G = (V, E)\) be a finite simple graph. \(G\) is said to be a magic graph iff there exists a magic assignment of \(G\), which is a mapping \(L\) from \(E\) to \({N} = \{1, 2, \ldots\}\) such that the sums of the labels of all edges incident to the vertices in \(V\) are identical. Let \(M(G)\) be the set of all magic assignments of \(G\). For any \(L\) in \(M(G)\), define \(s(L) = \max\{L(e): e \in E\}\). Then, the magic strength of \(G\) is defined as \(m(G) = \min\{s(L): L \in M(G)\}\). In this paper, we determine the magic strengths of several classes of graphs and introduce some constructions of magic graphs. We also show that every connected graph is an induced subgraph of a magic graph.

We determine upper bounds on the number of elements in connected and \(3\)-connected matroids with fixed rank and bounded cocircuit size. The existence of these upper bounds is a Ramsey property of matroids. We also determine size type function and extremal matroids in several classes of matroids with small cocircuits.

Let \(V\) be a finite set of order \(v\). A \((v, \kappa, \lambda)\) packing design of index \(\lambda\) and block size \(u\) is a collection of \(u\)-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(v, \kappa, \lambda)\), in a packing design. It is well known that \(\sigma(v, \kappa, \lambda) \leq [\frac{v}{\kappa}[\frac{v-1}{\kappa-1}\lambda]] = \psi(v, \kappa, \lambda)\), where \([ x ]\) is the largest integer satisfying \(x \geq [ x ]\). It is shown here that \(\sigma(v, 5, 3) = \psi(v, 5, 3)\) for all positive integers \(v \geq 5\) with the possible exceptions of \(v = 43\) and that \(\sigma(v, 5, 3) = \psi(v, 5, 3)\) for all positive integers \(v = 1, 5, 9, 17 \pmod{20}\) and \(\sigma(v, 5, 3) = \psi(v, 5, 3) – 1\) for all positive integers \(v \equiv 13 \pmod{20}\) with the possible exception of \(v = 17, 29, 33, 49\).

A graph with signed edges is orientation embedded in a surface when it is topologically embedded and a polygon preserves or reverses orientation depending on whether its sign product is positive or negative. We study orientation-embedding analogs of three facts about unsigned graph embedding: planarity is equivalent to having cographic polygon matroid, the polygon matroid of a graph determines the surfaces in which it embeds, and contraction preserves embeddability of a graph in a surface.
We treat three matroids of a signed graph. Our main results:
For a signed graph which is orientation embeddable in the projective plane, the bias and lift matroids (which coincide) are cographic.
Neither the bias nor lift nor complete lift matroid determines the surfaces in which a signed graph orientation embeds.
Of the two associated contractions of signed edges, the bias contraction does not preserve orientation embeddability but the lift contraction does.Thus the signed graphs which orientation embed in a particular surface are characterizable by forbidden lift minors.

A graph \(G\) having \(7\) vertices is called a chordal ring if its vertices can be arranged in a Hamiltonian cycle \(0, 1, 2, \ldots, n-1\) and there is a proper divisor \(d\) of \(n\) such that for all vertices \(i\) and \(j\), \(i\) is adjacent to \(j\) in \(G\) if and only if \(i+d\) is adjacent to \(j+d\) (addition modulo \(n\)). We consider here the efficacy of coloring the vertices of such a graph by the greedy algorithm applied to the vertices in the order of their appearance on the cycle. For any positive integer \(n\), let \(\Sigma_n\) denote the set of all permutations of the set \(\{1, 2, \ldots, n\}\) together with the adjacency relation \(\sim\) defined as follows: for \(\sigma\) and \(\tau\) in \(\Sigma_n\), \(\sigma \sim \tau\) if and only if there is an integer \(i\) such that \(\sigma-i = \tau-i\). (Here \(\sigma-i\) denotes the permutation of length \(n-1\) obtained by deleting \(i\) from \(\sigma\).) In this paper, we study some of the properties of the graph \((\Sigma_n, \sim)\). Two of the results obtained are the following:
(i) \((\Sigma_n, \sim)\) is a chordal ring for every positive integer \(n\);
(ii) the chromatic number of \(\Sigma_5\) is \(5\) but the greedy algorithm colors \(\Sigma_5\) in \(9\) colors.

A division of a cake \(X = X_1 \cup \cdots \cup X_n\) among \(n\) players with associated probability measures \(\mu_1, \ldots, \mu_n\) on \(X\) is said to be:

(a) exact in the ratios of \(\alpha_1 : \alpha_2 : \cdots : \alpha_n\) provided whenever \(1 \leq i, j \leq n\), \(\frac{\mu_i(X_j)} { \mu_1(X)} = \alpha_i / (\alpha_1 + \cdots + \alpha_n)\)

(b) \(\epsilon\)-near exact in the ratios \(\alpha_1 : \alpha_2 : \cdots : \alpha_n\) provided whenever \(1 \leq i, j \leq n\), \(|\frac{\mu_i(X_i)}{\mu_1(X_1)} + \cdots +\frac {\alpha_j}{\alpha_1 + \cdots + \alpha_n}| < \epsilon\)

(c) envy free in ratios \(\alpha_1 : \alpha_2 : \cdots : \alpha_n\) provided whenever \(1 \leq i, j \leq n\), \(\frac{\mu_i(X_i)}{\mu_i(X_j)} \geq \frac{\alpha_i}{\alpha_j}\).

A moving knife exact division is described for two players and it is shown there can be no finite exact algorithm for \(n \geq 2\) players. A bounded finite \(\epsilon\)-near exact algorithm is given which is used to produce a finite envy free, \(\epsilon\)-near exact algorithm.

We study bounds on the cardinality of sum-distinct sets of \(n\)-vectors with nonnegative integral components under component-wise real-number addition. A subclass of sum-distinct sets induced by an \(n \times n\) integral matrix of rank \(n\) is studied as well.

A family of subsets satisfies the Helly property when every subfamily of it, formed by pairwise intersecting subsets, has a common element. A graph is clique-Helly when the family of subsets of vertices which induces the maximal cliques of the graph satisfies the Helly property. We describe a characterization of clique-Helly graphs, leading to a polynomial time algorithm for recognizing them.

A semi-complete bigraph \(G\) has adjacency matrix
\[A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix},\]
where \(B + B^T = J – I\), so \(B\) is the adjacency matrix of a tournament \(T\) corresponding to \(G\). We determine algebraic and structural properties of this class of graphs. In particular, we obtain a condition equivalent to the connectedness of a semi-complete bigraph; moreover we determine characterizations of semi-complete bigraphs having 4 distinct eigenvalues in the case of \(G\) regular or \(A\) irreducible. In particular, a regular semi-complete bigraph has 4 distinct eigenvalues if and only if it corresponds to a doubly regular tournament.

Let \(D\) be an asymmetric digraph and \(A\) a finite group. We give a formula for the characteristic polynomial of a cyclic \(A\)-cover of \(D\). This is a generalization of a formula for the characteristic polynomial of a regular covering of a graph. Furthermore, we discuss cyclic abelian covers of \(D\).

We define an almost-convex polygon as a non-convex polygon in which any two vertices see each other inside the polygon unless they are not adjacent and belong to a chain of consecutive concave vertices. Using inclusion-exclusion techniques, we find formulas for the number of triangulations of almost-convex polygons in terms of the number and position of the concave vertices. We translate these formulas into the language of generating functions and provide several simple asymptotic estimates. We also prove that certain balanced configurations yield the maximum number of triangulations.

Let \(n,s\) be positive integers, and let \(r = 1 + \frac{1}{s}\). In this note we prove that if the sequence \(\{a_n(r)\}_{n=1}^{\infty}\) satisfies \(ra_n(r)= \sum_{k=1}^{n}\binom{n}{k}a_k(r), n> 1\), then \(a_n(r) = na_1(r)\left[(n -1)! / {(s+1)}(log r)^n+{{1/r(s+1)}} \right]\). Moreover, we obtain a related combinatorial identity.

A Mendelsohn triple system, \(MTS(v) = (X, \mathcal{B})\), is called self-converse if it and its converse \((X, \mathcal{B}^{-1})\) are isomorphic, where \(\mathcal{B}^{-1 } = \{\langle z,y,x\rangle; \langle x,y,z\rangle \in \mathcal{B}\}\). In this paper, the existence spectrum of self-converse \(MTS(v)\) is given, which is \(v \equiv 0\) or \(1 \pmod{3}\) and \(v \neq 6\).

In this paper, we discuss the automorphism groups of circulant digraphs. Our main purpose is to determine the full automorphism groups of circulant digraphs of degree \(3\).

The spectrum for the decomposition of \(\lambda K_v\) into \(3\)-perfect \(9\)-cycles is found for all \(\lambda > 1\). (The case \(\lambda = 1\) was dealt with in an earlier paper by the authors and Lindner.) The necessary conditions for the existence of a suitable decomposition turn out to be sufficient.

A directed triple system of order \(v\), denoted by \(DTS(v)\), is called \((f,k)\)-rotational if it has an automorphism consisting of \(f\) fixed points and \(k\) cycles each of length \((v-f)/k\). In this paper, we obtain a necessary and sufficient condition for the existence of \((f,k)\)-rotational \(DTS(v)\) for any arbitrary positive integer \(k\).

Let \( {R} = (r_1, r_2, \ldots, r_m)\) and \( {S} = (s_1, s_2, \ldots, s_n)\) be nonnegative integral vectors. Denote by \( {A}( {R}, {S})\) the class of \((0,1)\) matrices with row sum vector \( {R}\) and column sum vector \( {S}\). We study a generalization of invariant positions called locally invariant positions of a class \( {A}( {R}, {S})\). For a normalized class, locally invariant positions have in common with invariant positions the property that they lie above and to the left of some simple rook path through the set of positions.

This paper examines the numbers of lattice paths of length \(n\) from the origin to integer points along the line \((a,b,c,d) + t(1,-1,1,-1)\). These numbers form a sequence which this paper shows is log concave, and for sufficiently large values of \(n\), the location of the maximum of this sequence is shown. This paper also shows unimodality of such sequences for other lines provided that \(n\) is sufficiently large.

A cover of a finite set \(N\) is a collection of subsets of \(N\) whose union is \(N\). We determine the number of such covers whose blocks all have distinct sizes. The cases of unordered and ordered blocks are each considered.

Let \(n(k)\) be the smallest number of vertices of a bipartite graph not being \(k\)-choosable. We show that \(n(3) = 14\) and moreover that \(n(k) \leq k. n(k-2)+2^k\). In particular, it follows that \(n(4) \leq 40\) and \(n(6) \leq 304\).

Eight new codes are presented which improve the bounds on maximum minimum distance for binary linear codes. They are rate \(\frac{m-r}{pm},r\geq 1\) , \(r\)-degenerate quasi-cyclic codes.

A method for synthesizing combinatorial structures which are members of an extended class of resolvable incomplete lattice designs is presented. Square and rectangular lattices both are realizable, yet designs in the extended class are not limited in number of treatments by the classically severe restriction \(v = s^2\) or \(v = s(s-1)\). Rather, the current restriction is the condition that there exist a finite closable set of \(k\)-permutations on the objects of some group or finite field, which is then used as the generating array for a \(L(0,1)\) lattice design. A connection to Hadamard matrices \(H(p,p)\) is considered.

Near-perfect protection is a useful extension of perfect protection which is a necessary condition for authentication systems that satisfy Pei-Rosenbaum’s bound. Near-perfect protection implies perfect protection for key strategies, defined in the paper, in which the enemy tries to guess the correct key. We prove a bound on the probability of deception for key strategies, characterize codes that satisfy the bound with equality and conclude the paper with a comparison of this bound and Pei-Rosenbaum’s bound.

This note gives what is believed to be the first published example of a symmetric \(11 \times 11\) Latin square which, although not cyclic, has the property that the permutation between any two rows is an \(11\)-cycle. The square has the further property that two subsets of its rows constitute \(5 \times 11\) Youden squares. The note shows how this \(11 \times 11\) Latin square can be obtained by a general construction for \(n \times n\) Latin squares where \(n\) is prime with \(n \geq 11\). The permutation between any two rows of any Latin square obtained by the general construction is an \(n\)-cycle; two subsets of \((n-1)/2\) rows from the Latin square constitute Youden squares if \(n \equiv 3 \pmod{8}\).

The twenty-five year old \(\lambda\)-design conjecture remains unsettled. Attempts to characterize these irregular, tight, \(2\)-designs have produced a great number of parametric and dual structure characterizations of the so-called Type-I Designs. We establish some new structural characterizations and establish the conjecture in the smallest unsettled case (\(\lambda = 14\)) of the \(2p\) family.

In this paper we consider a random walk in a plane in which a particle at any stage moves one unit in any one of the four directions, namely, north, south, east, and west with equal probability and derive the joint and marginal distributions of certain characteristics of this random walk by using combinatorial methods.

A subset \(S\) of an ordered set \(P\) is called a cutset if each maximal chain of \(P\) has nonempty intersection with \(S\); if, in addition, \(S\) is also an antichain, it is an antichain cutset. We consider new characterizations and generalizations of these and related concepts. The main generalization is to make our definitions in graph theoretic terms. For instance, a cutset is a subset \(S\) of the vertex set \(V\) of graph \(G = (V, E)\) which meets each extremal path of \(G\). Our principal results include (1)a characterization, by means of a closure property, of those antichains which are cutsets;(2) a characterization, by means of “forbidden paths” in the graph, of those graphs which can be expressed as the union of antichain cutsets;(3) a simpler proof of an existing result about \(N\)-free orders; and (4) efficient algorithms for many related problems, such as constructing antichain cutsets containing or excluding specified elements or forming a chain.

We include a brief discussion of the use of antichain cutsets in a parsing problem for \(LR(k)\) languages.

The \(n\)-star graph \(S_n\) is a simple graph whose vertex set is the set of all \(n!\) permutations of \(\{1,2,\ldots,n\}\) and two vertices \(\alpha\) and \(\beta\) are adjacent if and only if \(\alpha(1) \neq \beta(1)\) and \(\alpha(i) \neq \beta(i)\) for exactly one \(i\), \(i \neq 1\). In the paper, we determine the values of the domination number \(\gamma\), the independent domination number \(\gamma_i\), the perfect domination number \(\gamma_p\), and we obtain bounds for the total domination number \(\gamma_t\) and the connected domination number \(\gamma_c\) for \(S_n\).

Holey factorizations of \(K_{v_1,v_2,\ldots,v_n}\) are a basic building block in the construction of Room frames. In this paper we give some necessary conditions for the existence of holey factorizations and give a complete enumeration for nonisomorphic sets of orthogonal holey factorizations of several special types.

It is shown that the maximal number of pairwise edge disjoint forests, \(F\), of order six in the complete graph \(K_n\), and the minimum number of forests of order six, whose union is \(K_n\) are \(\lfloor\frac{n(n-1)}{2e(F)}\rfloor\) and \(\lceil\frac{n(n-1)}{2e(F)}\rceil\), \(n\geq 6\), respectively and \(e(F)\) is the number of edges of \(F\). (\(\lfloor x\rfloor\) denotes the largest integer not exceeding \(x\) and \(\lceil x\rceil\) the least integer not less than \(x\)). Some generalizations to multiple copies of these forests and of paths are also given.

We study four \(q\)-series. Each of which is interpreted combinatorially in three different ways. This results in four new classes of infinite \(3\)-way partition identities. In some particular cases we get even \(4\)-way partition identities. Our every \(3\)-way identity gives us three Roderick-Ramanujan type identities and \(4\)-way identity gives six. Several partition identities due to Gordon \((1965)\), Hirschhorn \((1979)\), Subbarao \((1985)\), Blecksmith et al. \((1985)\), Agarwal \((1988)\) and Subbarao and Agarwal (1988) are obtained as particular cases of our general theorems.

Motivated by the spectral radius of a graph, we introduce the notion of numerical radius for multigraphs and directed multigraphs, and it is proved that, unlike the spectral radius, the numerical radius is invariant under changes in the orientation of a directed multigraph. An analogue of the Perron-Frobenius theorem is given for the numerical radius of a matrix with nonnegative entries.

We consider the polytope \(\mathcal{P}(s)\) of generalized tournament matrices with score vector \(s\). For the case that \(s\) has integer entries, we find the extreme points of \(\mathcal{P}(s)\) and discuss the graph-theoretic structure of its \(1\)-skeleton.

Our purpose is to determine the minimum integer \(f_i(m)\) (\(g_i(m)\), \(h_i(m)\) respectively) for every natural \(m\), such that every digraph \(D\), \(f_i(m)\)-connected, (\(g_i(m)\), \(h_i(m)\)-connected respectively) and \(\alpha^i(D) \leq m\) is hamiltonian (D has a hamilton path, D is hamilton connected respectively), (\(i = 0,1, 2\)). We give exact values of \(f_i(m)\) and \(g_i(m)\) for some particular values of \(m\). We show the existence of \(h_2(m)\) and that \(h_2(1) = 1\), \(h_2(2) = 4\) hold.

A two-valued function \(f\) defined on the vertices of a graph \(G = (V,E)\), \(f: V \to \{-1,1\}\), is a signed dominating function if the sum of its function values over any closed neighborhoods is at least one. That is, for every \(v \in V\), \(f(N[v]) \geq 1\), where \(N[v]\) consists of \(v\) and every vertex adjacent to \(v\). The function \(f\) is a majority dominating function if for at least half the vertices \(v \in V\), \(f(N[v]) \geq 1\). The weight of a signed (majority) dominating function is \(f(V) = \sum f(v)\). The signed (majority) domination number of a graph \(G\), denoted \(\gamma_s(G)\) (\(\gamma_{\text{maj}}(G)\), respectively), equals the minimum weight of a signed (majority, respectively) dominating function of \(G\). In this paper, we establish an upper bound on \(\gamma_s(G)\) and a lower bound on \(\gamma_{\text{maj}}(G)\) for regular graphs \(G\).

A pseudosurface is obtained from a collection of closed surfaces by identifying some points. It is shown that a pseudosurface \(S\) is minor-closed if and only if \(S\) consists of a pseudosurface \(S^\circ \), having at most one singular point, and some spheres glued to \(S^\circ\) in a tree structure.

Let \(\operatorname{PW}(G)\) and \(\operatorname{TW}(G)\) denote the path-width and tree-width of a graph \(G\), respectively. Let \(G+H\) denote the join of two graphs \(G\) and \(H\). We show in this paper that

\(\operatorname{PW}(G + H) = \min\{|V(G)| + \operatorname{PW}(H),|V(H)| + \operatorname{PW}(G)\}\)

and

\(\operatorname{TW}(G + H) = \min\{|V(G)| + \operatorname{TW}(H), |V(H)| + \operatorname{TW}(G)\}\).

For a positive integer \(k\), a \(k\)-subdominating function of \(G = (V, E)\) is a function \(f: V \to \{-1, 1\}\) such that the sum of the function values, taken over closed neighborhoods of vertices, is at least one for at least \(k\) vertices of \(G\). The sum of the function values taken over all vertices is called the aggregate of \(f\) and the minimum aggregate amongst all \(k\)-subdominating functions of \(G\) is the \(k\)-subdomination number \(\gamma_{ks}(G)\). In the special cases where \(k = |V|\) and \(k = \lceil|V|/2\rceil\), \(\gamma_{ks}\) is respectively the signed domination number [{4}] and the majority domination number [{2}]. In this paper we characterize minimal \(k\)-subdominating functions. By determining \(\gamma_{ks}\) for paths, we give a sharp lower bound for \(\gamma_{ks}\) for trees. We also determine an upper bound for \(\gamma_{ks}\) for trees which is sharp for \(k \leq |V|/2 \).

Let \(G\) be a connected (multi)graph. We define the leaf-exchange spanning tree graph \( {T_l}\) of \(G\) as the graph with vertex set \(V_l = \{T|T \text{ is a spanning tree of } G\}\) and edge set \(E_l = \{(T, T’)|E(T)\Delta E(T’) = \{e, f\}, e \in E(T), f \in E(T’) \text{ and } e \text{ and } f \text{ are incident with a vertex } v \text{ of degree } 1 \text{ in } T \text{ and } T’\}\). \({T}(G)\) is a spanning subgraph of the so-called spanning tree graph of \(G\), and of the adjacency spanning tree graph of \(G\), which were studied by several authors. A variation on the leaf-exchange spanning tree graph appeared in recent work on basis graphs of branching greedoids. We characterize the graphs which have a connected leaf-exchange spanning tree graph and give a lower bound on the connectivity of \( {T_l}(G)\) for a \(3\)-connected graph \(G\).

The fine structure of a directed triple system of index \(\lambda\) is the vector \((c_1,c_2,\ldots,c_\lambda)\), where \(c_i\) is the number of directed triples appearing precisely \(i\) times in the system. We determine necessary and sufficient conditions for a vector to be the fine structure of a directed triple system of index \(3\) for \(v \equiv 0\) or \(1 \pmod{3}\).

Let \(p\) denote the circumference of a two-connected graph \(G\). We construct a hamiltonian cycle in \(G^2\) which contains more than \(p/2\) edges of \(G\). Using this construction we prove some properties of hamiltonian cycles in the square of \(G\).

For a connected graph \(G\) that is not a cycle, a path or a claw, let its \(k\)-iterated line graph have the diameter \(diam_k\), and the radius \(r_k\). Then \(diam_{k+1} = diam_k + 1\) for sufficiently large \(k\). Moreover, \(\{r_k\}\) also tends to infinity and the sequence \(\{diam_k – r_k – \sqrt{2\log_2 k}\}\) is bounded.

In \([1]\) it is proved that each \(4\)-critical plane graph contains either a \(4\)- or a \(5\)-cycle or otherwise a face of size between \(6\) and \(11\).

For nonempty graphs \(G\) and \(H\), \(H\) is said to be \(G\)-decomposable (written \(G|H\)) if \(E(H)\) can be partitioned into sets \(E_1, \ldots, E_n\) such that the subgraph induced by each \(E_i\) is isomorphic to \(G\). If \(H\) is a graph of minimum size such that \(F|H\) and \(G|H\), then \(H\) is called a least common multiple of \(F\) and \(G\). The size of such a least common multiple is denoted by \(\mathrm{lcm}(F,G)\). We show that if \(F\) and \(G\) are bipartite, then \(\mathrm{lcm}(F,G) \leq |V(F)|\cdot|V(G)|\), where equality holds if \((|V(F)|,|V(G)|) = 1\). We also determine \(\mathrm{lcm}(F,G)\) exactly if \(F\) and \(G\) are cycles or if \(F = P_m, G = K_n\), where \(n\) is odd and \((m-1,\frac{1}{2}(n-1)) = 1\), in the latter case extending a result in [{8}].

Let \(G\) be a graph. A vertex subversion strategy of \(G\), \(S\), is a set of vertices in \(G\) whose closed neighborhood is deleted from \(G\). The survival-subgraph is denoted by \(G/S\). The vertex-neighbor-integrity of \(G\), \(\mathrm{VNI}(G)\), is defined to be \(\mathrm{VNI}(G) = \displaystyle\min_{S\subseteq V(G)} \{|S| + w(G/S)\}\), where \(S\) is any vertex subversion strategy of \(G\), and \(w(G/S)\) is the maximum order of the components of \(G/S\). In this paper, we show the minimum and the maximum vertex-neighbor-integrity among all trees with any fixed order, and also show that for any integer \(l\) between the extreme values there is a tree with the vertex-neighbor-integrity \(l\).

Let \(G\) be a graph of size \(\binom{n+1}{2}\) for some integer \(n \geq 2\). Then \(G\) is said to have an ascending star subgraph decomposition if \(G\) can be decomposed into \(n\) subgraphs \(G_1, G_2, \ldots, G_n\) such that each \(G_i\) is a star of size \(i\) with \(1 \leq i \leq n\). We shall prove in this paper that a star forest with size \(\binom{n+1}{2}\) possesses an ascending star subgraph decomposition under some conditions on the number of components or the size of components.

Let \(G\) and \(H\) be connected graphs and let \(G \square H\) be the Cartesian product of \(G\) by \(H\). A lower and an upper bound for the independence number of the Cartesian product of graphs is proved for the case, where one of the factors is bipartite. Cartesian products with one factor being an odd path or an odd cycle are considered as well.

It is proved in particular that if \(S_1 + S_2\) is a largest 2-independent set of a graph \(G\), such that \(|S_2|\) is as small as possible and if \(|S_2| \leq n+2\), then \(\alpha(G \square P_{2n+1}) = (n+1)|S_1| + n|S_2|\). A similar result is shown for the Cartesian product with an odd cycle. It is finally proved that \(\alpha(C_{2k+1} \square C_{2n+1}) = k(2n+1)\), extending a result of Jha and Slutzki.

Parallel processing has been a valuable tool for improving the performance of many algorithms. Solving intractable problems is an attractive application of parallel processing. Traditionally, exhaustive search techniques have been used to find solutions to \(NP\)-complete problems. However, the performance benefit of parallelization of exhaustive search algorithms can only provide linear speedup, which is typically of little use as problem complexity increases exponentially with problem size. Genetic algorithms can be useful tools to provide satisfactory results to such problems. This paper presents a genetic algorithm that uses parallel processing in a cooperative fashion to determine mappings for the rectilinear crossing problem. Results from this genetic algorithm are presented which contradict a conjecture that has been open for over 20 years regarding the minimal crossing number for rectilinear graphs.

A balanced tournament design, \(\mathrm{BTD}(n)\), defined on a \(2n\)-set \(V\), is an arrangement of the \(\binom{2n}{2}\) distinct unordered pairs of the elements of \(V\) into an \(n \times 2n-1\) array such that:
(1) every element of \(V\) is contained in precisely one cell of each column, and
(2) every element of \(V\) is contained in at most two cells of each row.

If we can partition the columns of a \(\mathrm{BTD}(n)\) defined on \(V\) into three sets \(C_1, C_2, C_3\) of sizes \(1, n-1, n-1\) respectively such that the columns in \(C_1 \cup C_2\) form a Howell design of side \(m\) and order \(2n\), an \(\mathrm{H}(n,2n)\), and the columns in \(C_1 \cup C_3\) form an \(\mathrm{H}(n,2n)\), then the \(\mathrm{BTD}(n)\) is called partitionable. We denote a partitioned balanced tournament design of side \(n\) by \(\mathrm{PBTD}(n)\). The existence of these designs has been determined except for seven possible exceptions. In this note, we describe constructions for four of these designs. This completes the spectrum of \(\mathrm{PBTD}(n)\) for \(n\) even.

In this note we complete the table of Ramsey numbers for \(K_s\) versus the family of all \((p,q)\)-graphs for \(p \leq 8\).
Moreover, some results are obtained for the general case.

Let \(G\) be a \(2\)-connected graph of order \(n\) with connectivity \(\kappa\) and independence number \(\alpha\). In this paper, we show that if for each independent set \(S\) with \(|S| = k+1\), there are \(u,v \in S\) such that satisfying one of the following conditions:

1. \(d(u) + d(v) \geq n\); or \(|N(u) \cap N(v)| \geq \alpha\); or \(|N(u) \cup N(v)| \geq n-k\);
2. for any \(x \in \{u,v\}\), \(y \in V(G)\) and \(d(x,y) = 2\), it implies that \(\max\{d(x), d(y)\} \geq n/2\),

then \(G\) is hamiltonian. This result reveals the internal relations among several well-known sufficient conditions: \((1)\) it shows that it does not need to consider all pairs of nonadjacent or distance two vertices in \(G\); \((2)\) it makes known that for different pairs of vertices in \(G\), it permits to satisfy different conditions.

Let \(G\) be a graph of order \(p\) such that both \(G\) and \(\overline{G}\) have no isolated vertices. Let \(\Upsilon_t\) and \(\overline{\Upsilon}_t\) denote respectively the total domination number of \(G\) and \(\overline{G}\). In this paper we obtain a characterization of all graphs \(G\) for which \\(i) \(\Upsilon_t +\overline{\Upsilon}_t= p+1\) and (ii) \(\Upsilon_t + \overline{\Upsilon}_t = p\).

The bondage number \(b(G)\) of a nonempty graph \(G\) was first introduced by Fink, Jacobson, Kinch, and Roberts [3]. In their paper they conjectured that \(b(G) \leq \Delta(G)+1\) for a nonempty graph \(G\). A counterexample for this conjecture was shown in [5]. Beyond it, we show now that there doesn’t exist an upper bound of the following form: \(b(G) \leq \Delta(G)+c\) for any \(c\in\mathbb{N}\).

It is shown that if \(t > 1\) and \(u \geq 5\), then the known necessary condition for the existence of a skew Room frame of type \(t^u\), is also sufficient with the possible exception of \((u, f)\) where \(u = 5\) and \(t \in \{11, 13, 17, 19, 23, 29, 31, 41, 43\}\).

The class of \(t-sc\) graphs constitutes a new generalization of self-complementary graphs. Many \(t-sc\) graphs exhibit a stable complementing permutation. In this paper, we prove a sufficient condition for the existence of a stable complementing permutation in a \(t-sc\) graph. We also construct several infinite classes of \(t-sc\) graphs to show the stringency of our sufficient condition.

A polyhex graph is either a hexagonal system or a coronoid system. A polyhex graph \(G\) is said to be \(k\)-coverable if for any \(k\) mutually disjoint hexagons the subgraph obtained from \(G\) by deleting all these \(k\) hexagons together with their incident edges has at least one perfect matching. In this paper, a constructive criterion is given to determine whether or not a given polyhex graph is \(k\)-coverable. Furthermore, a simple method is developed which allows us to determine whether or not there exists a \(k\)-coverable polyhex graph with exactly \(h\) hexagons.

A \((k, \lambda)\)-semiframe of type \(g^u\) is a group divisible design of type \(g^u\) \((\chi, \mathcal{G}, \mathcal{B})\), in which \(\mathcal{B}\) is written as a disjoint union \(\mathcal{B} = \mathcal{P} \cup \mathcal{Q} \) where \(\mathcal{P} \) is partitioned into partial parallel classes of \(\chi\) (with respect to some \(G \in \mathcal{G}\)) and \(\mathcal{Q} \) is partitioned into parallel classes of \(\chi\). In this paper, new constructions for these designs are provided with some series of designs with \(k = 3\). Cyclic semiframes are discussed. Finally, an application of semiframes is also mentioned.

A solution of Dudeney’s round table problem is given when \(n\) is as follows:

1. \(n = pq + 1\), where \(p\) and \(q\) are odd primes.
2. \(n = p^e + 1\), where \(p\) is an odd prime.
3. \(n = p^e q^f + 1\), where \(p\) and \(q\) are distinct odd primes satisfying \(p \geq 5\) and \(q \geq 11\), and \(e\) and \(f\) are natural numbers.

An upper bound on the size of any collection of mutually orthogonal partial Latin squares is derived as a function of the number of compatible cells that are occupied in all squares. It is shown that the bound is strict if the number of compatible cells is small.

The quantity \(B(G) = \min \max\{|f(u)-f(v)|: (u,v) \in E(G)\}\) is called the bandwidth of a graph \(G = (V(G), E(G))\) where \(\min\) is taken over all bijections \(f: V(G) \to \{1,2,\ldots,|V(G)|\}\) called labelings. L.H. Harper presented an important inequality related to the boundary of subsets \(S \subseteq V(G)\). This paper gives a refinement of Harper’s inequality which will be more powerful in determining bandwidths for several classes of graphs.

In this paper we consider the problem of constructing magic rectangles of size \(m \times n\) where \(m\) and \(n\) are nonprime integers. What seems to be two new methods of constructing such rectangles are given.

The point-distinguishing chromatic index \(\chi_o(G)\) of a graph \(G\) represents the minimum number of colours in an edge colouring of \(G\) such that each vertex of \(G\) is distinguished by the set of colours of its incident edges. It is known that \(\chi_o(K_{n,n})\) is a non-decreasing function of \(n\) with jumps of value \(1\). We prove that \(\chi_o(K_{46,46}) = 7\) and \(\chi_o(K_{47,47}) = 8\).

There have been many results concerning claw-free graphs and hamiltonicity. Recently, Jackson and Wormald have obtained more general results on walks in claw-free graphs. In this paper, we consider the family of almost claw-free graphs that contains the previous one, and give some results on walks, especially on shortest covering walks visiting only once some given vertices.

A \(t\)-(n, k, \(\lambda\)) covering design consists of a collection of \(k\)-element subsets (blocks) of an \(n\)-element set \(\chi\) such that each \(t\)-element subset of \(\chi\) occurs in at least \(\lambda\) blocks. We use probabilistic techniques to obtain a general upper bound for the minimum size of such designs, extending a result of Erdős and Spencer [4].

In this paper, difference sets in groups containing subgroups of index \(2\) are considered, especially groups of order \(2m\) where \(m\) is odd. The author shows that the only difference sets in groups of order \(2p^\alpha\) are trivial. The same conclusion is true for some special parameters.

We completely classify the graphs all of whose neighbourhoods of vertices are isomorphic to \(P^k_n\) (\(2 \leq k \leq n\)), where \(P^k_n\) is the \(k\)-th power of the path \(P_n\) of length \(n-1\).

Let \(G\) be a finite group and let \(p_i(G)\) denote the proportion of \((x,y) \in G^2\) for which the set \(\{x^2, xy, yx, y^2\}\) has cardinality \(i\). We show that either \(0 < p_1(G) + p_2(G) \leq \frac{1}{2}\) or \(p_1(G) + p_2(G) = 1\), and that either \(p_4(G) = 0\) or \(\frac{5}{32} \leq p_4(G) < 1\). Each of the preceding inequalities are the best possible.

Using linear algebra over \(\text{GF}(2)\) we supply simple proofs to three parity theorems: Gallai’s partition theorem, the odd-parity cover theorem of Sutner, and generalize the “odd-cycle property” theorem of Manber and Shao to binary matroids.

Let \(F\) and \(F’\) be two forests sharing the same vertex set \(V\) such that \(|E(F) \cap E(F’)| = \theta\). By \(F \cup F’\) we denote the graph on \(V\) with edge set \(E(F) \cup E(F’)\). Since both \(F\) and \(F’\) are \(2\)-colorable, we have \(\chi(F \cup F’) \leq 4\). In this paper we will investigate forests for which we can actually obtain this upper bound for the chromatic number. It will turn out that if neither \(F\) nor \(F’\) contain a path of length three then the chromatic number of \(F \cup F’\) is at most three. We will characterize those pairs of forests \(F\) and \(F’\) which both contain a path of length three and for which the chromatic number of \(F \cup F’\) is always at most three. In the case where one of the forests contains a path of length three and the other does not contain a path of length three we obtained only partial results. The problem then seems to be similar to a problem of Erdős which recently has been solved by Fleischner [2] using a theorem of Alon [3].

With Burnside’s lemma as the main tool, we derive a formula for the number of oriented triangle graphs and for the number of such graphs in which all largest cliques are transitively oriented.

This paper deals with \((a, d)\)-antimagic labelings of special graphs called parachutes. After the introduction of the concept of a parachute, the authors succeed in proving the finiteness of two very interesting subsets of the set of all \((a, d)\)-antimagic parachutes by means of a method using the theory of Diophantine equations and other number-theoretical results.

A rooted graph is a pair \((G, x)\), where \(G\) is a simple undirected graph and \(x \in V(G)\). If \(G\) is rooted at \(x\), its \(k\)-th rotation number \(h_k(G, x)\) is the minimum number of edges in a graph \(F\) of order \(|G| + k\) such that for every \(v \in V(F)\) we can find a copy of \(G\) in \(F\) with the root vertex \(x\) at \(v\); any such \(F\) of size \(h_k(G, x)\) is called a minimal graph. In this paper we prove that if \((G, x)\) is a rooted graph with \(d_{G}(x) = d\) then

\[p(G, x)=\lim_{k \to \infty} \frac{h_k(G, x)}{k} \]

exists and satisfies \(d/2 \leq p(G, x) \leq d\), where \(p(G, x)\) is termed the rotation index of \((G, x)\). We obtain the precise value of this parameter for several classes of rooted graphs and describe the asymptotic behaviour of corresponding minimal graphs.

A \(t\)-interval representation \(f\) of a graph \(G\) is a function which assigns to each vertex \(v \in V(G)\) a union of at most \(t\) closed intervals \(I_{v,1}, I_{v,2}, \ldots, I_{v,t}\) on the real line such that \(f(v) \cap f(w) \neq \emptyset\) if and only if \(v, w \in V(G)\) are adjacent. If no real number lies in more than \(r\) intervals of the representation, we say the interval representation has depth \(r\). The least positive integer \(t\) for which there exists a \(t\)-representation of depth \(r\) of \(G\) is called the depth-\(r\) interval number \(i_r(G)\). E. R. Scheinerman proved that \(i_2(K_n) = \lceil \frac{n}{2} \rceil\) for \(n \geq 2\) and that \(\lceil \frac{n-1}{2(r-1)}+\frac{r}{2n} \rceil \leq i_r(K_n) \leq \frac{n}{2r-2}+1+2\lceil log_r n \rceil \). In the following paper, we will see by construction that \(i_3(K_n) = \lceil \frac{n-1}{4}+\frac{3}{2n} \rceil \). If \(n \geq 5\), this is equal to \(\lceil \frac{n}{4} \rceil\). The main theorem is: if \(n \geq r \geq 4\), then \(i_r(K_n) \leq \max \{ \lceil \frac{n-2}{2(r-1)}+\frac{1}{2} \rceil , 2 \}\). The difference between the lower and upper bounds is at most \(1\).

Let \(L\) be a linear form on the Galois field \(\text{GF}(q^{n+1})\) over \(\text{GF}(q)\) (\(n \geq 2\)). We characterize those integers \(s\) coprime to \(v = (q^{n+1}-1)/(q-1)\) such that \(L(x^s)\) is (or is related to) a quadratic form on \(\text{GF}(q^{n+1})\) over \(\text{GF}(q)\). This relates to a conjecture of Games concerning quadrics of the form \(rD\) in \(\text{PG}(n,q)\), where \(D\) is a difference set in the cyclic group \({Z}_v\), acting as a Singer group on the points and hyperplanes of \(\text{PG}(n,q)\). It has been shown that Games’ conjecture does not hold except possibly in the case \(q = 2\): here we establish that it holds exactly when \(q = 2\). We also suggest a new conjecture. Our result for \(q=2\) enables us to prove another conjecture of Games’, concerning \(m\)-sequences with three-valued periodic cross-correlation function.

Let \(G\) be a group acting on a set \(\Omega\). A subset (finite or infinite) \(A \subseteq \Omega\) is called \(k\)-quasi-invariant, where \(k\) is a non-negative integer, if \(|A^g \backslash A| \leq k\) for every \(g \in G\). In previous work of the authors a bound was obtained, in terms of \(k\), on the size of the symmetric difference between a \(k\)-quasi-invariant subset and the \(G\)-invariant subset of \(\Omega\) closest to it. However, apart from the cases \(k = 0, 1\), this bound gave little information about the structure of a \(k\)-quasi-invariant subset. In this paper a classification of \(2\)-quasi-invariant subsets is given. Besides the generic examples (subsets of \(\Omega\) which have a symmetric difference of size at most \(2\) with some \(G\)-invariant subset) there are basically five explicitly determined possibilities.

This note is an extension of \([4]\) , wherein is shown a relation between the dual notions of graceful and edge-graceful graphs. In particular, this note proves two graceful conjectures raised in \([4]\) , and then utilizes the result to edge-gracefully label certain trees not previously known to be edge-graceful.

We present sufficient conditions for the existence of a \(k\)-factor in a simple graph depending on \(\sigma_2(G)\) and the neighbourhood of independent sets in our first theorem and on \(\sigma_2(G)\) and \(\alpha(G)\) in the second one.

It is well known that a necessary condition for the existence of a \((v, 4, 1)\)-RPMD is \(v \equiv 0 \text{ or } 1 \pmod{4}\) and the existence of \((v, 4, 1)\)-RPMDs for \(v \equiv 1 \pmod{4}\) has been completely settled.
In this paper, we shall introduce the concept of \((v, k, 1)\)-nearly-RPMDs and use it to obtain some new construction methods for \((v, k, 1)\)-RPMDs with \(v \equiv 0 \pmod{k}\). As an application, we shall show that a \((v, 4, 1)\)-RPMD exists for all integers \(v \geq 4\) where \(v \equiv 0 \pmod{4}\), except for \(v = 4, 8\) and with at most \(49\) possible exceptions of which the largest is \(336\).
It is also well known that a \((v, k, 1)\)-RPMD exists for all sufficiently large \(v\) with \(k \geq 3\) and \(v \equiv 1 \pmod{k}\), and a \((v, k, 1)\)-PMD exists with \(v(v – 1) \equiv 0 \pmod{k}\) for the case when \(k\) is an odd prime and \(v\) is sufficiently large. In this paper, we shall show that there exists a \((v, k, 1)\)-RPMD for all sufficiently large \(v\) with \(v \equiv 0 \pmod{k}\), and there exists a \((v, k,\lambda)\)-PMD for all sufficiently large \(v\) with \(\lambda v(v – 1) \equiv 0 \pmod{k}\).

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.

New sufficient conditions for equality of edge-connectivity and minimum degree of graphs are presented, including those of Chartrand, Lesniak, Plesnik, Plesník, and Ždmán, and Volkmann.