We study cube-complementary graphs, that is, graphs whose com- plement and cube are isomorphic. We prove several necessary conditions for a graph to be cube-complementary, describe ways of building new cube-complementary graphs from existing ones, and construct infinite families of cube-complementary graphs.

We suggest the notion of the surface area centered at an edge for a network structure, which generalizes the usual notion of surface area of a structure centered at a vertex. As a specific result, we derive explicit expressions of the edge-centered surface areas for the edge-asymmetric \((n, k)\)-star graph, following a generating function approach, in terms of two different kinds of edges.

For a set \( S \) of \( k \) vertices of \( G \), let \( \kappa(S) \) denote the maximum number \( \ell \) of pairwise edge-disjoint trees \( T_1, T_2, \ldots, T_\ell \) in \( G \) such that \( V(T_i) \cap V(T_j) = S \) for \( 1 \leq i \neq j \leq \ell \) and \( \lambda(S) \) denote the maximum number \( \ell \) of pairwise edge-disjoint trees \( T_1, T_2, \ldots, T_\ell \) in \( G \) such that \( S \subseteq V(T_i) \) for \( 1 \leq i \leq \ell \). Similar to the classical maximum local connectivity, H. Li et al. introduced the parameter \( \overline{\kappa}_k(G) = \max\{\kappa(S) \mid S \subseteq V(G), |S| = k\} \), which is called the maximum generalized local connectivity of \( G \). The maximum generalized local edge-connectivity of \( G \) which was introduced by X. Li et al. is defined as \( \overline{\lambda}_k(G) = \max\{\lambda(S) \mid S \subseteq V(G), |S| = k\} \). In this paper, we investigate the maximum generalized local connectivity and edge-connectivity of a cubic connected Cayley graph \( G \) on an Abelian group. We determine the precise values for \( \overline{\kappa}_3(G) \) and \( \overline{\lambda}_3(G) \) and also prove some results of \(\overline{\kappa}_k(G)\) and \(\overline{\lambda}_k(G)\) for general \(k\).

The generalized \( k \)-connectivity \( \kappa_k(G) \) of a graph \( G \) was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized \( k \)-edge-connectivity. In this paper, we completely determine the precise values of the generalized \( 3 \)-connectivity and generalized \( 3 \)-edge-connectivity for the Cartesian products of some graph classes.

In this work, we investigate the gap-adjacent-chromatic number, a graph colouring parameter introduced by M. A. Tahraoui, E. Duchéne, and H. Kheddouci in \([5]\). From an edge labelling \( f: E \to \{1, \ldots, k\} \) of a graph \( G = (V, E) \), the vertices of \( G \) get an induced colouring. Vertices of degree greater than one are coloured with the difference between their maximum and their minimum incident edge label, i.e., with their so-called gap, and vertices of degree one get their incident edge label as colour. The gap-adjacent-chromatic number of \( G \) is the minimum \( k \) for which a labelling \( f \) of \( G \) exists that induces a proper vertex colouring.

The main purpose of this work is to state easy colouring approaches for bipartite graphs and to estimate the gap-adjacent-chromatic number for arbitrary graphs in terms of the chromatic number.

We call \( T = (G_1, G_2, G_3) \) a graph-triple of order \( t \) if the \( G_i \) are pairwise non-isomorphic graphs on \( t \) non-isolated vertices whose edges can be combined to form \( K_t \). If \( m \geq t \), we say \( T \) divides \( K_m \) if \( E(K_m) \) can be partitioned into copies of the graphs in \( T \) with each \( G_i \) used at least once, and we call such a partition a \( T \)-multidecomposition. For each graph-triple \( T \) of order \( 6 \) for which it was not previously known, we determine all \( K_m \), \( m \geq 6 \), that admit a \( T \)-multidecomposition. Moreover, we determine maximum multipackings and minimum multicoverings when \( K_m \) does not admit a multidecomposition.

For the Firefighter Process with weights on the vertices, we show that the problem of deciding whether a subset of vertices of a total weight can be saved from burning remains NP-complete when restricted to binary trees. In addition, we show that a greedy algorithm that defends the vertex of highest degree adjacent to a burning vertex is not an \(\epsilon\)-\emph{approximation} algorithm for any \(\epsilon \in (0, 1]\) for the problem of determining the maximum weight that can be saved. This closes an open problem posed by MacGillivray and Wang.

Let \( K_v \) be the complete graph with \( v \) vertices. Let \( G \) be a finite simple graph. A \( G \)-decomposition of \( K_v \), denoted by \((v, G, 1)\)-GD, is a pair \((X, \mathcal{B})\), where \( X \) is the vertex set of \( K_v \), and \(\mathcal{B}\) is a collection of subgraphs of \( K_v \), called blocks, such that each block is isomorphic to \( G \). In this paper, the discussed graphs are \( G_i \), \( i = 1, 2, 3, 4 \), where \( G_i \) are four kinds of graphs with eight vertices and eight edges. We obtain the existence spectrum of \((v, G_i, 1)\)-GD.

We present a simple bijection between the set of triangulations of a convex polygon and the set of \(312\)-avoiding permutations.

A \({2-rainbow\; dominating\; function}\) of a graph \( G \) is a function \( g \) that assigns to each vertex a set of colors chosen from the set \( \{1, 2\} \) so that for each vertex \( v \) with \( g(v) = \emptyset \) we have \( \cup_{u \in N(v)} g(u) = \{1, 2\} \). The minimum of \( g(V(G)) = \sum_{v \in V(G)} |g(v)| \) over all such functions is called the \({2-rainbow \;domination\; number}\) \( \gamma_{r2}(G) \). A \(2\)-rainbow dominating function \( g \) of a graph \( G \) is independent if no two vertices assigned non-empty sets are adjacent. The \({independent \;2-rainbow\; domination\; number}\) \( i_{r2}(G) \) is the minimum weight of an independent \(2\)-rainbow dominating function of \( G \). In this paper, we study independent \(2\)-rainbow domination in graphs. We present some bounds and relations with other domination parameters.