Given a distribution \(D\) of pebbles on the vertices of a graph \(G\), a pebbling move on \(G\) consists of removing two pebbles from a vertex and placing one on an adjacent vertex (the other is discarded). The pebbling number of \(G\), denoted \(f(G)\), is the smallest integer \(k\) such that any distribution of \(k\) pebbles on \(G\) allows one pebble to be moved to any specified vertex via pebbling moves. In this paper, we calculate the \(t\)-pebbling number of the graph \(D_{n,C_{2m}}\). Furthermore, we verify the \(q\)-\(t\)-pebbling number to demonstrate that \(D_{n,C_{2m}}\) possesses the \(2t\)-pebbling property.

Most. of pooling designs are always constructed by the “containment matrix”. But we are interested in considering non-containment
relationship. In [J. Guo, K. Wang, Pooling designs with surprisingly high degree of error correction in a finite vector space, Discrete Appl Math], Guo and Wang gave a construction by the use of non-containment relationship. In this paper, we generalize Guo-Wang’s designs and obtain a new family of pooling designs. Our designs and Guo-Wang’s designs have the same numbers of items and pools,but the error-tolerance property of our designs is better than that of Guo-Wang’s designs.

A \(k\)-edge labeling of a graph \(G\) is a function \(f: E(G) \to \{0, \ldots, k-1\}\). Such a labeling induces a labeling on the vertex set \(V(G)\) by defining \(f(v) := \sum f(e) \pmod{k}\), where the summation is taken over all edges \(e\) incident on \(v\). For an edge labeling \(f\), let \(v_f(i)\) (resp., \(e_f(i)\)) denote the number of vertices (resp., edges) receiving the label \(i\). A graph \(G\) is said to be \(E_k\)-cordial if there exists a \(k\)-edge labeling \(f\) of \(G\)such that \(|v_f(i) – v_f(j)| \leq 1\) and \(|e_f(i) – e_f(j)| \leq 1\) for all \(0 \leq i, j \leq k-1\). A wheel \(W_n\) is the join of the cycle \(C_n\) on \(n\) vertices and \(K_1\). A Helm \(H_n\) is obtained by attaching a pendent edge to each vertex of the cycle of the wheel \(W_n\). We prove that (i) Helms, (ii) one-point unions of helms, and (iii) path unions of helms are \(E_3\)-cordial.

In this paper, we prove that the graphs \(P_n\) (\(n \geq 3\)), \(C_n\) (\(n \geq 3\), \(n \not\equiv 4 \pmod{8}\)), and \(K_n\) (\(n \geq 3\)) are \(E_4\)-cordial graphs. Additionally, we show that every graph of \(\geq 3\) is a subgraph of an \(E_4\)-cordial graph.

In this paper, we study the upper bounds for the \(D(\beta)\)-vertex-distinguishing total-chromatic numbers using the probability method, and obtain: Let \(\Delta\) be the maximum degree of \(G\), then

\[
\chi_{\beta vt}\leq
\left\{
\begin{array}{ll}
16\Delta^{(\beta+1)/(2\Delta+2)}, & \Delta \geq 3,\beta\geq 4\Delta+3; \\
13\Delta^{(\beta+4)/4} , & \Delta\geq 4,\beta\geq 5;\\
10\Delta^2, & \Delta \geq 3, 2 \leq \beta \leq 4.
\end{array}
\right.
\]

Given a tournament \(T = (V, A)\), a subset \(X\) of \(V\) is an interval of \(T\) provided that for any \(a, b \in X\) and \(x \in V \setminus X\), \((a, x) \in A\) if and only if \((b, x) \in A\). For example, \(\emptyset\), \(\{x\}\) (\(x \in V\)), and \(V\) are intervals of \(T\), called trivial intervals. A two-element interval of \(T\) is called a duo of \(T\). Tournaments that do not admit any duo are called duo-free tournaments. A vertex \(x\) of a duo-free tournament is \(d\)-critical if \(T – x\) has at least one duo. In 2005, J.F. Culus and B. Jouve [5] characterized the duo-free tournaments, all of whose vertices are d-critical, called tournaments without acyclic interval. In this paper, we characterize the duo-free tournaments that admit exactly one non-d-critical vertex, called (-1)-critically duo-free tournaments.

The toughness, as the parameter for measuring stability and vulnerability of networks, has been widely used in computer communication
networks and ontology graph structure analysis. A graph \(G\) is called a fractional \((a, b, n)\)-critical deleted graph if after deleting any \(n\) vertices from \(G\), the resulting graph is still a fractional \((a, b)\)-deleted graph. In this paper,we study the relationship between toughness and fractional \((a, b, n)\)-critical deleted graph. A sufficient condition for a graph G to be a fractional \((a, b, n)\)-critical deleted graph is determined.

The Classification Problem is the problem of deciding whether a simple graph has chromatic index equal to \(\Delta\) or \(\Delta + 1\), where \(\Delta\) is the maximum degree of the graph. It is known that deciding if a graph has chromatic index equal to \(4\) is \(NP\)-complete. A split graph is a graph whose vertex set admits a partition into a stable set and a clique. The chromatic indexes for some subsets of split graphs, such as split graphs with odd maximum degree and split-indifference graphs, are known. However, for the general class, the problem remains unsolved. In this paper, we exhibit a new subset of split graphs with even maximum degree that have chromatic index equal to \(\Delta\). Moreover, we present polynomial-time algorithms to perform an edge-coloring and to recognize these graphs.

Let \(K_4^-\) be the graph obtained from \(K_4\) by deleting one edge. A graph \(G\) is called \(K_4^-\)-free if it does not contain \(K_4^-\) as a subgraph. K. Kawarabayashi showed that a \(K_4^-\)-free \(k\)-connected graph has a \(k\)-contractible edge if \(k\) is odd. Furthermore, when \(k\) is even, K. Ando et al. demonstrated that every vertex of a \(K_4^-\)-free contraction critical \(k\)-connected graph is contained in at least two triangles. In this paper, we extend Kawarabayashi’s result and obtain a new lower bound on the number of \(k\)-contractible edges in a \(K_4^-\)-free \(k\)-connected graph when \(k\) is odd. Additionally, we provide characterizations and properties of \(K_4^-\)-free contraction critical \(k\)-connected graphs and prove that such graphs have at least \(\frac{2|G|}{k-1}\) vertices of degree \(k\).

Let \(D\) be a directed graph with \(n\) vertices and \(m\) edges. A function \(f: V(D) \to \{1, 2, 3, \ldots, k\}\), where \(k \leq n\), is said to be a harmonious coloring of \(D\) if for any two edges \(xy\) and \(uv\) of \(D\), the ordered pair \((f(x), f(y)) \neq (f(u), f(v))\). If the pair \((i, i)\) is not assigned, then \(f\) is said to be a proper harmonious coloring of \(D\). The minimum \(k\) is called the proper harmonious coloring number of \(D\). We investigate the proper harmonious coloring number of various graphs, including unidirectional paths, unicycles, inward-spoken (outward-spoken) wheels, \(n\)-ary trees of different levels, and others.

A vertex subset \(S\) of a digraph \(D = (V, A)\) is called an out-dominating (resp.,in-dominating) set of \(D\) if every vertex in \(V – S\) is adjacent from (resp., to) some vertex in \(S\). The out-domination (resp., in-domination) number of \(D\), denoted by \(\gamma^+(D)\) (resp.,\(\gamma^-(D)\)), is the minimum cardinality of an out-dominating (resp., in-dominating) set of \(D\). In 1999, Chartrand et al. proved that \(\gamma^+(D) + \gamma^-(D) \leq \frac{4n}{3}\) for every digraph \(D\) of order \(n\) with no isolated vertices. In this paper, we determine the values of \(\gamma^+(D) + \gamma^-(D)\) for rooted trees and connected contrafunctional digraphs \(D\), based on which we show that \(\gamma^+(D) + \gamma^-(D) \leq \frac{(2k+2)n}{2k+1}\) for every digraph \(D\) of order \(n\) with minimum out-degree or in-degree no less than \(1\), where \(2k + 1\) is the length of a shortest odd directed cycle in \(D\). Our result partially improves the result of Chartrand et al. In particular, if \(D\) contains no odd directed cycles, then \(\gamma^+(D) + \gamma^-(D) \leq n\).

Given graphs \(G\) and \(H\), an \(H\)-decomposition of \(G\) is a partition of the edge set of \(G\) such that each part is either a single edge or forms a graph isomorphic to \(H\). Let \(\gamma_H(n)\) denote the smallest number \(k\) such that any graph \(G\) of order \(n\) admits an \(H\)-decomposition with at most \(k\) parts. Here, we study the case when \(H = C_7\), the cycle of length \(7\), and prove that \(\gamma_{C_7}(n) = \left\lceil \frac{nZ^2}{4} \right\rceil\) for all \(n \geq 10\).

Given a (directed) graph \(G = (V, A)\), a subset \(X\) of \(V\) is an interval of \(G\) provided that for any \(a, b \in X\) and \(x \in V – X\), \((a, x) \in A\) if and only if \((b, x) \in A\) and \((x, a) \in A\)if and only if \((x, b) \in A\). For example, \(\emptyset\), \(\{x\}\) (\(z \in V\)), and \(V\) are intervals of \(G\), called trivial intervals. A graph, all of whose intervals are trivial, is indecomposable; otherwise, it is decomposable. A vertex \(x\) of an indecomposable graph is critical if \(G – x\) is decomposable. In 1998, J.H. Schmerl and W.T. Trotter characterized the indecomposable graphs, all of whose vertices are critical, called critical graphs. In this article, we characterize the indecomposable graphs that admit a single non-critical vertex, which we term (-1)-critical graphs, answering a question posed by Y. Boudabbous and P. Ille in a recent article studying critical vertices in indecomposable graphs.

Let \(G\) be a graph with minimum degree \(\delta(G)\). R.P. Gupta proved two interesting results: 1) A bipartite graph \(G\) has a 5-edge-coloring in which all 6 colors appear at each vertex. 2) If \(G\) is a simple graph with \(\delta(G) > 1\), then \(G\) has a \((\delta – 1)\)-edge-coloring in which all \((\delta – 1)\) colors appear at each vertex. Let \(t\) be a positive integer. In this paper, we extend the first result by showing that for every bipartite graph, there exists a \(t\)-edge coloring such that at each vertex \(v\), \(\min\{t, d(v)\}\) colors appear. Additionally, we demonstrate that if \(G\) is a graph, then the edges of \(G\) can be colored using \(t\) colors, where for each vertex \(v\), the number of colors appearing at \(v\) is at least \(\min\{t, d(v) – 1\}\), generalizing the second result.

The Zarankiewicz number \(z(m, n; s, t)\) is the maximum number of edges in a subgraph of \(K_{m,n}\) that does not contain \(K_{s,t}\) as a subgraph. The \emph{bipartite Ramsey number} \(b(n_1, \ldots, n_k)\) is the least positive integer \(b\) such that any coloring of the edges of \(K_{b,b}\) with \(k\) colors will result in a monochromatic copy of \(K_{n_i,n_i}\) in the \(i\)-th color, for some \(i\), \(1 \leq i \leq k\). If \(n_i = m\) for all \(i\), we denote this number by \(b_k(m)\). In this paper, we obtain the exact values of some Zarankiewicz numbers for quadrilaterals (\(s = t = 2\)), and derive new bounds for diagonal multicolor bipartite Ramsey numbers avoiding quadrilaterals. Specifically, we prove that \(b_4(2) = 19\) and establish new general lower and upper bounds on \(b_k(2)\).

Given non-negative integers \(r\), \(s\), and \(t\), an \({[r, s, t]-coloring}\) of a graph \(G = (V(G), E(G))\) is a function \(c\) from \(V(G) \cup E(G)\) to the color set \(\{0, 1, \ldots, k-1\}\) such that \(|c(v_i) – c(v_j)| \geq r\) for every two adjacent vertices \(v_i\), \(v_j\), \(|c(e_i) – c(e_j)| \geq s\) for every two adjacent edges \(e_i\), \(e_j\), and \(|c(v_i) – c(e_j)| \geq t\) for all pairs of incident vertices \(v_i\) and edges \(e_j\). The [\(r\), \(s\), \(t\)]-chromatic number \(\chi_{r,s,t}(G)\) is the minimum \(k\) such that \(G\) admits an [\(r\), \(s\), \(t\)]-coloring. In this paper, we examine [\(r\), \(s\), \(t\)]-chromatic numbers of fans for every positive integer \(r\), \(s\), and \(t\).

A new hemisystem of the generalized quadrangle \(\mathcal{H}(3, 49)\) admit-
ting the linear group \(PSL_2(7)\) has been found.

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.

A cyclic edge-cut of a graph \(G\) is an edge set whose removal separates two cycles. If \(G\) has a cyclic edge-cut, it is said to be cyclically separable. For a cyclically separable graph \(G\), the cyclic edge-connectivity \(c\lambda(G)\) is the cardinality of a minimum cyclic edge-cut of \(G\). Let \(\zeta(G) = \min\{w(X) \mid X \text{ induces a shortest cycle in } G\}\), where \(w(X)\) is the number of edges with one end in \(X\) and the other end in \(V(G) – X\). A cyclically separable graph \(G\) with \(c\lambda(G) = \zeta(G)\) is said to be cyclically optimal. In this work, we discuss the cyclic edge connectivity of regular double-orbit graphs. Furthermore, as a corollary, we obtain a sufficient condition for mixed Cayley graphs, introduced by Chen and Meng \([3]\), to be cyclically optimal.

Let \(G = (V, E)\) be a graph of order \(p\) and size \(q\). It is known that if \(G\) is a super edge-magic graph, then \(q \leq 2p – 3\). Furthermore, if \(G\) is super edge-magic and \(q = 2p – 3\), then the girth of \(G\) is \(3\). Additionally, if the girth of \(G\) is at least \(4\) and \(G\) is super edge-magic, then \(q \leq 2p – 5\). In this paper, we demonstrate that there are infinitely many graphs that are super edge-magic, have girth \(5\), and \(q = 2p – 5\). Hence, we conclude that for super edge-magic graphs of girths \(4\) and \(5\), the size is upper bounded by twice the order of the graph minus \(5\), and this bound is tight.

The game of Nim as played on graphs was introduced in \([3]\) and extended in \([4]\) by Masahiko Fukuyama. His papers detail the calculation of Grundy numbers for graphs under specific circumstances. We extend these results and introduce the strategy for even cycles. This paper examines a more general class of graphs by restricting the edge weight to one. We provide structural conditions for which there exist a winning strategy. This yields the solution for the complete graph.

Given positive integers \(j\) and \(k\) with \(j \geq k\), an {L\((j,k)\)-labeling} of a graph \(G\) assigns nonnegative integers to \(V(G)\) such that adjacent vertices’ labels differ by at least \(j\), and vertices distance two apart have labels differing by at least \(k\). The span of an L\((j,k)\)-labeling is the difference between the maximum and minimum assigned integers. The \(\lambda_{j,k}\)-number of \(G\) is the minimum span over all L\((j,k)\)-labelings of \(G\). This paper investigates the \(\lambda_{j,k}\)-numbers of Cartesian products of three complete graphs.

An \(L(2,1)\)-labeling of a graph \(G = (V, E)\) is a function \(f\) from its vertex set \(V\) to the set of nonnegative integers such that \(|f(x) – f(y)| \geq 2\) if \(xy \in E\) and \(|f(x) – f(y)| \geq 1\) if \(x\) and \(y\) are at distance two apart. The span of an \(L(2,1)\)-labeling \(f\) is the maximum value of \(f(x)\) over all \(x \in V\). The \emph{\(L(2,1)\)-labeling number} of \(G\), denoted \(\lambda(G)\), is the least integer \(k\) such that \(G\) has an \(L(2,1)\)-labeling of span \(k\). Chang and Kuo [1996, SIAM J. Discrete
Mathematics, Vol 9, No. 2, pp. \(309 — 316]\) proved that \(\lambda(G) \leq 2\Delta(G)\) and conjectured that \(\lambda(G) \leq \Delta(G) + \omega(G)\) for a strongly chordal graph \(G\), where \(\Delta(G)\) and \(\omega(G)\) are the maximum degree and maximum clique size of \(G\), respectively. In this paper, we propose an algorithm for \(L(2,1)\)-labeling a block graph \(G\) with \(\Delta(G) + \omega(G) + 1\) colors. As block graphs are strongly chordal graphs, our result proves Chang and Kuo’s conjecture for block graphs. We also obtain better bounds of \(\lambda(G)\) for some special subclasses of block graphs. Finally, we investigate finding the exact value of \(\lambda(G)\) for a block graph \(G\).

In terms of Sears’ transformation formula for \(_4\phi_3\)-series, we provide standard proofs of a summation formula for \(_4\phi_3\)-series due to Andrews [Andrews, Adv. Appl. Math. \(46 (2011), 15-24]\) and another summation formula for \(_4\phi_3\)-series conjectured in the same paper. Meanwhile, several other related results are also derived.

In the book embedding of an ordered set, the elements of the set are embedded along the spine of a book to form a linear extension. The pagenumber (or stack number) is the minimum number of pages needed to draw the edges as simple curves such that
edges drawn on the same page do not intersect. The pagenumber problem for ordered sets is known to be NP-complete, even if the order of the elements on the spine is-fixed. In this paper, we investigate this problem for some classes of ordered sets. We provide an efficient algorithm for embedding bipartite interval orders in a book with the minimum number of pages. We also give an upper bound for the pagenumber of general bipartite ordered sets and the pagenumber of complete multipartite ordered sets. At the end of this paper we discuss the effect of a number of diagram operations on the pagenumber of ordered sets. We give an answer to an open question by Nowakowski and Parker \([7]\) and we provide several known and new open questions we consider worth investigating.

Let \(\Gamma\) be a \(d\)-bounded distance-regular graph with diameter \(d \geq 2\).In this paper, we give some counting formulas of subspaces in \(\Gamma\) and construct an authentication code with perfect. secrecy.

We determine the full friendly index sets of spiders and disprove a conjecture by Lee and Salehi \([4]\) that the friendly index set of a tree forms an arithmetic progression.

Let \(k\) be a positive integer and \(G = (V(G), E(G))\) a graph. A subset \(S \subseteq V(G)\) is a \(k\)-dominating set if every vertex of \(V(G)- S\) is adjacent to at least \(k\) vertices of \(S\). The \(k\)-domination number \(\gamma_k(G)\) is the minimum cardinality of a \(k\)-dominating set of \(G\). A graph \(G\) is called \(\gamma_k\)-stable if \(\gamma_{\bar{k}}(G – e) = \gamma_{{k}}(G)\) for every edge \(e\) of \(E(G)\). We first provide a necessary and sufficient condition for \(\gamma_{\bar{k}}\)-stable graphs. Then, for \(k \geq 2\), we offer a constructive characterization of \(\gamma_{\bar{k}}\)-stable trees.

The zero-divisor graph of a commutative semigroup with zero is a graph whose vertices are the nonzero zero-divisors of the semigroup, with two distinct vertices joined by an edge if their product in the semigroup is zero. In this paper, we provide formulas to calculate the numbers of non-isomorphic zero-divisor semigroups corresponding to star graphs \(K_{1,m}\), two-star graphs \(T_{m,n}\), and windmill graphs, respectively.