It is shown that the Overfull Conjecture, which would provide a chromatic index characterization for a large class of graphs, and the Conformability Conjecture, which would provide a total chromatic number characterization for a large class of graphs, both in fact apply to almost all graphs, whether labelled or unlabelled. The arguments are based on Polya’s theorem, and are elementary in the sense that practically no knowledge of random graph theory is presupposed. It is similarly shown that the Biconformability Conjecture, which would provide a total chromatic number characterization for a large class of equibipartite graphs, in fact applies to almost all equibipartite graphs.

The \([0,\infty)\)-valued dominating function minimization problem has the \([0,\infty)\)-valued packing function as its linear programming dual. The standard \(\{0, 1\}\)-valued minimum dominating set problem has the \(\{0, 1\}\)-valued maximum packing set problem as its binary dual. The recently introduced complementary problem to a minimization problem is also a maximization problem, and the complementary problem to domination is the maximum enclaveless problem. This paper investigates the dual of the enclaveless problem, namely, the domination-coverage number of a graph. Specifically, let \(\eta(G)\) denote the minimum total coverage of a dominating set. The number of edges covered by a vertex \(v\) equals its degree, \(\deg v\), so \(\eta(G) = \text{MIN}\{\sum_{s \in S} \deg s: S \text{ is a dominating set}\}\). Bounds on \(\eta(G)\) and computational complexity results are presented.

In this note, we computationally prove that the size of smallest critical sets for the quaternion group of order eight, the group \(\mathbb{Z}_2 \times \mathbb{Z}_4\) and the dihedral group of order eight are 20, 21 and 22, respectively.

A graph is said \(h\)-decomposable if its edge-set is decomposable into hamiltonian cycles. In this paper, we prove that if \(G = L_1 \cup L_2 \cup L_3\) is a strongly hamiltonian bipartite cubic graph (where \(L_i\) is a perfect matching, for \(1 \leq i \leq 3\) and \((L_1, L_2, L_3)\) is a \(1\)-factorization of \(G\)), then \(G \times C_{2n+1}\) (where \(n\) is odd and \(n \geq 1\)) is decomposable. As a corollary, we show that for \(r \geq 1\) odd and \(n \geq 3\), \(K_{r,r} \times K_n\) is \(h\)-decomposable. Moreover, in the case where \(G\) is a strongly hamiltonian non-bipartite cubic graph, we prove that the same result can be derived using a special perfect matching. Hence \(K_{2r} \times K_{2n+1}\) will be \(h\)-decomposable, for \(r,n \geq 1\).

To study the product of \(G = L_1 \cup L_2 \cup L_3\) by even cycle, we define a dual graph \(G_C\) based on an alternating cycle subset of \(L_2 \cup L_3\). We show that if a non-bipartite cubic graph \(G = L_1 \cup L_2 \cup L_3\), with \(|V(G)| = 2m\), admits \(L_1 \cup L_2\) as a hamiltonian cycle and \(G_C\) is connected, then \(G \times K_2\) is hamiltonian and \(G \times C_{2n}\) has two edge-disjoint hamiltonian cycles. Finally, we prove that if \(C = L_2 \cup L_3\) and \(L_1 \cup L_3\) admits a particular alternating \(4\)-cycle \(C’\), then \(G \times C_{2n}\) is \(h\)-decomposable.