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.

An \( H \)-decomposition of a graph \( G \) is a partition of the edges of \( G \) into copies isomorphic to \( H \). When the decomposition is not feasible, one looks for the best possible by minimizing: the number of unused edges (leave of a packing), or the number of reused edges (padding of a covering). We consider the \( H \)-decomposition, packing, and covering of the complete graphs and complete bipartite graphs, where \( H \) is a 4-cycle with three pendant edges.

We introduce a new bivariate polynomial
\[
J(G; x, y) := \sum_{W \subseteq V(G)} x^{|W|} y^{|N[W]| – |W|}
\]
which contains the standard domination polynomial of the graph \( G \) in two different ways. We build methods for efficient calculation of this polynomial and prove that there are still some families of graphs which have the same bivariate polynomial.

Let \( G \) be a \( (p, q) \) graph. Let \( f : V(G) \to \{1, 2, \ldots, k\} \) be a map where \( k \) is an integer \( 2 \leq k \leq p \). For each edge \( uv \), assign the label \( |f(u) – f(v)| \). \( f \) is called \( k \)-difference cordial labeling of \( G \) if \( |v_f(i) – v_f(j)| \leq 1 \) and \( |e_f(0) – e_f(1)| \leq 1 \), where \( v_f(x) \) denotes the number of vertices labeled with \( x \), \( e_f(1) \) and \( e_f(0) \) respectively denote the number of edges labeled with 1 and not labeled with 1. A graph with a \( k \)-difference cordial labeling is called a \( k \)-difference cordial graph. In this paper, we investigate 3-difference cordial labeling behavior of slanting ladder, book with triangular pages, middle graph of a path, shadow graph of a path, triangular ladder, and the armed crown.

In this paper, we consider the sequences \( \{F(n, k)\}_{n \geq k} \) (\(k \geq 1\)) defined by\( F(n, k) = (n – 2)F(n – 1, k) + F(n – 1, k – 1), \quad F(n, 1) = \frac{n!}{2}, \quad F(n, n) = 1. \) We mainly study the log-convexity of \( \{F(n, k)\}{n \geq k} \) (\(k \geq 1\)) when \( k \) is fixed. We prove that \( \{F(n, 3)\}{n \geq 3}, \{F(n, 4)\}{n \geq 5}, \) and \( \{F(n, 5)\}{n \geq 6} \) are log-convex. In addition, we discuss the log-behavior of some sequences related to \( F(n, k) \).
\end{abstract}

Let \( G = C_n \oplus C_n \) with \( n \geq 3 \) and \( S \) be a sequence with elements of \( G \). Let \( \Sigma(S) \subseteq G \) denote the set of group elements which can be expressed as a sum of a nonempty subsequence of \( S \). In this note, we show that if \( S \) contains \( 2n – 3 \) elements of \( G \), then either \( 0 \in \Sigma(S) \) or \( |\Sigma(S)| \geq n^2 – n – 1 \). Moreover, we determine the structures of the sequence \( S \) over \( G \) with length \( |S| = 2n – 3 \) such that \( 0 \notin \Sigma(S) \) and \( |\Sigma(S)| = n^2 – n – 1 \).

Let \(G\) be a finite and simple graph with vertex set \(V(G)\). A nonnegative signed Roman dominating function (NNSRDF) on a graph \(G\) is a function \(f:V(G)\to \{-1,1,2\}\) satisfying the conditions that (i) \(\sum_{x\in N[v]}f(x)\ge 0\) for each \(v \in V(G)\), where \(N[v]\) is the closed neighborhood of \(v\) and (ii)every vertex u for which \(f(u)=-1\) has a neighbor v for which \(f(v)=2\). The weight of an NNSRDF \(f\) is \(\omega(f) = \sum_{v\in V(G)} f(v)\). The nonnegative signed Roman domination number \(\gamma_{sR}^{NN} (G)\) of \(G\) is the minimum weight of an NNSRDF \(G\) In this paper, we initiate the study of the nonnegative signed Roman domination number of a graph and we present different bounds on \(\gamma _{sR}^{NN}(G) \ge (8n-12m)/7\). In addition, if \(G\) is a bipartite graph of order \(n\), then we prove that \(\gamma _{sR}^{NN}(G) \ge^\frac{3}{2}(\sqrt{4n+9}-3)-n\), and we characterize the external graphs.