A covering of the complete directed symmetric graph \(DK_v\) by \(m\)-circuits, denoted by \((v,m) – {DCC}\), is a family of \(m\)-circuits in \(DK_v\) whose union is \(DK_v\). The covering number \(C(v,m)\) is the minimum number of \(m\)-circuits in such a covering.

The covering problem is to determine the value \(C(v,m)\) for every integer \(v \geq m\). In this paper, the problem is reduced to the case \(m+5 \leq v \leq 2m – 4\), for any fixed even integer \(m \geq 4\).

In particular, the values of \(C(v,m)\) are completely determined for \(m = 12, 14,\) and \(16\). Additionally, a directed construction of optimal \((6k + 11, 4k + 6) – {DCC}\) is given.

It is shown that if \(H\) is a connected graph obtained from \(H_1\) and \(H_2\) by joining them with a bridge, then \(r(K_k, H) \leq r(K_k, H_1) + r(K_k, H_2) + k – 2\). We give some applications of this result.

Two closely related types of vertex subsets of a graph, namely external redundant sets and weak external redundant sets, together with associated parameters, are discussed. Both types may be used to characterize those irredundant subsets of a graph which are maximal.

Let \(G\) be a graph and let \(S\) be a subset of vertices of \(G\). A vertex \(v\) of \(G\) is called perfect with respect to \(S\) if \(|N[v] \cap S| = 1\), where \(N[v]\) denotes the closed neighborhood of \(v\). The set \(S\) is defined to be a perfect neighborhood set of \(G\) if every vertex of \(G\) is perfect or adjacent with a perfect vertex.

The perfect neighborhood number \(\theta(G)\) of \(G\) is defined to be the minimum cardinality among all perfect neighborhood sets of \(G\). In this paper, we present a variety of algorithmic results on the complexity of perfect neighborhood sets in graphs.

We consider the problem of sweeping (or grazing) the interior/exterior of a polygon by a flexible rope whose one endpoint (anchor) is attached on the boundary of the polygon. We present a linear-time algorithm to compute the grazing area inside a simple polygon. We show how to extend the algorithm for computing the internal grazing area, without increasing its time complexity, to compute the grazing area in the exterior of a simple polygon. For grazing in the exterior of a convex polygon, we present an \(O(n)\) time algorithm to locate the anchor point that maximizes the simple grazing area. All three algorithms are optimal within a constant factor. Grazing area problems can be viewed as guard placement problems under \(L\)-visibility.

Forming all distinct subsets with \(k\) or fewer objects from a set with \(n\) elements can be accomplished by generating a subset of the binary reflected Gray code. This paper presents a straightforward algorithm that generates the desired Gray codewords by altering the stack which maintains the transition sequence that determines the next codeword position to be altered.

A vertex of a graph \(G\) dominates itself and its neighbors. A set \(S\) of vertices of \(G\) is a dominating set if each vertex of \(G\) is dominated by some vertex of \(S\). The domination number \(\gamma(G)\) of \(G\) is the minimum cardinality of a dominating set of \(G\). A minimum dominating set is one of cardinality \(\gamma(G)\). A subset \(T\) of a minimum dominating set \(S\) is a forcing subset for \(S\) if \(S\) is the unique minimum dominating set containing \(T\). The forcing domination number \(f(S, \gamma)\) of \(S\) is the minimum cardinality among the forcing subsets of \(S\), and the forcing domination number \(f(G, \gamma)\) of \(G\) is the minimum forcing domination number among the minimum dominating sets of \(G\). For every graph \(G\), \(f(G, \gamma) \leq \gamma(G)\).

It is shown that for integers \(a, b\) with \(b\) positive and \(0 \leq a \leq b\), there exists a graph \(G\) such that \(f(G, \gamma) = a\) and \(\gamma(G) = b\). The forcing domination numbers of several classes of graphs are determined, including complete multipartite graphs, paths, cycles, ladders, and prisms. The forcing domination number of the cartesian product \(G\) of \(k\) copies of the cycle \(C_{2k+1}\) is studied. Viewing the graph \(G\) as a Cayley graph, we consider the algebraic aspects of minimum dominating sets in \(G\) and forcing subsets.

The complete stability \(cs(P_k)\), where \(P_k\) denotes the property of having a \(k\)-factor, satisfies \(cs(P_k) = n + k – 2, \text{ if } 1 \leq k \leq 3\), and \(n + k – 2 \leq cs(P_k) \leq n + k – 1, \text{ if } k \geq 4\). A similar result for bipartite graphs with complete biclosure is proved also.

It is known that in every 2-coloring of the edges of the complete graph there exist two vertex disjoint paths—one red, one blue—that collectively cover all the vertices. In this paper, analogous existence and efficiency questions are examined when edges are missing from the complete graph. The main result shows the existence of a path cover when at most \(\left\lfloor{n}/{2}\right\rfloor\) edges are missing. An example shows this result is sharp. A second result shows that a path cover can be found efficiently if a matching is missing.

A map shows only the names of some (but not all) towns in a region. If for each town, the names of all neighboring towns are known, when is it possible to reconstruct from this information the missing names? We deal with a generalization of this problem to arbitrary graphs. For a graph \(G = (V, E)\) with \(n\) nodes, we give an \(O(n^3)\) algorithm to recognize those instances for which the answer is YES, as well as two characterization theorems: NO-instances are determined by the existence of a certain partition of \(V\) and YES-instances by the existence of a suitable weak order in \(V\).

Let \(G\) be a connected claw-free graph of order \(n\). If \(G \not\in M\) and the minimum degree of \(G\) is at least \(\frac{n}{4}\), then \(G\) is traceable.

Here, \(M\) is a set of graphs such that each element in \(M\) can be decomposed into three disjoint subgraphs \(G_1\), \(G_2\), \(G_3\) and \(E_G(G_i, G_j) = u_iu_j\), here \(1 \leq i, j \leq 3\) and \(u_i \in G_i\), \(1\leq i \leq 3\).

In this paper, we consider the two-dimensional sequence of primitive polynomials, which is defined by two positive integers and a primitive polynomial. The concept of \(q^m\) conjugate order is used to describe the two-dimensional sequence. Using the two-dimensional sequences, we can find maximum period primitive-polynomial sequences for more values of degrees than using the one-dimensional sequences. Examples of the applications of the two-dimensional sequence by computer search are shown.

We show that results analogous to the theorem of the arithmetic and geometric means hold for the three multiplicative fundamental bases of the vector space of symmetric functions – the elementary symmetric functions, the homogeneous symmetric functions, and the power sum symmetric functions. We give examples to demonstrate that no such results hold for the two non-multiplicative fundamental bases – the Schur functions and the monomial symmetric functions.

We describe a class of graphs \(\Gamma\) for which the stability number can be obtained in polynomial time. A graph in class \(\Gamma\) is chair-free, net-free, and has the property that the claw-centers form an independent set.

A Freeman-Youden rectangle (FYR) is a Graeco-Latin row-column design consisting of a balanced superimposition of two Youden squares. There are well-known infinite series of FYRs of sizes \(q \times (2q + 1)\) and \((q+1) \times (2q+1)\), where \( (2q+1) \) is a prime power congruent to 3 (modulo 4). Any member of these series is readily constructed from an initial column whose entries are specified very simply in terms of powers of a primitive root of GF\((2q + 1)\).

We now show that, for \(q \geq 9\), initial columns for FYRs of the above sizes can be specified more generally, which allows us to obtain many more FYRs, which are unlike any that have previously appeared in the literature. We present enumerations for \(q = 9\) and \(q = 11\), and we tabulate new FYRs for these values of \(q\). We also present some new FYRs for \(q = 15\).

The harmonious chromatic number of a graph \(G\), denoted \(h(G)\), is the smallest number of colors needed to color the vertices of \(G\) so that adjacent vertices receive different colors and no two edges have the same pair of colors represented at their endvertices.

The mixed harmonious Ramsey number \(H(a, b)\) is defined to be the smallest integer \(p\) such that if a graph \(G\) has \(p\) vertices, then either \(h(G) \geq a\) or \(\alpha(G) \geq b\). For certain values of \(a\) and \(b\), we determine the exact value of \(H(a,b)\). In some other cases, we are able to determine upper and lower bounds for \(H(a, b)\).

Let \(H\) and \(Y\) be fixed digraphs, and let \(h\) be a fixed homomorphism of \(H\) to \(Y\). The \emph{Homomorphism Factoring Problem with respect} to \((H, h, Y)\) is described as follows:

\text{HFP}(H, h, Y)

INSTANCE: A digraph \(G\) and a homomorphism \(g\) of \(G\) to \(Y\).

QUESTION: Does there exist a homomorphism \(f\) of \(G\) to \(H\) such that \(h \circ f = g\)? That is, can the given homomorphism \(g\) be factored into the composition of \(h\) and some homomorphism \(f\) of \(G\) to \(H\)?

We investigate the complexity of this problem and show that it differs from that of the \(H\)-colouring problem, i.e., the decision problem “is there a homomorphism of a given digraph \(G\) to the fixed digraph \(H\)?”, and of restricted versions of this problem. We identify directed graphs \(H\) for which any homomorphism factoring problem involving \(h\) is solvable in polynomial time. By contrast, we prove that for any fixed undirected graph \(Y\) which is not a path on at most four vertices, there exists a fixed undirected graph \(H\), which can be chosen to be either a tree or a cycle, and a fixed homomorphism \(h\) of \(H\) to \(Y\) such that \text{HFP}(H, h, Y) is NP-complete, and if \(Y\) is such a path then \text{HFP}(H, h, Y) is polynomial.

A causal directed graph (CDG) is a finite directed graph with and-gates and or-nodes, in which nodes indicate true or false conditions and where arcs indicate causality. The set of all nodes implied true by a set of conditions (nodes declared true) is called the transitive closure of that set. Theorems 3-5 evaluate the number of distinct transitive closures for common CDGs. We present linear-space, linear-time algorithms for solving three transitive closure problems on CDG’s:

1. determine if a particular node is implied by a set of conditions,
2. Find the transitive closure of a set of conditions,
3. determine the minimal set of initial conditions for a given transitive closure of an acyclic CDG.

Implicit in Problem 3 is that every transitive closure of an acyclic CDG is generated by a unique minimal set of initial conditions. This is proved in Theorem 6.

A graph \(G\) is \emph{triangle-saturated} if every possible edge insertion creates at least one new triangle. Furthermore, if no proper spanning subgraph has this property, then \(G\) is minimally triangle-saturated. (Minimally triangle-saturated graphs of order \(n\) are the diameter \(2\) critical graphs when \(n \geq 3\).) The maximally triangle-free graphs of order \(n\) are a proper subset of the minimally triangle-saturated graphs of order \(n\) when \(n \geq 6\).

All triangle-saturated graphs are easily derivable from the minimally triangle-saturated graphs which are primitive, that is, have no duplicate vertices. We determine the \(23\) minimally triangle-saturated graphs of orders \(n \leq 7\) and identify the \(6\) primitive graphs among them.