Let \( \lambda K_v \) be the complete multigraph, and \( G \) a finite simple graph. A \( G \)-design (\( G \)-packing, \( G \)-covering, respectively) of \( \lambda K_v \) is denoted by \( GD(v, G, \lambda) \) (\( PD(v, G, \lambda) \), \( CD(v, G, \lambda) \), respectively). In this paper, we will give some construction methods of graph packings and graph coverings, determine the existence spectrum for the \( G \)-designs of \( \lambda K_v \), and construct the maximum packings and the minimum coverings of \( \lambda K_v \) with \( G \) for any positive integer \( \lambda \). The graph \( G \) is either \( (K_4 – e) \cup P_1 \) or \( C_5 \bigodot P_1 \). Therefore, the problems of \( G \)-coverings and \( G \)-packings of \( \lambda K_v \) are solved completely when \( G \) is a graph with order \( 6 \) and \( |E(G)| \leq 6 \).

A maximal directed path in an acyclic orientation of a graph \( G \) is a path \( a_1 \to a_2 \to \cdots \to a_k \) such that \( \text{id}\; a_1 = \text{od}\; a_k = 0 \). The compression of \( G \) is the smallest integer \( k \) such that, for any acyclic orientation of \( G \), there is a maximal directed path of length at most \( k \). We characterize graphs with compression \( 1 \) and \( 2 \) and determine the compression of trees.

The generalized deBruijn graph \(dB(a,k)\) is the directed graph with \(a^k\) vertices and edges between vertices \(x = a_1, a_2, \ldots, a_k\) and \(y = b_1, b_2, \ldots, b_k\) precisely when \(a_2\cdots a_k = b_1,b_2\cdots b_{k-1}\). The deBruijn graphs can be further generalized by introducing an overlap variable \(t \leq k-1\) where the number of consecutive digits by which the vertex labels (sequences) overlap is \(t\). The \(\alpha\)-overlap graph is the underlying simple graph of the generalized deBruijn digraph with vertex label overlap \(0 t > 0\). Thus \(dB(a,k) = G(a,k,k-1)\). In this paper, we show that every \(\alpha\)-overlap graph is \(3\)-colorable for any \(a\) if \(k\) is sufficiently large. We also determine bounds on the chromatic number of the \(\alpha\)-overlap graphs if \(a\) is much larger than \(k\).

For an ordered set \( W = \{w_1, w_2, \dots, w_k\} \) of \( k \) distinct vertices in a nontrivial connected graph \( G \), the metric code of a vertex \( v \) of \( G \) with respect to \( W \) is the \( k \)-vector
\[
\text{code}(v) = (d(v, w_1), d(v, w_2), \dots, d(v, w_k)),
\]
where \( d(v, w_i) \) is the distance between \( v \) and \( w_i \) for \( 1 \leq i \leq k \). The set \( W \) is a local metric set of \( G \) if \( \text{code}(u) \neq \text{code}(v) \) for every pair \( u, v \) of adjacent vertices of \( G \). The minimum positive integer \( k \) for which \( G \) has a local metric set of cardinality \( k \) is the local metric dimension \(\text{lmd}(G)\) of \( G \). We determine the local metric dimensions of joins and compositions of some well-known classes of graphs, namely complete graphs, cycles, and paths. For a nontrivial connected graph \( G \), a vertex \( v \) of \( G \), and an edge \( e \) of \( G \), where \( v \) is not a cut-vertex and \( e \) is not a bridge, it is shown that \(\text{lmd}(G – v) \leq \text{lmd}(G) + \text{deg}(v)\) and \(\text{lmd}(G – e) \leq \text{lmd}(G) + 2.
\) The sharpness of these two bounds is studied. We also present several open questions in this area of research.

Let \( G \) be a connected graph. In this paper, we introduce the concepts of vertex-to-clique \({radius}\) \( r_1 \), vertex-to-clique \({diameter}\) \( d_1 \), clique-to-vertex \({radius}\) \( r_2 \), clique-to-vertex \({diameter}\) \( d_2 \), clique-to-clique \({radius}\) \( r_3 \), and clique-to-clique \({diameter}\) \( d_3 \) in \( G \). We prove that for any connected graph, \( r_i \leq d_i \leq 2r_i + 1 \) for \( i = 1, 2, 3 \). We also find expressions for \( d_1 \), \( d_2 \), and \( d_3 \) for a tree \( T \) in terms of \( r_1 \), \( r_2 \), and \( r_3 \) respectively, which determine the cardinality of each \( Z_i(T) \), where \( Z_i(T) \) is the vertex-to-clique, the clique-to-vertex, and the clique-to-clique center respectively of \( T \) for \( i = 1, 2, 3 \). If \( G \) is a graph that is not a tree and if \( g(G) \) denotes the girth of the graph, then its relation with each of \( d_1 \), \( d_2 \), and \( d_3 \) is discussed. We also characterize the class of graphs \( G \) such that \( G \) is not a tree, \( d_3 \neq 0 \), and \( g(G) = 2d_3 + 3 \).

A tournament is an orientation of a complete graph, and a multipartite or \( c \)-partite tournament is an orientation of a complete \( c \)-partite graph. If we speak of a path, then we mean a directed path.

Let \( D \) be a regular \( c \)-partite tournament with \( r \) vertices in each partite set, and let \( X \subseteq V(D) \) be an arbitrary set with exactly \( 2 \) vertices from each partite set. For all \( c \geq 4 \), the authors determined in a recent article the minimal value \( g(c) \) such that \( D – X \) is Hamiltonian for every regular multipartite tournament with \( r \geq g(c) \). In this paper, we will supplement this result by postulating a given path covering number instead of the Hamiltonicity of the digraph \( D – X \). This means, for all \( c \geq 4 \) and \( k \geq 1 \), we will determine the minimal value \( h(k, c) \) such that \( D – X \) can be covered by at most \( k \) paths for every regular \( c \)-partite tournament with \( r \geq h(k, c) \). Moreover, we will present the minimal path covering number of \( D – X \), if \( D \) is a regular \( 3 \)-partite tournament and \( X \) contains exactly \( s \) vertices (\( s \geq 2 \)) from every partite set.

We investigate the problem of decomposing the edges of a connected circulant graph with \( n \) vertices and generating set \( S \) into isomorphic subgraphs, each having \( n \) edges. For \( 8 \)-regular circulants, we show that this is always possible when \( s+2 \leq \frac{n}{4} \) for all edge lengths \( s \in S \).

This paper continues the results of “Domination Cover Pebbling: Graph Families.” An almost sharp bound for the domination cover pebbling (DCP) number, \( \psi(G) \), for graphs \( G \) with specified diameter has been computed. For graphs of diameter two, a bound for the ratio between \( \lambda(G) \), the cover pebbling number of \( G \), and \( \psi(G) \) has been computed. A variant of domination cover pebbling, called subversion DCP, is introduced, and preliminary results are discussed.

A graph \(G\) has a representation modulo \(n\) if there exists an injective map \(f: V(G) \to \{0, 1, \dots, n-1\}\) such that vertices \(u\) and \(v\) are adjacent if and only if \(f(u) – f(v)\) is relatively prime to \(n\). The representation number \(rep(G)\) is the smallest \(n\) such that \(G\) has a representation modulo \(n\). In 2000, Evans, Isaak, and Narayan determined the representation number of a complete graph minus a path. In this paper, we refine their methods and apply them to the family of complete graphs minus a disjoint union of paths.

Let \(G = (V, E)\) be a graph and \(\overline{G}\) be the complement of \(G\). The complementary prism of \(G\), denoted \(G \overline{G}\), is the graph formed from the disjoint union of \(G\) and \(\overline{G}\) by adding the edges of a perfect matching between the corresponding vertices of \(G\) and \(\overline{G}\). A set \(D \subseteq V(G)\) is a locating-dominating set of \(G\) if for every \(u \in V(G) \setminus D\), its neighborhood \(N(u) \cap D\) is nonempty and distinct from \(N(v) \cap D\) for all \(v \in V(G) \setminus D\) where \(v \neq u\). The locating-domination number of \(G\) is the minimum cardinality of a locating-dominating set of \(G\). In this paper, we study locating-domination of complementary prisms. We determine the locating-domination number of \(G \overline{G}\) for specific graphs \(G\) and characterize the complementary prisms with small locating-domination numbers. We also present upper and lower bounds on the locating-domination numbers of complementary prisms, and we show that all values between these bounds are achievable.