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.

In this paper, we derive some inequalities on the existence of balanced arrays (B-arrays) of strength six and with two symbols by using some results involving moments from Statistics. Besides providing illustrative examples, we will make brief comments on the use of these combinatorial arrays in Statistical Design of Experiments.

We estimate the number of labelled loop-free Eulerian oriented graphs with multiple edges with \(n\) vertices by using an \(n\)-dimensional Cauchy integral. An asymptotic formula is obtained for the case where the multiplicity of each edge is \(O(\log n)\).

The number of hypohamiltonian and that of hypotraceable \(n\)-vertex digraphs are both bounded below by a superexponential function of \(n\) for \(n \geq 6\) and \(n \geq 7\), respectively.

In a graph \(G = (V, E)\), a set \(S \subset V\) is a dominating set if each vertex of \(V – S\) is adjacent to at least one vertex in \(S\).Approximately 1000 papers have been written on domination-related concepts, with more than half of them appearing in the literature in the last five years. Obviously, a comprehensive survey is beyond the scope of this paper, so a brief overview is presented.