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.

It has been conjectured that the smallest cardinality \(\theta(G)\) of a perfect neighbourhood set of a graph is bounded above by ir\((G)\), the smallest order of a maximal irredundant set.
We prove results concerning the construction of perfect neighbourhood sets from irredundant sets which could help to resolve the conjecture and which establish that \(\theta(G) \leq \text{ir}(G)\) in certain cases.
In particular, the inequality is proved for claw-free graphs and for any graph which has an ir-set \(S\) whose induced subgraph has at most six non-isolated vertices.

We introduce and study two new parameters, namely the upper harmonious chromatic number, \(H(G)\), and the upper line-distinguishing chromatic number, \(H'(G)\), of a graph \(G\).\(H(G)\) is defined as the maximum cardinality of a minimal harmonious coloring of a graph \(G\), while \(H'(G)\) is defined as the maximum cardinality of a minimal line-distinguishing coloring of a graph \(G\).
We show that the decision problems corresponding to the computation of the upper line-distinguishing and upper harmonious chromatic numbers are NP-complete for general graphs \(G\).We then determine \(H'(P_n)\) and \(H(P_n)\).
Lastly, we show that \(H\) and \(H’\) are incomparable, even for trees.

For a graph \(G\), assign an integer value weight to each edge. For a vertex \(v\), the label of v is the sum of weights of the edges incident with it. Further, the weighting is irregular if all the vertex labels are distinct. It is well known that if \(G\) has at most one isolated vertex and no isolated edges, then there exist irregular assignments, in fact, using positive edge weights.

In this paper, we consider the following special weighting:

– If \(G\) has order \( 2 k + 1\), then a consecutive labeling is an assignment where the vertex labels are precisely \(-k, -k+1, \ldots, -1, 0, 1, 2, \ldots, k-1, k\).

– If \(G\) has order \( 2k\), then a consecutive labeling is an assignment where the vertex labels are precisely \( -k+1, \ldots, -1, 0, 0, 1, 2, \ldots, k-1\).

Here we show that every graph which has an irregular assignment also has a consecutive labeling. This concept is extended by considering all consecutive labelings and looking for one that has the smallest maximum, in absolute value, edge weight. This weight is referred to as the consecutive strength. Results parallel to the concept of irregularity strength are presented.

A modification of the Schreier-Sims algorithm is described which builds a permutation group utilising the transitivity of the stabiliser subgroups. Alternating and symmetric groups are recognised by their transitivity, resulting in a greatly improved time to build symmetric and alternating groups.
The algorithm has applications to graph isomorphism and other combinatorial isomorphism algorithms, as well as permutation group algorithms.

Suppose \(G = (V, E)\) is a graph in which every vertex \(v\) has a non-negative real number \(\omega(v)\) as its weight. The \(\omega\)-distance sum of \(v\) is \(D_{G,\omega}(v) = \sum_{u \in V} d(v, u)\omega(u).\) The \(\omega\)-median \(M_\omega(G)\) of \(G\) is the set of all vertices \(v\) with minimum \(\omega\)-distance sum \(D_{G,\omega}(v)\). This paper gives linear-time algorithms for computing the \(\omega\)-medians of interval graphs and block graphs.

Let \(p\) denote the number of vertices in a graph and let \(q\) denote the number of edges. Two cycles in a graph are disjoint if they have no common vertices. Pósa proved that any graph with \(q \geq 3p – 5\) contains two disjoint cycles. This result does not apply to planar graphs, since every planar graph has \(q \leq 3p – 6\).
In this paper, I show that any planar graph with \(q \geq 2p\) contains two disjoint cycles. I also show that this bound is best possible and that there is no minimum number of edges in a planar graph which will ensure the graph contains \(3\) disjoint cycles. Furthermore, a sufficient condition for any triangle-free graph (and therefore any bipartite graph) to contain \(k\) disjoint cycles is given.