Let \(G\) be a connected graph and \(T\) be a spanning tree of \(G\). (Here, trees and cycles are equated with their edge sets.) Then, the gi-pair \((G,T)\) is a dfs-pair if there exists a digraph \(D\) such that the underlying graph of \(D\) is \(G\), \(T\) is a rooted-ditree in \(D\), and every fundamental cycle of \((G,T)\) is a dicycle of \(D\). Two gi-pairs \((G,T)\) and \((G’,T)\) are cycle-isomorphic if there is a 1-1 mapping between \(Z(G)\) and \(Z(G’)\) so that \((G,T)\) and \((G’,T)\) have the same sets of fundamental cycles. Shinoda, Chen, Yasuda, Kajitani, and Mayeda [6] showed that a 2-connected graph \(G\) is series-parallel if and only if for every spanning tree \(T\) of \(G\), the gi-pair \((G,T)\) is cycle-isomorphic to a dfs-pair. In this paper, an alternate proof of this characterization is given. An efficient algorithm to find such a cycle-isomorphic dfs-pair is also described.

We determine the exact closure of all subsets \(K\) of \(\{3,\ldots,10\}\) which contain \(3\).

Let \(G\) be a simple graph on \(n\) vertices and an even number of edges. It was proved in [15] that the zero-sum (mod 2) Ramsey numbers are given by

\[R(G,\mathbb{Z}_2) =
\begin{cases}
n+2 & \text{if } G = K_{n}, n \equiv 0,1 \pmod{4} \\
n+1 & \text{if } G = K_{p} \cup K_q({\frac{p}{2}}) + (\frac{q}{2}) \equiv 0 \pmod{2} \\
n+1 & \text{if all degrees in } G \text{ are odd} \\
n & \text{otherwise}
\end{cases}
\]

The proof is rather long and based on complicated algebraic machinery. Here we shall prove that \(R(G,\mathbb{Z}_2) \leq n+2\) with equality holding iff \(G = K_{n,}n \equiv 0,1 \pmod{4}\).

The proof uses simple combinatorial arguments and it is also applied to the case, not considered before, when \(G\) has an odd number of edges. Some algorithmic aspects, which cannot be tackled using the methods of [1] and [15], are also considered.

In a previous paper [2] it was established that, up to isomorphism, there exist at least 112,000 symmetric \(2-(41,16,6)\) designs with a non-trivial automorphism of odd order. Using the underlying derived designs of just one of these and extending them to a \(2-(41,16,6)\) design we have found ten non-isomorphic symmetric \(2-(41,16,6)\) designs with trivial automorphism group (five pairs of non-selfdual designs).

A dominating function for a graph is a function from its vertex set into the unit interval so that the sum of function values taken ‘over the closed neighbourhood of each vertex is at least one. We prove that any graph has a positive minimal dominating function and begin an investigation of the question: When are convex combinations of minimal dominating functions themselves minimal dominating?

The author and N.K. Khachatrian proved that a connected graph \(G\) of order at least \(3\) is hamiltonian if for each vertex \(x\) the subgraph \(G_1(x)\) induced by \(x\) and its neighbors in \(G\) is an Ore graph.

We prove here that a graph \(G\) satisfying the above conditions is fully cycle extendible. Moreover, \(G\) is panconnected if and only if \(G\) is \(3\)-connected and \(G \neq K_n \lor \overline{K}_n\) for some \(n \geq 3\), where \(\lor\) is the join operation. The paper is concluded with two conjectures.

Let \(p,q\) denote primes, \(p \equiv 1 \pmod{4}\), \(g \equiv 3 \pmod{4}\), \(g \geq 7\). In an earlier study we established that if \(\gcd(q-1, p^{n-1}(p-1)) = 2\) and if a \(\mathbb{Z}\)-cyclic \(Wh(q+1)\) exists then a \(\mathbb{Z}\)-cyclic \(Wh(qp^n + 1)\) exists for all \(n \geq 0\). Here we consider \(\gcd(qg-1,p^{n-1}(p-1)) > 2\) and prove that if a \(\mathbb{Z}\)-cyclic \(Wh(q+1)\) exists then there exists a \(\mathbb{Z}\)-cyclic \(Wh(qp^n + 1)\) for all \(n \geq 0\). The proof employed depends on the existence of an appropriate primitive root of \(p\). Utilizing a theorem of S. D. Cohen we establish that such appropriate primitive roots always exist.

A 2-distant coloring of a graph is an assignment of positive integers to its vertices so that adjacent vertices cannot get either the same number or consecutive numbers. Given a 2-distant coloring of a graph \(G\), a hole of \(f\) is a finite maximal set of consecutive integers not used by \(f\), and \(h(f)\) is the number of holes of \(f\). In this paper we study the problem of minimizing the number of holes, i.e., we are interested in the number \(h(G) = \min_f h(f)\) where the minimum runs over all 2-distant colorings \(f\) of \(G\). Besides finding exact values for \(h(G)\) for particular graphs, we also relate \(h(G)\) to the path-covering number and the Hamiltonian completion number of \(G\).

For graph \(G\), a total dominating set \(S\) is a subset of the vertices in \(G\) such that every vertex in \(G\) is adjacent to at least one vertex in \(S\). The total domination number of \(G\) is the cardinality of a smallest total dominating set of \(G\). We consider the total domination number of graphs formed from an \(m\times n\) chessboard by letting vertices represent the squares, and letting two vertices be adjacent if a given chess piece can move between the associated squares. In particular, we bound from above and below the total domination numbers of the graphs induced by the movement of kings, knights, and crosses (a hypothetical piece that moves as does a king, except that it cannot move diagonally). We also provide some results of computer searches for the total domination numbers of small square boards.

A set of integers is \(k\)-multiple-free if it never contains two integers \(x\) and \(kx\), where \(k\) is a given integer greater than \(1\). Such a set \(S\) is maximal in \([1,n] = \{1,2,\dots,n\}\) if \(S \cup \{t\}\) is not \(k\)-multiple free for any \(t\) in \([1,n] \setminus S\). In this paper we investigate the size of maximal \(k\)-multiple-free subsets of \([1,n]\), prove that the smallest such set has \(\frac{(k^5-k^3+1)n}{k(k+1)(k^3-1)}+ 0(\log n)\) members, and show that given \(k\) and \(n\), if \(s\) is any integer between the minimum and maximum possible orders, there is a maximal \(k\)-multiple-free subset of \([1,n]\) with \(s\) elements.