Historically, a number of problems and puzzles have been introduced that initially appeared to have no connection to graph colorings but, upon further analysis, suggested graph colorings problems. In this paper, we discuss two combinatorial problems and several graph colorings problems that are inspired by these two problems. We survey recent results and open questions in this area of research as well as some relationships among these coloring parameters and well-known colorings and labelings.

Let \( G \) be a graph with vertex set \( V(G) \) and edge set \( E(G) \), and let \( A \) be an abelian group. A labeling \( f: V(G) \to A \) induces an edge labeling \( f^*: E(G) \to A \) defined by \( f^*(xy) = f(x) + f(y) \) for each edge \( xy \in E(G) \). For \( i \in A \), let \( v_f(i) = |\{v \in V(G) : f(v) = i\}| \), and \( e_f(i) = |\{e \in E(G) : f^*(e) = i\}| \). Define \( c(f) = \{ |e_f(i) – e_f(j)| : (i, j) \in A \times A \} \).A labeling \( f \) of a graph \( G \) is said to be A-friendly if \( |\text{v}_f(i) – \text{v}_f(j)| \leq 1 \) for all \( (i, j) \in A \times A \). If \( c(f) \) is a \( (0,1) \)-matrix for an A-friendly labeling \( f \), then \( f \) is said to be A-cordial.When \( A = \mathbb{Z}_2 \), the friendly index set of the graph \( G \), denoted \( FI(G) \), is defined as \( \{ |e_f(0) – e_f(1)| : \text{the vertex labeling } f \text{ is } \mathbb{Z}_2\text{-friendly} \} \).In this paper, we completely determine the friendly index sets for two classes of cubic graphs, prisms and Möbius ladders , are completely determined.

A vertex \( x \) in a graph \( G \) strongly resolves a pair of vertices \( v \) and \( w \) if there exists a shortest path from \( x \) to \( w \) that contains \( v \), or a shortest path from \( x \) to \( v \) that contains \( w \) in \( G \). A set of vertices \( S \subseteq V(G) \) is a strong resolving set of \( G \) if every pair of distinct vertices in \( G \) is strongly resolved by some vertex in \( S \). The strong metric dimension \( sdim(G) \) of a graph \( G \) is the minimum cardinality of a strong resolving set of \( G \).

Given two disjoint copies of a graph \( G \), denoted \( G_1 \) and \( G_2 \), and a permutation \( \sigma : V(G_1) \to V(G_2) \), the permutation graph \( G_\sigma = (V, E) \) is defined with vertex set \( V = V(G_1) \cup V(G_2) \) and edge set \( E = E(G_1) \cup E(G_2) \cup \{uv \mid v = \sigma(u)\} \).

We show that for a connected graph \( G \) of order \( n \geq 3 \), the strong metric dimension of \( G_\sigma \) satisfies \( 2 \leq sdim(G_\sigma) \leq 2n – 2 \). We also provide an example demonstrating that there is no function \( f \) such that \( f(sdim(G)) > sdim(G_\sigma) \) for all pairs \( (G, \sigma) \). Additionally, we prove that \( sdim(G_{\sigma_o}) \leq 2sdim(G) \) when \( \sigma_o \) is the identity permutation.

Further, we characterize permutation graphs \( G_\sigma \) that satisfy \( sdim(G_\sigma) = 2n – 2 \) or \( 2n – 3 \) when \( G \) is a complete \( k \)-partite graph, a cycle, or a path on \( n \) vertices.

In a recent paper, E. Gelman provided an exact formula for the number of subgroups of a given index for the Baumslag-Solitar groups \( \text{BS}(p, q) \) when \( p \) and \( q \) are coprime. We use Gelman’s proof as the basis for an algorithm that computes a maximal set of inequivalent permutation representations of \( \text{BS}(p, q) \) with degree \( n \). The computational complexity of this algorithm is linear in both space and time with respect to the index. We compare the performance of this algorithm with the Todd-Coxeter procedure, which generally lacks a polynomial bound on the number of cosets used during the enumeration process.

An \( H_2 \) graph is a multigraph on three vertices with a double edge between one pair of distinct vertices and a single edge between the other two pairs. The problem of decomposing a complete multigraph \( 3K_{8t} \) into \( H_2 \) graphs has been completely solved. In this paper, we describe some new procedures for such decompositions and pose the following question: Can these procedures be adapted or extended to provide a unified proof of the existence of \( H_2(8t, \lambda) \)’s?

For a nontrivial connected graph \( G \) of order \( n \) and a cyclic ordering \( s: v_1, v_2, \ldots, v_n, v_{n+1} = v_1 \) of \( V(G) \), let \( d(s) = \sum_{i=1}^n d(v_i, v_{i+1}) \), where \( d(v_i, v_{i+1}) \) is the distance between \( v_i \) and \( v_{i+1} \) for \( 1 \leq i \leq n \). The Hamiltonian number \( h(G) \) and the upper Hamiltonian number \( h^+(G) \) of \( G \) are defined as:

1. \( h(G) = \min \{ d(s) \} \), where the minimum is taken over all cyclic orderings \( s \) of \( V(G) \).
2. \( h^+(G) = \max \{ d(s) \} \), where the maximum is taken over all cyclic orderings \( s \) of \( V(G) \).

All connected graphs \( G \) with \( h^+(G) = h(G) \) and \( h^+(G) = h(G) + 1 \) have been characterized in [6, 13]. In this note, we first present a new and significantly improved proof of the characterization of all graphs whose Hamiltonian and upper Hamiltonian numbers differ by 1. We then determine all pairs of integers that can be realized as the order and upper Hamiltonian number of some tree.