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\).

There are \(267\) nonisomorphic groups of order \(64\). It was known that \(259\) of these groups admit \((64, 28, 12)\) difference sets. In \([4]\), the author found all \((64, 28, 12)\) difference sets in \(111\) groups. In this paper, we find all \((64, 28, 12)\) difference sets in all the remaining groups of order \(64\) that admit \((64, 28, 12)\) difference sets. Also, we find all nonisomorphic symmetric \((64, 28, 12)\) designs that arise from these difference sets. We use these \((64, 28, 12)\) difference sets to construct all \((64, 27, 10, 12)\) and \((64, 28, 12, 12)\) partial difference sets. Finally, we examine the corresponding strongly regular graphs with parameters \((64, 27, 10, 12)\) and \((64, 28, 12, 12)\).

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.