
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
The number of hypohamiltonian and that of hypotraceable
In a graph
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.
Let
This result generalizes an early result by Ellingham and is a partial result of Tutte’s edge-
Let
It has been known that
for
A string is strongly square-free if it contains no Abelian squares; that is, adjacent substrings which are permutations of each other. We discuss recent results concerning the construction of strongly square-free finite strings.
It is shown that the circuit polynomial characterizes many of the well-known families of graphs. These include chains, stars, cycles, complete graphs, regular complete bipartite graphs, and wheels. Some analogous results are deduced for the characteristic polynomial and the
A connected dominating set is a dominating set
Trees, for instance, clearly belong to this collection. A partial characterization will be discussed; in particular, we determine those graphs which have the property that all spanning trees have the same number of leaves. It is noted that membership in this sub-collection of C can be determined in polynomial time.
A continuum with finitely many non-cut points is an irreducible tree. A two-variable power series for the number of (unlabelled) irreducible trees with \(p\) pendant and \(q\) interior vertices.
The result is then specialized to get Harary's series for the number of irreducible trees with \(n\) vertices and to another series for the number of irreducible trees with \(p\) pendant vertices, a result of interest in continuum theory.
The theory of lifting voltage digraphs provides a useful tool for constructing large digraphs with specified properties from suitable small base digraphs endowed with an assignment of voltages (= elements of a finite group) on arcs.
We revisit the degree/diameter problem for digraphs from this new perspective and prove a general upper bound on the diameter of a lifted digraph in terms of properties of the base digraph and voltage assignment.
In addition, we demonstrate that all currently known largest vertex-transitive Cayley digraphs for semidirect products of groups can be described by means of a voltage assignment construction using simpler groups.
The “characteristic” of a graph—the number of vertices, minus the number of edges, plus the number of triangles, etc.—is a little-studied, overtly combinatorial graph parameter intrinsically related to chordal graphs and common neighborhoods of subgraphs. I also introduce a sequence of related “higher characteristic” parameters.
A \emph{least deviant path} between two vertices in a weighted graph is defined as a path that minimizes the difference between the largest and smallest edge weights on the path.
Algorithms are presented to determine the least deviant path. The fastest algorithm runs in
An SOLS (self-orthogonal Latin square) of order
In this article, it is shown that an
It is straightforward to show that the full automorphism group of
In this note, necessary and sufficient conditions are given for the existence of an equitable partial Steiner triple system
A catalogue is presented which contains the graphs having order at most 10 which are critical with respect to the total chromatic number. A number of structural properties which cause these graphs to be critical are discussed, and a number of infinite classes of critical graphs are identified.
A total colouring of a graph
A longstanding conjecture, made independently by Behzad [3] and Vizing [17], claims that
where
We define a graph
Given
exceeded. Motivated by the NP-hardness of the problem, Coffman et al. proposed a class of heuristics, the \emph{prefix} algorithms, and analyzed its worst-case performance bound.
Bruno and Downey gave a probabilistic bound for the FFI algorithm (which is a prefix algorithm proposed by Coffman et al.), under the assumption that piece sizes are drawn from the uniform distribution over
dependent only on
where
Another probabilistic bound is also given for
mild assumption of
The distance of a vertex
Let
vertices.
A weak repetition in a string consists of two or more adjacent substrings which are permutations of each other. We describe a straightforward
on an arbitrary alphabet
An algorithm is presented which, when given the non-isomorphic designs with given parameters, generates all the trades in each of the designs. The lists of trades generated by the algorithm were used to find the sizes, previously unknown, of smallest defining sets of the
defining sets. The lists of trades were then used to find the sizes of these smallest member and class defining sets, for five parameter sets.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.