A complete bipartite graph with the number of two partitions s and t is denoted by \(K{s,t}\). For a positive integer s and two bipartite graphs G and H, the s-bipartite Ramsey number \(BR_s (G, H)\) of G and H is the smallest integer t such that every 2-coloring of the edges of \(K_{s,t}\) contains the a copy of G with the first color or a copy of H with the second color. In this paper, by using an integer linear program and the solver Gurobi Optimizer 8.0, we determine all the exact values of \(BR_s (K_{2,3}, K_{3,3})\) for all possible \(s\). More precisely, we show that \(BR_s (K_{2,3}, K_{3,3})=13\) for \(s\) \(\in\) {8,9}, \(BR_s (K_{2,3}, K_{3,3})=12\) for \(s \in \{10,11\}\), \(BR_s (K_{2,3}, K_{3,3})=10\) for \(s = 12\), \(BR_s (K_{2,3}, K_{3,3})=8\) for \(s \in \{13,14\}\), \(BR_s (K_{2,3}, K_{3,3})=6\) for \(s \in \{15,16,…, 20\}\), and \(BR_s (K_{2,3}, K_{3,3})=4\) for s ≥ 21. This extends the results presented in [Zhenming Bi, Drake Olejniczak and Ping Zhang, “The s-Bipartite Ramsey Numbers of Graphs \(K_{2,3}\) and \(K_{3,3}\)” , Journal of Combinatorial Mathematics and Combinatorial Computing 106, (2018) 257-272].

In this work we construct many new examples of maximal partial line spreads in \(PG(3, q), q\) even. We do this by giving a suitable representation of \(PG(3, q)\) in the non-singular quadric \(Q(4, q)\) of \(PG(4, q)\). We prove the existence of maximal partial line spreads of sizes \(q^2- q + 1 – \bar{t}\bar{z}\), for every pair \((\bar{t},\bar{z}) \in P_1 \cup P_2\), where \(P_1\) and \(P_2\) are the pair sets \(P_1=\{(t,z)\in\mathbb{Z}\times\mathbb{Z}:\frac{q}{2}-2\leq t\leq q-3,0\leq z\leq\frac{q}{2}-2\}\) and \(P_2=\{(t,z)\in\mathbb{Z}\times\mathbb{Z}:0\leq t\leq \frac{q}{2}-3,0\leq z\leq{q}-1\}\), for \(q \geq 8\).

Low-Density Parity-Check (LDPC) codes have low linear decoding complexity, which is a kind of good codes with excellent performance. Therefore, LDPC codes have great research value. This article is based on vector space over finite field as a theoretical tool by the inclusive relation of vector subspaces to construct protograph, and then constructs the LDPC codes with larger girth based on protograph by the modified progressive edge growth(M-PEG) algorithm, and utilize the related knowledge, such as Anzahl theorem in vector space, determines the code length, code rate and code word number of the LDPC codes. Moreover, the LDPC codes constructed are compared with the existing codes, and the constructed codes are better than some existing ones.

Let G be a graph and a1,…, as be positive integers. The expression \(G\, \underrightarrow{v}(a_1,…,a_s)\) means that for every coloring of the vertices of G in s colors there exists \(i \in {1,…, s}\) such that there is a monochromatic \(a_i\)-clique of color i. The vertex Folkman numbers \(F_v(a_1, …, a_s; q)\) are defined by the equality:
\[F_v(a_1, …, a_s; q) = min\{|V(G)| : G\, \underrightarrow{v}(a_1,…,a_s)\,\, and K_q \nsubseteq G\}\].
Let \(m = \sum^s_{i=1} (a_i – 1) + 1\). It is easy to see that \(F_v(a_1,…, a_s; q) = m\) if \(q \geq m + 1\). In [11] it is proved that \(F_v(a_1, …, a_s;m) = m +max {a_1,…, a_s}\). We know all the numbers \(F_v(a_1,…, a_s; m – 1)\) when \(max {a_1,..,a_s} ≤ 5\) and none of these numbers is known if \(max{a_1, …, a_s} ≥ 6\). In this paper we present computer algorithms, with the help of which we compute all Folkman numbers \(F_v (a_1, .., a_s;m – 1)\) when \(max{a_1,.., a_s} = 6\). We also prove that \(F_v (2,2,7;8) = 20\) and obtain new bounds on the numbers \(F_v(a_1, …, a_s;m – 1)\) when \(max(a_1, …, a_s) = 7\).

Let G be an edge-colored connected graph. For vertices u and v of G, a shortest u – v path P in G is a u – u geodesic and P is a proper u – u geodesic if no two adjacent edges in P are colored the same. An edge coloring of a connected graph G is called a proper k-geodesic coloring of G for some positive integer k if for every two nonadjacent vertices u and v of G, there exist at least k internally disjoint proper u – u geodesics in G. The minimum number of the colors required in a proper k-geodesic coloring of G is the strong proper k-connectivity \(spc_k(G)\) of G. Sharp lower bounds are established for the strong proper k-connectivity of complete bipartite graphs \(K_{r,s}\) for all integers k, r, s with 2 ≤ k ≤ r ≤ s and it is shown that the strong proper 2-connectivity of \(K_{r,s}\) is \(spc_2(K_{r,s}) = \left\lceil ^{r-1}\sqrt{s} \right\rceil\) for 2 ≤ r ≤ s.

Suppose \(G = (V, E)\) is a simple graph and \(f: (V\cup E) → {1,2,…, k}\) is a proper total k-coloring of G. Let \(C(u) = {f(u)} \cup {f(uv): uv \in E(G)}\) for each vertex u of G. The coloring f is said to be an adjacent vertex-distinguishing total coloring of G if \(C(u) \neq C(v)\) for every \(uv \in E(G)\). The minimum k for which such a chromatic number of G, and is denoted by \(X_at (G)\). This paper considers three types of cubic graphs: a specific family of cubic hasmiltonian graphs, snares and Generalized Petersen graphs. We prove that these cubic graphs have the same adjacent vertex-distinguishing total chromatic number 5. This is a step towards a problem that whether the bound \(X_at (G) ≤ 6\) is sharp for a graph G with maximum degree three.

An Italian dominating function (IDF) on a graph G = (V,E) is a function f: V → {0,1,2} satisfying the property that for every vertex \(v \in V\), with f(v) = 0, \(\sum_{u \in N_{(v)}}f(u)\geq2\). The weight of an IDF f is the value \(w(f) = f(V) = \sum_{u \in V}f(u)\). The minimum weight of an IDF on a graph G is called the Italian domination number of G, denoted by \(\gamma_I(G)\). For a graph G = (V,E), a double Roman dominating function (or just DRDF) is a function f: V → {0, 1, 2,3} having the property that if \(f(v) = O\) for a vertex \(u\), then \(u\) has at least two neighbors assigned 2 under for one neighbor assigned 3 under f, and if \(f(v) = 1\), then u has at least one neighbor with f(w) ≥ 2. The weight of a DRDF f is the sum \(f(V) = \sum_{u \in V}f(v)\), and the minimum weight of a DRDF on G is the double Roman domination number oi G, denoted by \(\gamma_{dR}(G)\). In this paper we show that \(\gamma_dR(G)/2 ≤ \gamma_I(G) ≤ 2\gamma_dR(G)/3\), and characterize all trees T with \(\gamma_I(T) = 2\gamma_dR (T)/3\).

This paper mainly presents a construction of LDPC codes based on symplectic spaces. By two subspaces of type (m, r) to produce a subspace of type (m + 1,r) or (m + 1,r + 1) in \(\mathbb{F}^{2v}\) , we use all subspaces of type (m,r) to mark rows and all subspaces of type (m + 1, r) and (m + 1, r + 1) to mark columns of check matrix H. A construction of LDPC codes has been given based on symplectic spaces. As a special case, we use all subspaces of type (1,0) to mark rows and all subspaces of type (2,0) and (2,1) to mark columns of check matrix \(H_1\), in \(\mathbb{F}^4_q\), the cycles of length 6 of \(H_1\), is further discussed.

We introduce and study a subring SC of \(\mathbb{Z}SL_2 (\mathbb{F}_q)\) obtained by summing elements of \(SL_2 (\mathbb{F}_q)\) according to their support. The ring SC can be used for the construction of several association schemes.

Randic index and geometric-arithmetic index are two important chemical indices. In this paper, we give the generalized Nordhaus-Gaddum-type inequalities for the two kinds of chemical indices.

Graceful graphs were first studied by Rosa [17]. A graceful labeling \(f\) of a graph G is a one-to-one map from the set of vertices of \(G\) to the set {0.1,., |E(G)|}. where for edges \(xy\), the induced edge labels |f(x) – f (y)| form the set {1,2,., |E(G)|, with no label repeated. In this paper, we investigate the set of labels taken by the central vertex of the star in the graph \(K_{1.m-1} \oplus C_n\), for each graceful labeling. We also study gracefulness of certain unicyclic graphs where paths \(P_3, P_2\) are pendant at vertices of the cycle. For these unicyclic graphs, the deletion of any edge of the cycle does not result in a caterpillar.

An edge-magic total labeling of a graph \(G = (V, E)\) is an assignment of integers \(1,2, …,|V|+|E|\) to the vertices and edges of the graph so that the sum of the labels of any edge \(uv\) and the labels on vertices \(u\) and \(v\) is constant. It is known that the class of complete graphs on \(n\) vertices, \(K_n\), are not edge magic for any n ≥ 7. The edge magic number \(M_E(K_n)\) is defined to be the minimum number t of isolated vertices such that \(K_n \cup tK_1\), is edge magic. In this paper we show that, for n ≥ 10, \(M_E(K_n) ≤ f_{n+1} + 57 – \frac{n^2+n}{2} where \(f_i\) is the \(i^{th}\) Fibonacci number. With the aid of a computer, we also show that \(M_E(K_7) = 4,\, M_E(K_8) = 10\), and \(M_E(K_9) = 19\), answering several questions posed by W. D. Wallis.

A cograph is a simple graph that does not contain an induced path on 4 vertices. A graph G is \(k_{-e} colorable\) if the vertices of G can be colored in k colors such that, for each color, the subgraph induced by the vertices assigned the color is a cograph. A graph that is \(k_{-e} colorable\) and is not \((k-1)_{-e} colorable\), but becomes \((k-1)_{-e} colorable\) whenever a vertex is removed, is called \(k_{-e} critical\) graph. Two general constructions are provided that produce critical graphs from color critical graphs and hypergraphs. A characterization is also given for when a general composition of graphs (path-joins) is critical. The characterization is used to provide an upper bound for the fewest number of vertices of a \(k_{-e} critical\) graph.

We survey Dudeney’s round table problem which asks for a set of Hamilton cycles in the complete graph that uniformly covers the 2-paths of the graph. The problem was proposed about one hundred years ago but it is still unsettled. We mention the history of the problem, known results, gener-alizations, related designs, and some open problems.

Constructions are given for non-cubic, edge-critical Hamilton laceable bigraphs with 3m edges on 2m vertices for all m ≥ 4. The significance of this result is that it shows the conjectured hard upper bound of 3m edges for edge-critical bigraphs on 2m vertices is populated by both cubic and non-cubic cases for all m. This is unlike the situation for the hard 3m-edge lower bound for edge-stable bigraphs where the bound is populated exclusively by cubics.

In this paper, we identify LOW and OLW graphs, find the minimum \(\lambda\) for decomposition of \(\lambda k_n\), into these graphs, and show that for all viable values of \(\lambda\), the necessary conditions are sufficient for LOW- and OLW-decompositions using cyclic decompositions from base graphs.

A maximal independent set is an independent set that is not a proper subset of any other independent set. A twinkle graph W is a connected unicyclic graph with cycle C such that W – x is disconnected for any \(x \in V(C)\). In this paper, we determine the largest number of maximal independent sets and characterize those extremal graphs achieving these values among all twinkle graphs. Using the results on twinkle graphs, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs with at most one cycle.