In this paper, we investigate the total colorings of the join graph \(G_1 + G_2\) where \(G_1 \cup G_2\) is a graph with maximum degree at most \(2\). As a consequence of the main result, we prove that if \(G = (2l+1)C_m + (2l+1)C_n\), then \(G\) is Type 2 if and only if \(m = n\) and \(n\) is odd, where \((2l+1)C_m\) and \((2l+1)C_n\) represent \((2l+1)\) disjoint copies of \(C_m\) and \(C_n\), respectively.

In this paper, the standard basis for trades is used to develop an algorithm to classify all simple 2-(8,3) trades. The existence of a total number of 15,011 trades reveals the rich structure of trades in spite of a small number of points. Some results on simple 2-(9, 3) trades are also obtained.

We describe an algorithm for finding smallest defining sets of designs. Using this algorithm, we show that the 104 \(STS(19)\) which have automorphism group order at least 9 have smallest defining set sizes in the range 18-23. The numbers of designs with smallest defining sets of 18, 19, 20, 21, 22 and 23 blocks are, respectively, 1, 2, 17, 68, 14 and 2.

In this paper, three simple algorithms for the satisfiability problem are presented with their probabilistic analyses. One algorithm, called counting, is designed to enumerate all the solutions of an instance of satisfiability. The second one, namely E-SAT, is proposed for solving the corresponding decision problem. Both the enumeration and decision algorithms have a linear space complexity and a polynomial average time performance for a specified class of instances. The third algorithm is a randomized variant of E-SAT. Its probabilistic analysis yields a polynomial average time performance.

For any abelian group A, we call a graph G = (V, E) as A-magic if there exists a labeling I: E(G) \(\to \text{A} – \{0\}\) such that the induced vertex set labeling \(I^+: V(G) \to A\)
\[\text{I}^+\text{(v)} = \Sigma \{ \text{I(u,v) : (u,v) in E(G)} \}\]
is a constant map. We denote the set of all A such that G is A-magic by AM(G) and call it as group-magic index set of G.

Let \((\mathcal{P}, \mathcal{B}, \mathcal{I})\) be an asymmetric \((v, k, \lambda)\) block design. The incidence graph \(G\) of this design is distance-regular, hence belongs to an association scheme. In this paper, we use the algebraic structure of this association scheme to analyse certain symmetric partitions of the incidence structure.

A set with two intersection numbers is a subset \(\mathcal{K} \subseteq \mathcal{P}\) with the property that \(|{B} \cap \mathcal{K}|\) takes on only two values as ${B}$ ranges over the blocks of the design. In the special case where the design is a projective plane, these objects have received considerable attention. Two intersection theorems are proven regarding sets of this type which have a certain type of dual. Applications to the study of substructures in finite projective spaces of dimensions two and three are discussed.

In this paper, necessary and sufficient conditions for the existence of a 5-cycle system of the \(\lambda\)-fold complete graph of order \(v\) with a hole of size \(u\),\(\lambda(K_v – K_u)\), are proved.

Let \(G\) be a simple connected graph on \(2n\) vertices with a perfect matching. For a positive integer \(k\), \(1 \leq k \leq n – 1\), \(G\) is \(k\)-\emph{extendable} if for every matching \(M\) of size \(k\) in \(G\), there is a perfect matching in \(G\) containing all the edges of \(M\). For an integer \(k\), \(0 \leq k \leq n – 2\), \(G\) is \emph{strongly \(k\)-extendable} if \(G\) – \(\{u, v\}\) is \(k\)-extendable for every pair of vertices \(u\) and \(v\) of \(G\). The problem that arises is that of characterizing \(k\)-extendable graphs and strongly \(k\)-extendable graphs. The first of these problems has been considered by several authors whilst the latter has only been recently studied by the author. In a recent paper, we established a number of properties of strongly \(k\)-extendable graphs including some sufficient conditions for strongly \(k\)-extendable graphs. In this paper, we focus on a necessary condition, in terms of minimum degree, for strongly \(k\)-extendable graphs. Further, we determine the set of realizable values for minimum degree of strongly \(k\)-extendable graphs. A complete characterization of strongly \(k\)-extendable graphs on \(2n\) vertices for \(k = n – 2\) and \(n – 3\) is also established.

In this paper we discuss some designs that have been used to train mediators for dispute resolution and tabulate some small examples.

The spectrum \(Q(k,\lambda)\) of coset difference arrays has played an important role in Lu’s work on asymptotic existence of resolvable balanced incomplete block designs. In this article, we use Weil’s theorem on character sums to show that if \(k = 2\lambda + 1\), then for any prime power \(q \equiv 1+2k \pmod{4k}\), \(q \in Q(k,\lambda)\) whenever \(g > D(k) = (\frac{B+\sqrt{B^2+4C}}{2})^2\), where \(B = (k-2)k(2k-1)(2k)^{k-1} – (2k)^{k} + 1\) and \(C = \frac{(k-2)(k-1)}{2}(2k)^{k-1}\). In particular, we determine the spectrum \(Q(3,1)\). In addition, the degenerate case when \(k = \lambda + 1\) is also discussed.

The third author proved earlier [8] that if a Euclidean space is colored with red and blue so that the distance one is forbidden for blue, and translates of some \(k\)-point configuration are forbidden for red, then the unit-distance chromatic number of the space is no greater than \(k\). Here we give a generalization.

We continue the study of graphs defined by a certain adjacency property by investigating the $n$-existentially closed line-critical graphs. We classify the \(1\)-e.c. line-critical graphs and give examples of \(2\)-e.c. line-critical graphs for all orders \(\geq 9\).

An isometric path is merely any shortest path between two vertices. Inspired by the game of `Cops and Robber’ and a result by Aigner \(\&\) Fromme [1], we are interested in determining the minimum number of isometric paths required to cover the vertices of a graph. We find a lower bound on this number in terms of the diameter of a graph and find the exact number for trees and grid graphs.

An edge-graceful \((p, q)\)-graph \(G = (V, E)\) is a graph with \(p\) vertices and \(q\) edges for which there is a bijection \(f : E \to \{1,2,\ldots,q\}\) such that the induced mapping \(f^+ : V \to \mathbb{Z}_p\), defined by \(f^+(u) \equiv \sum\limits_{uv \in E} f(uv) \pmod{p}\), for \(u \in V\), is a bijection. In this paper, some results on edge-gracefulness of trees are extended to \(k\)-fold graphs based on graphs with \(p$ vertices and \(p – 1\) edges. A \(k\)-fold multigraph \(G[k]\) derived from a graph \(G\) is one in which each edge of \(G\) has been replaced by \(k\) parallel edges with the same vertices as the original edge. Certain classes of \(k\)-fold multigraphs derived from paths, combs, and spiders are shown to be edge-graceful, as well as other graphs constructed by combining these graphs in specified ways.

We determine solutions to the problem of gossiping in minimum time (briefly: minimum time problem or MTP) which require less calls than the previously known solutions for infinitely many values of the number \(n\) of persons and optimal solutions to the MTP, i.e. solutions of the MTP which minimize the number of calls, for some values of \(n\). We conjecture that our methods provide optimal solutions of the MTP for all \(n\).

Erdős and Gallai (1963) showed that any \(r\)-regular graph of order \(n\), with \(r < n-1\), has chromatic number at most \({3n}/{5}\), and this bound is achieved by precisely those graphs with complement equal to a disjoint union of 5-cycles.

We are able to generalize this result by considering the problem of determining a \((j-1)\)-regular graph \(G\) of minimum order \(f(j)\) such that the chromatic number of the complement of \(G\) exceeds \({f(j)}/{2}\). Such a graph will be called an \(F(j)\)-\emph{graph}. We produce an \(F(j)\)-graph for all odd integers \(j \geq 3\) and show that \(f(j) = {5(j – 1)}/{2}$ if \(j \equiv 3 \pmod{4}\), and \(f(j) = 1 + {5(j – 1)}/{2}\) if \(j \equiv 1 \pmod{4}\).

A lemma of Enomoto, Llado, Nakamigawa and Ringel gives an upper bound for the edge number of a super edge-magic graph with \(p > 1\) vertices. In this paper we give some results which come out from answering some natural questions suggested by this useful lemma.

The scheme associated with a graph is an association scheme if and only if the graph is strongly regular. Consider the problem of extending such an association scheme to a superscheme in the case of a colored, directed graph. The obstacles can be expressed in terms of \(t\)-vertex conditions. If a graph does not satisfy the \(t\)-vertex condition, a prescheme associated with it cannot be erected beyond the \((t-3)\)rd-level.

A mandatory representation design MRD \((K; v)\) is a pairwise balanced design PBD \((K; v)\) in which for each \(k \in K\) there is at least one block in the design of size \(k\). The study of the mandatory representation designs is closely related to that of subdesigns in pairwise balanced designs. In this paper, we survey the known results on MRDs and pose some open questions.

It is shown that the necessary conditions are sufficient for the existence of all \(c\)-BRDs\((v, 3, \lambda)\) for negative \(c\)-values. This completes the study of \(c\)-BRDs with block size three as previously the authors and J. Seberry have shown that the necessary conditions are sufficient for \(c \geq -1\).

Let \(G\) be a simple connected graph on \(2n\) vertices with a perfect matching. For a positive integer \(k\), \(1 \leq k \leq n-1\), \(G\) is \(k\)-\emph{extendable} if for every matching \(M\) of size \(k\) in \(G\), there is a perfect matching in \(G\) containing all the edges of \(M\). For an integer \(k\), \(0 \leq k \leq n – 2\), \(G\) is \emph{strongly \(k\)-extendable} if \(G – \{u, v\}\) is \(k\)-extendable for every pair of vertices \(u\) and \(v\) of \(G\). The problem that arises is that of characterizing \(k\)-extendable graphs and strongly \(k\)-extendable graphs. The first of these problems has been considered by several authors whilst the latter has been investigated only for the case \(k = 0\). In this paper, we focus on the problem of characterizing strongly \(k\)-extendable graphs for any \(k\). We present a number of properties of strongly \(k\)-extendable graphs including some necessary and sufficient conditions for strongly \(k\)-extendable graphs.

In this paper we count the number of non-homeomorphic continua in a certain collection of continua. The continua in these collections are trees with certain restrictions on them. We refer to a continuum in one of these collections as a caterpillar continuum.