Let \(G\) be a cubic graph containing no subdivision of the Petersen graph. If \(G\) has a \(2\)-factor \(F\) consisting of two circuits \(C_1\) and \(C_2\) such that \(C_1\) is chordless and \(C_2\) has at most one chord, then \(G\) is edge-\(3\)-colorable.This result generalizes an early result by Ellingham and is a partial result of Tutte’s edge-\(3\)-coloring conjecture.

Let \(f(n,k)\) be the maximum chromatic number among all graphs whose edge set can be covered by \(n\) copies of \(K(n)\), the complete graph on \(n\) vertices, so that any two of those \(K(n)\) share at most \(k\) vertices.It has been known that \(f(n,k) = (1 – o(1)).n^{{3}/{2}}\) for \(k \geq n^{{1}/{2}}\). We show that
\((1 – o(1))n.k \leq f(n,k) \leq (k+1)(n-k)\) for \(k < n^{{1}/{2}}\), hence, for \({1}/{k} = o(1)\),\(f(n,k) = (1 + o(1))n.k.\)

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 \(\mu\)-polynomial.

A connected dominating set is a dominating set \(S\) with the additional property that the subgraph induced by \(S\) is connected. We are interested in the collection C of graphs in which every minimal connected dominating set is of one size.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 \({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 \(O(|E|^{1.793})\), in the worst case. A type of two-dimensional binary search is used to achieve this running time.

An SOLS (self-orthogonal Latin square) of order \(n\) with \(n_i\) missing sub-SOLS (holes) of order \(h_i\) (\(1 \leq i \leq k\)), which are disjoint and spanning (i.e., \(\sum_{i=1}^{k} n_ih_i = n\)), is called a frame SOLS and denoted by \(\text{FSOLS}(h_1^{n_1}, h_2^{n_2}, \ldots, h_k^{n_k})\).In this article, it is shown that an \(\text{FSOLS}(3^{n-u}3^1)\) exists if and only if \(n \geq 4\) and \(n \geq 1 + \frac{2u}{3}\), with seventeen possible exceptions \((n, u) =\{(5, 1)\}\) and \(\{(n, u) = (n, \lfloor \frac{3(n-1)}{2}\rfloor)\) for \((n \in \{6, 10, 14, 18, 22, 30, 34, 38, 42, 46, 54, 58, 62, 66, 70, 94\} \).