A graph is termed Laplacian integral if its Laplacian spectrum comprises integers. Let \(\theta(n_1, n_2, \ldots, n_k)\) be a generalized \(\theta\)-graph (see Figure 1). Denote by \(\mathcal{G}_{k-1}\) the set of \((k-1)\)-cyclic graphs, each containing some generalized \(\theta\)-graph \(\theta(n_1, n_2, \ldots, n_{k})\) as its induced subgraph. In this paper, we establish an edge subdividing theorem for Laplacian eigenvalues of a graph (Theorem 2.1), from which we identify all Laplacian integral graphs in the class \(\mathcal{G}_{ k-1}\) (Theorem 3.2).

We determine the Ramsey numbers \(R(S_{2,m} K_{2, q})\) for \(m \in \{3, 4, 5\}\) and \(q \geq 2\). Additionally, we obtain \(R(tS_{2, 3}, sK_{2, 2})\) and \(R(S_{2, 3}, sK_{2, 2})\) for \(s \geq 2\) and \(t \geq 1\). Furthermore, we also establish \(R(sK_2, \mathcal{H})\), where \( \mathcal{H}\) is the union of graphs with each component isomorphic to the connected spanning subgraph of \(K_{s} + C_n\), for \(n \geq 3\) and \(s \geq 1\).

For a given set \(M\) of positive integers, a well known problem of Motzkin asks for determining the maximal density \(\mu(M)\) among sets of nonnegative integers in which no two elements differ by an element of \(M\). The problem is completely settled when \(|M| \leq 2\), and some partial results are known for several families of \(M\) for \(|M| \geq 3\),including the case where the elements of \(M\) are in arithmetic progression. We resolve the problem in case of geometric progressions and geometric sequences.

A new Turán-type problem on distances of graphs was introduced by Tyomkyn and Uzzell. In this paper, we focus on the case of distance two. We show that for any positive integer \(n\), a graph \(G\) on \(n\) vertices without three vertices pairwise at distance \(2\) has at most \(\frac{(n-1)^2}{4} + 1\) pairs of vertices at distance \(2\), provided \(G\) has a vertex \(v \in V(G)\) whose neighbors are covered by at most two cliques. This partially answers a conjecture of Tyomkyn and Uzzell [Tyomkyn, M.,Uzzell, A.J.: A new Turdn-type problem on distances of graphs. Graphs Combin. \(29(6), 1927-1942 (2012)\)]..

In the first installment of this series, we proved that for every integer \(a \geq 3\) and every \(m \geq 2a^2 – a + 2\), the \(2\)-color Rado number of \[x_1+x_2+\ldots+x_{m-1}=ax_m\]. is \(\lceil \frac{m-1}{a} \lceil \frac{m-1}{a} \rceil\rceil \). Here, we obtain the best possible improvement of the bound on \(m\). Specifically, we prove that if \(3|a\), then the \(2\)-color Rado number is \(\lceil \frac{m-1}{a} \lceil\frac{m-1}{a} \rceil\rceil \) when \(m \geq 2a + 2\) but not when \(m = 2a+1\), and that if \(3 \nmid\) is composite, then the \(2\)-color Rado number is \(\lceil \frac{m-1}{a}\lceil\frac{m-1}{a}\rceil \rceil \) when \(m \geq 2a + 2\) but not when \(m = 2a + 1\). Additionally, we determine the \(2\)-color Rado number for all \(a \geq 3\) and \(m \geq \frac{a}{3} + 1\).

Let \(G = (V, E)\) be a graph without isolated vertices. A set \(D \subseteq V\) is a paired-dominating set if \(D\) is a dominating set of \(G\) and the induced subgraph \(G[D]\) has a perfect matching. In this paper, we provide a characterization for block graphs with a unique minimum paired-dominating set. Furthermore, we also establish a constructive characterization for trees with a unique minimum paired-dominating set.

Estimates of the choice numbers and the Ohba numbers of the complete multipartite graphs \(K(m, n, 1, \ldots, 1)\) and \(K(m, n, 2, \ldots, 2)\) are provided for various values of \(m \geq n \geq 1\). The Ohba number of a graph \(G\) is the smallest integer \(n\) such that \(\operatorname{ch}(G \vee K_n) = \chi(G \vee K_n)\).

Kuratowski proved that a finite graph embeds in the plane if it does not contain a subdivision of either \(K_5\) or \(K_{3,3}\), known as Kuratowski subgraphs. Glover posed the question of whether a finite minimal forbidden subgraph for the Klein bottle can be expressed as the union of three Kuratowski subgraphs, such that the union of each pair of these fails to embed in the projective plane. We demonstrate that this holds true for all finite minimal forbidden graphs for the Klein bottle with connectivity \(< 3\).

The partition theorem of connected graphs was established in \(1985\) and it is very useful in graphical enumeration. In this paper, we generalize th partition theorem from connected graphs to weakly connected digraphs. Applying these two partition theorems, we obtain the recursive formulas for enumerations of labeled connected (even) digraphs, labeled rooted connected (even) digraphs whose roots have a given number of blocks, and labeled connected \(d\)-cyclic (\(d \geq 0\)) (directed) graphs, etc. Moreover, a new proof of the counting formula for labeled trees (Cayley formula) is given.

In this paper, we introduce a special kind of graph homomorphisms namely semi-locally-surjective graph homomorphisms. We show some relations between semi-locally-surjective graph homomorphisms and colorful colorings of graphs. Then, we prove that for each natural number \(k\), the Kneser graph KG\((2k + 1, k)\) is \(b\)-continuous. Finally, we present some special conditions for graphs to be \(b\)continuous.