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.

Let \(G\) be a simple graph. A set \(D\) of vertices of \(G\) is dominating if every vertex not in \(D\) is adjacent to some vertex in \(D\). A set \(M\) of edges of \(G\) is called independent, or a matching, if no two edges of \(M\) are adjacent in \(G\). The domination number \(\gamma(G)\) is the minimum order of a dominating set in \(G\). The edge independence number \(\alpha_0(G)\) is the maximum size of a matching in \(G\). If \(G\) has no isolated vertices, then the inequality \(\gamma(G) \leq \alpha_0(G)\) holds. In this paper we characterize regular graphs, unicyclic graphs, block graphs, and locally connected graphs for which \(\gamma(G) = \alpha_0(G)\).

Let \(n \geq 1\) be an integer and let \(G\) be a graph of order \(p\). A set \(I_n\) of vertices of \(G\) is \(n\)-independent if the distance between every two vertices of \(I_n\) is at least \(n+1\). Furthermore, \(I_n\) is defined to be an \(n\)-independent dominating set of \(G\) if \(I_n\) is an \(n\)-independent set in \(G\) and every vertex in \(V(G) – I_nv is at distance at most \(n\) from some vertex in \(I_n\). The \(n\)-independent domination number, \(i_n(G)\), is the minimum cardinality among all \(n\)-independent dominating sets of \(G\). Hence \(i_n(G) = i(G)\) where \(i(G)\) is the independent domination number of \(G\). We establish the existence of a connected graph \(G\) every spanning tree \(T\) of which is such that \(i_n(T) < i_n(G)\). For \(n \in \{1,2\}\) we show that, for any tree \(T\) and any tree \(T’\) obtained from \(T\) by joining a new vertex to some vertex of \(T\), we have \(i_n(T) \geq i_n(T’)\). However, we show that this is not true for \(n \geq 3\). We show that the decision problem corresponding to the problem of computing \(i_n(G)\) is NP-complete, even when restricted to bipartite graphs. Finally, we obtain a sharp lower bound on \(i_n(G)\) for a graph \(G\).

In this paper, we consider symmetric and skew equivalence of Hadamard matrices of order \(28\) and present some computational results and some applications.