Addressing a problem posed by Chellali, Haynes, and Hedetniemi (Discrete Appl. Math. 178 (2014) 27–32), we prove \( \gamma_{r2}(G) \leq 2\gamma_r(G) \) for every graph \( G \), where \( \gamma_{r2}(G) \) and \( \gamma_r(G) \) denote the 2-rainbow domination number and the weak Roman domination number of \( G \), respectively. We characterize the extremal graphs for this inequality that are \( \{K_4, K_4 – e\} \)-free, and show that the recognition of the \( K_5 \)-free extremal graphs is NP-hard.

For a graph \( H \), let \( \delta_t(H) = \min\{|\bigcup_{i=1}^t N_H(v_i)| : |v_1, \dots, v_t| \text{ are } t \text{ vertices in } H\} \). We show that for a given number \( \epsilon \) and given integers \( p \geq 2 \) and \( k \in \{2, 3\} \), the family of \( k \)-connected Hamiltonian claw-free graphs \( H \) of sufficiently large order \( n \) with \( \delta(H) \geq 3 \) and \( \delta_k(H) \geq t(n + \epsilon)/p \) has a finite obstruction set in which each member is a \( k \)-edge-connected \( K_3 \)-free graph of order at most \( \max\{p/t + 2t, 3p/t + 2t – 7\} \) and without spanning closed trails. We found the best possible values of \( p \) and \( \epsilon \) for some \( t \geq 2 \) when the obstruction set is empty or has the Petersen graph only. In particular, we prove the following for such graphs \( H \):

• (a) For \( k = 2 \) and a given \( t \) (\( 1 \leq t \leq 4 \)), if \( \delta_t(H) \geq \frac{n+1}{3} \) and \( \delta(H) \geq 3 \), then \( H \) is Hamiltonian.
• (b) For \( k = 3 \) and \( t = 3 \), (i) if \( \delta_3(H) \geq \frac{n+9}{10} \), then \( H \) is Hamiltonian; (ii) if \( \delta_2(H) \geq \frac{n+9}{10} \), then either \( H \) is Hamiltonian, or \( H \) can be characterized by the Petersen graph.
• (c) For \( k = 3 \) and \( t = 3 \), (i) if \( \delta_3(H) \geq \frac{n+9}{8} \), then \( H \) is Hamiltonian; (ii) if \( \delta_3(H) \geq \frac{n+6}{9} \), then either \( H \) is Hamiltonian, or \( H \) can be characterized by the Petersen graph.

These bounds on \( \delta_t(H) \) are sharp. Since the number of graphs of orders at most \( \max\{p/t + 2t, 3p/t + 2t – 7\} \) is finite for given \( p \) and \( t \), improvements to (a), (b), or (c) by increasing the value of \( p \) are possible with the help of a computer.

Any dominating set of vertices in a triangle-free graph can be used to specify a graph coloring with at most one color class more than the number of vertices in the dominating set. This bound is sharp for many graphs. Properties of graphs for which this bound is achieved are presented.

A graph \( G \) is quasi-claw-free if it satisfies the property: \( d(x, y) = 2 \) implies there exists \( u \in N(x) \cap N(y) \) such that \( N[u] \subseteq N[x] \cup N[y] \). The matching number of a graph \( G \) is the size of a maximum matching in the graph. In this note, we present a sufficient condition involving the matching number for the Hamiltonicity of quasi-claw-free graphs.

Let \( S \) be an orthogonal polygon and let \( A_1, \ldots, A_n \) represent pairwise disjoint sets, each the connected interior of an orthogonal polygon, \( A_i \subseteq S, 1 \leq i \leq n \). Define \( T = S \setminus (A_1 \cup \ldots \cup A_n) \). We have the following Krasnosel’skii-type result: Set \( T \) is staircase star-shaped if and only if \( S \) is staircase star-shaped and every \( 4n \) points of \( T \) see via staircase paths in \( T \) a common point of \( \text{Ker } S \). Moreover, the proof offers a procedure to select a particular collection of \( 4n \) points of \( T \) such that the subset of \( \text{Ker } S \) seen by these \( 4n \) points is exactly \( \text{Ker } T \). When \( n = 1 \), the number 4 is best possible.

The \( p \)-competition graph \( C_p(D) \) of a digraph \( D = (V, A) \) is a graph with \( V(C_p(D)) = V(D) \), where an edge between distinct vertices \( x \) and \( y \) if and only if there exist \( p \) distinct vertices \( v_1, v_2, \ldots, v_p \in V \) such that \( x \to v_i, y \to v_i \) are arcs of the digraph \( D \) for each \( i = 1, 2, \ldots, p \). In this paper, we prove that double stars \( DS_m \) (\( m \geq 2 \)) are \( p \)-competition graphs. We also show that full regular \( m \)-ary trees \( T_{m,n} \) with height \( n \) are \( p \)-competition graphs, where \( p \leq \frac{m – 1}{2} \).

Let \( G \) be a graph with at least half of the vertices having degree at least \( k \). For a tree \( T \) with \( k \) edges, Loebl, Komlós, and Sós conjectured that \( G \) contains \( T \). It is known that if the length of a longest path in \( T \) (i.e., the diameter of \( T \)) is at most 5, then \( G \) contains \( T \). Since \( T \) is a bipartite graph, let \( \ell \) be the number of vertices in the smaller (or equal) part. Clearly \( 1 \leq \ell \leq \frac{1}{2}(k + 1) \). In our main theorem, we prove that if \( 1 \leq \ell \leq \frac{1}{6}k + 1 \), then the graph \( G \) contains \( T \). Notice that this includes certain trees of diameter up to \( \frac{1}{3}k + 2 \).

If a tree \( T \) consists of only a path and vertices that are connected to the path by an edge, then the tree \( T \) is a caterpillar. Let \( P \) be the path obtained from the caterpillar \( T \) by removing each leaf of \( T \), where \( P = a_1, \ldots, a_r \). The path \( P \) is the spine of the caterpillar \( T \), and each vertex on the spine of \( T \) with degree at least 3 in \( T \) is a joint. It is known that the graph \( G \) contains certain caterpillars having at most two joints. If only odd-indexed vertices on the spine \( P \) are joints, then the caterpillar \( T \) is an odd caterpillar. If the spine \( P \) has at most \( \lceil \frac{1}{2}k \rceil \) vertices, then \( T \) is a short caterpillar. We prove that the graph \( G \) contains every short, odd caterpillar with \( k \) edges.

The decision problems of the existence of a Hamiltonian cycle or of a Hamiltonian path in a given graph, and of the existence of a truth assignment satisfying a given Boolean formula C, are well-known NP-complete problems. Here we study the problems of the uniqueness of a Hamiltonian cycle or path in an undirected, directed or oriented graph, and show that they have the same complexity, up to polynomials, as the problem U-SAT of the uniqueness of an assignment satisfying C. As a consequence, these Hamiltonian problems are NP-hard and belong to the class DP, like U-SAT.

A graph \( G \) is \( k \)-frugal colorable if there exists a proper vertex coloring of \( G \) such that every color appears at most \( k – 1 \) times in the neighborhood of \( v \). The \( k \)-frugal chromatic number, denoted by \( \chi_k(G) \), is the smallest integer \( l \) such that \( G \) is \( k \)-frugal colorable with \( l \) colors. A graph \( G \) is \( L \)-list colorable if there exists a coloring \( c \) of \( G \) for a given list assignment \( L = \{L(v) : v \in V(G)\} \) such that \( c(v) \in L(v) \) for all \( v \in V(G) \). If \( G \) is \( k \)-frugal \( L \)-colorable for any list assignment \( L \) with \( |L(v)| \geq l \) for all \( v \in V(G) \), then \( G \) is said to be \( k \)-frugal \( l \)-list-colorable. The smallest integer \( l \) such that the graph \( G \) is \( k \)-frugal \( l \)-list-colorable is called the \( k \)-frugal list chromatic number, denoted by \( \text{ch}_k(G) \). It is clear that \( \text{ch}_k(G) \geq \left\lceil \frac{\Delta(G)}{k – 1} \right\rceil + 1 \) for any graph \( G \) with maximum degree \( \Delta(G) \). In this paper, we prove that for any integer \( k \geq 4 \), if \( G \) is a planar graph with maximum degree \( \Delta(G) \geq 13k – 11 \) and girth \( g \geq 6 \), then \( \text{ch}_k(G) = \left\lceil \frac{\Delta(G)}{k – 1} \right\rceil + 1; \) and if \( G \) is a planar graph with girth \( g \geq 6 \), then \(\text{ch}_k(G) \leq \left\lceil \frac{\Delta(G)}{k – 1} \right\rceil + 2.\)

In 1987, Alavi, Boals, Chartrand, Erdös, and Oellermann conjectured that all graphs have an ascending subgraph decomposition (ASD). In previous papers, we showed that all tournaments of order congruent to 1, 2, or 3 mod 6 have an ASD. In this paper, we will consider the case where the tournament has order congruent to 5 mod 6.