For two graphs G1 and G2, the connected size Ramsey number ˆrc(G1,G2) is the smallest number of edges of a connected graph G such that if each edge of G is colored red or blue, then G contains either a red copy of G1 or a blue copy of G2. Let nK2 be a matching with n edges and P4 a path with four vertices. Rahadjeng, Baskoro, and Assiyatun [Procedia Comput. Sci. 74 (2015), 32-37] conjectured that ˆrc(nK2,P4)=3n−1 if n is even, and ˆrc(nK2,P4)=3n otherwise. We verify the conjecture in this short paper.
Citation: Yixin Zhang, Yanbo Zhang, Hexuan Zhi. A proof of a conjecture on matching-path connected size Ramsey number[J]. AIMS Mathematics, 2023, 8(4): 8027-8033. doi: 10.3934/math.2023406
[1] | Xiaohong Chen, Baoyindureng Wu . Gallai's path decomposition conjecture for block graphs. AIMS Mathematics, 2025, 10(1): 1438-1447. doi: 10.3934/math.2025066 |
[2] | Sitta Alief Farihati, A. N. M. Salman, Pritta Etriana Putri . Rainbow connection numbers of some classes of s-overlapping r-uniform hypertrees with size t. AIMS Mathematics, 2024, 9(7): 18824-18840. doi: 10.3934/math.2024916 |
[3] | Shahid Zaman, Fouad A. Abolaban, Ali Ahmad, Muhammad Ahsan Asim . Maximum H-index of bipartite network with some given parameters. AIMS Mathematics, 2021, 6(5): 5165-5175. doi: 10.3934/math.2021306 |
[4] | Chunyan Qin, Xiaoxia Zhang, Liangchen Li . Z3-connectivity of graphs with independence number at most 3. AIMS Mathematics, 2023, 8(2): 3204-3209. doi: 10.3934/math.2023164 |
[5] | Jianping Li, Leshi Qiu, Jianbin Zhang . Proof of a conjecture on the ϵ-spectral radius of trees. AIMS Mathematics, 2023, 8(2): 4363-4371. doi: 10.3934/math.2023217 |
[6] | Christophe Ndjatchi, Joel Alejandro Escareño Fernández, L. M. Ríos-Castro, Teodoro Ibarra-Pérez, Hans Christian Correa-Aguado, Hugo Pineda Martínez . On the packing number of 3-token graph of the path graph Pn. AIMS Mathematics, 2024, 9(5): 11644-11659. doi: 10.3934/math.2024571 |
[7] | Linyu Li, Jun Yue, Xia Zhang . Double total domination number of Cartesian product of paths. AIMS Mathematics, 2023, 8(4): 9506-9519. doi: 10.3934/math.2023479 |
[8] | Yinkui Li, Jiaqing Wu, Xiaoxiao Qin, Liqun Wei . Characterization of Q graph by the burning number. AIMS Mathematics, 2024, 9(2): 4281-4293. doi: 10.3934/math.2024211 |
[9] | Sakander Hayat, Bagus Imanda, Asad Khan, Mohammed J. F. Alenazi . Three infinite families of Hamilton-connected convex polytopes and their detour index. AIMS Mathematics, 2025, 10(5): 12343-12387. doi: 10.3934/math.2025559 |
[10] | Abeer M. Albalahi, Zhibin Du, Akbar Ali . On the general atom-bond sum-connectivity index. AIMS Mathematics, 2023, 8(10): 23771-23785. doi: 10.3934/math.20231210 |
For two graphs G1 and G2, the connected size Ramsey number ˆrc(G1,G2) is the smallest number of edges of a connected graph G such that if each edge of G is colored red or blue, then G contains either a red copy of G1 or a blue copy of G2. Let nK2 be a matching with n edges and P4 a path with four vertices. Rahadjeng, Baskoro, and Assiyatun [Procedia Comput. Sci. 74 (2015), 32-37] conjectured that ˆrc(nK2,P4)=3n−1 if n is even, and ˆrc(nK2,P4)=3n otherwise. We verify the conjecture in this short paper.
Since it was introduced by Erdős, Faudree, Rousseau, and Schelp [9] in 1978, size Ramsey number has always been an active branch of graph Ramsey theory. Given two graphs G1 and G2, we write G→(G1,G2) if for any partition (E1,E2) of E(G), either E(G1)⊆E1 or E(G2)⊆E2. In the language of coloring, G→(G1,G2) means that the graph G always contains either a red copy of G1 or a blue copy of G2 for any red-blue edge-coloring of G. The size Ramsey number ˆr(G1,G2) is the smallest number of edges in a graph G satisfying G→(G1,G2). In other words, ˆr(G1,G2)=min{|E(G)|:G→(G1,G2)}.
The statement that ˆr(G,G) grows linearly with |V(G)| has been well studied if G is a path [2,7], a tree with a bounded maximum degree [6,13], a cycle [14,15], etc. There are also a number of papers concerning the exact values of size Ramsey numbers [4,5,8,9,10,11,12,16,17,18,19,23]. Among them, Erdős and Faudree [8] studied the size Ramsey numbers involving matchings. Particularly, they confirmed that ˆr(nK2,P4)=⌈5n/2⌉.
Several variants have also been well-studied. In 2015, Rahadjeng, Baskoro, and Assiyatun [20] initiated the study of such a variant called connected size Ramsey number by requiring G to be connected. Formally speaking, the connected size Ramsey number ˆrc(G1,G2) is the smallest possible number of edges in a connected graph G satisfying G→(G1,G2). It is clear that ˆr(G1,G2)≤ˆrc(G1,G2), and equality holds when both G1 and G2 are connected graphs. But the latter function seems more tricky if either G1 or G2 is disconnected. The previous results mainly concern the connected size Ramsey numbers of a matching versus a sparse graph such as a path, a star, and a cycle; see [1,20,21,22,24,25,26].
Let nK2 be a matching with n edges, and Pm a path with m vertices. Rahadjeng, Baskoro, and Assiyatun [20] gave an upper bound of ˆrc(nK2,P4), and its exact value for 2≤n≤5. They also proposed the following conjecture.
Conjecture 1.1. [20] ˆrc(nK2,P4)={3n−1,if n is even;3n,if n is odd.
We prove this conjecture by introducing a tool called "deletable edge set" and carefully analyzing the end blocks of the host graph.
Theorem 1.2. ˆrc(nK2,P4)={3n−1,if n is even;3n,if n is odd.
The proof is postponed to Section 3. A more tricky problem is to determine ˆrc(nK2,P5). It is easy to check that ˆrc(K2,P5)=4 and ˆrc(2K2,P5)=6. To obtain a general upper bound, we use the fact that C6→(2K2,P5) and C11→(3K2,P5). It follows that n2C6→(nK2,P4) for even n with n≥2, and n−32C6∪C11→(nK2,P4) for odd n with n≥3. Both graphs n2C6 and n−32C6∪C11 have ⌊n/2⌋ components and can be connected by adding ⌊n/2⌋−1 new edges. Thus we have a connected graph G such that G→(nK2,P5) for each n≥2. The graph G has (7n+1)/2 edges if n is odd, and (7n−2)/2 edges if n is even. Hence ˆrc(nK2,P5)≤(7n−2)/2 for even n and ˆrc(nK2,P5)≤(7n+1)/2 for odd n. We believe this upper bound is also the lower bound, and pose the following conjecture.
Conjecture 1.3. ˆrc(nK2,P5)={(7n−2)/2,if n is even;(7n+1)/2,if n is odd.
We use induction to prove the lower bound of the main theorem. Thus the following values are needed as the base case.
Lemma 2.1 (Rahadjeng et al. [20]). ˆrc(2K2,P4)=5; ˆrc(3K2,P4)=9; ˆrc(4K2,P4)=11; ˆrc(5K2,P4)=15.
We need three terminologies that appear quite a few times in the proof. A (G1,G2)-coloring of G is a red-blue edge-coloring such that G contains neither a red copy of G1 nor a blue copy of G2. An edge set E0 of a connected graph G is called deletable, if E0 satisfies the following three conditions:
1. E0 can be partitioned into two edge sets E01 and E02, where E01 forms a star, E02 is a disjoint union of paths, each of whose lengths is at most two;
2. any path from E(G)∖E0 to E02 must pass through some edges of E01;
3. the edge set E(G)∖E0 induces a connected graph.
Notice that the graph induced by E(G)∖E0 is connected, even though the resulting graph by deleting all edges of E0 from G may have some isolated vertices. Further, by coloring all edges of E01 red and all edges of E02 blue, we have the following lemma.
Lemma 2.2. If E0 is a deletable edge set of G, then any (kK2,P4)-coloring of E(G)∖E0 can be extended to a ((k+1)K2,P4)-coloring of G.
A non-cut vertex of a connected graph is a vertex whose deletion still results in a connected graph. So every vertex of a nontrivial connected graph is either a cut vertex or a non-cut vertex. We see that the edges incident to a non-cut vertex form a deletable edge set, where E02 is an empty set.
We recall some more notation at the end of this section. Let us denote by Δ(H) the maximum degree of a graph H. The notation dH(u) stands for the number of edges with one end u and the other end in H. The graph H−v is the subgraph obtained from H by deleting the vertex v and all the edges incident to v. If S is a set of edges, we denote by G[S] the subgraph of G whose edge set is S and whose vertex set consists of all ends of edges of S. We use G∪H to denote the disjoint union of G and H, and nH to denote the disjoint union of n copies of H. For a connected graph H and any two vertices u,v of H, the distance from u to v, written d(u,v), is the length of a shortest path from u to v.
The upper bound follows from the fact that C5→(2K2,P4). If n is even, then n2C5→(nK2,P4). The graph n2C5 has n/2 components and can be connected by adding n/2−1 new edges. If n is odd, then n−12C5∪P4→(nK2,P4). The graph n−12C5∪P4 has (n+1)/2 components and can be connected by adding (n−1)/2 new edges. In both cases, we obtain a connected graph with 3n−1+S edges and hence the upper bound follows. Here, S is a Kronecker delta function, which means that S=0 if n is even, and S=1 if n is odd.
To show the lower bound, we proceed by induction on n. The result for n=1 is clear, and the results for 2≤n≤5 follow from Lemma 2.1. So set n≥6. Assume that the lower bound holds for every k with 1≤k≤n−1. That is to say, for any connected graph G with 3k−2+S edges, G has a (kK2,P4)-coloring. We show that the statement also holds for n by contradiction. Suppose to the contrary that there exists a connected graph G with 3n−2+S edges such that for any red-blue edge-coloring of G, it contains either a red copy of nK2 or a blue copy of P4. The following property of a deletable edge set follows from Lemma 2.2.
Claim 3.1. (a). Every deletable edge set has size at most three in G.
(b). If G has a deletable edge set E0 of size three, then the graph induced by E(G)∖E0, denoted by H, has the property that every deletable edge set has size at most two.
Proof. Let E0 be a deletable edge set. Then the graph H induced by E(G)∖E0 is still connected. If |E0|≥4, then H has at most 3n−5 edges and hence an ((n−1)K2,P4)-coloring by induction. By Lemma 2.2, it can be extended to an (nK2,P4)-coloring of G. This contradiction implies that every deletable edge set has size at most three.
If |E0|=3, then in the graph H, every deletable edge set has size at most two. Suppose not, there is a deletable edge set E′1 of H which also has size three. The graph induced by E(H)∖E′1 is still connected, and has six edges removed from G. This graph has an ((n−2)K2,P4)-coloring by the induction hypothesis. It can be extended to an (nK2,P4)-coloring of G, a contradiction.
Since the edges incident to any non-cut vertex form a deletable edge set, we have the following direct corollary.
Corollary 3.2. (a). Every non-cut vertex has degree at most three in G.
(b). If G has a non-cut vertex of degree three, then after removing it from G, the remaining graph has the property that every non-cut vertex has degree at most two.
To avoid a duplicate argument, if every deletable edge set of G has size at most two, we also use H to denote G. To be specific, we have
H={G if G has no deletable edge set of size three,G[E(G)∖E0] if G has a deletable edge set E0 of size three. |
That is to say, H is either the original graph G, or induced by E(G)∖E0, where E0 is a deletable edge set of size three. In either case, every deletable edge set in H has size at most two.
If H is 2-connected, then every vertex is non-cut and hence H is a cycle. Denote the cycle by v1v2⋯vpvp+1, where vp+1=v1. Then for 1≤i≤p, we color the edge vivi+1 red if i≡1(mod4) or i≡2(mod4). Otherwise, we color vivi+1 blue. The maximum red matching has at most ⌈|H|/4⌉ edges. Since n≥6, then ⌈|H|/4⌉<n if H is the graph G, and ⌈|H|/4⌉<n−1 if H is induced by E(G)∖E0. In both cases, G\not\to (nK_2, P_4) , a contradiction.
Now assume that H is connected but not 2-connected. To handle this case, we need the following definitions, which can be found in Bondy and Murty [3, Chap. 5.2]. Recall that a block of a graph is a subgraph that is nonseparable and is maximal concerning this property. We may associate with H a bipartite graph B(H) with bipartition (\mathcal{B}, S) , where \mathcal{B} has a vertex b_i for each block B_i of H , and S consists of the cut vertices of H . A block B and a cut vertex v are adjacent in B(H) if and only if B contains v in H . The graph B(H) is a tree, called the block tree of H . The blocks of H that correspond to leaves of B(H) are referred to as its end blocks. We have the following property of an end block in H .
Claim 3.3. If an end block is not K_2 , it must be a cycle.
Proof. Let B be an end block that is not K_2 . Since a block with at least three vertices is a 2-connected subgraph, it's left to show that every vertex has two neighbors on this block. By Corollary 3.2, every non-cut vertex has degree at most two. The block B has a single cut vertex of H , denoted by u_0 . Suppose that u_0 has more than two neighbors on the block, denoted by u_1, \dots, u_t , where t\ge 3 . If we delete u_0 from this block B , the resulting graph B-u_0 is still connected, but each of u_1, \dots, u_t has degree one. Since each vertex of B-u_0 has degree one or two, B-u_0 is either a path or a cycle. This contradicts the fact that at least three vertices of B-u_0 have degree one. Thus, we have d_B(u_0)\le 2 . Since B is 2-connected, it must be a cycle.
Claim 3.4. There are at least two cut vertices, each having degree at least three in H .
Proof. If every cut vertex has degree two, by Corollary 3.2(b), \Delta(H) = 2 . Since H is connected but not 2-connected, it must be a path. If H contains only one cut vertex whose degree is at least three, denoted by v , then every other vertex has degree at most two, and hence H-v is a disjoint union of some paths. We color all edges incident to v with red. In both cases, along each path, we alternately color two edges blue and two red until all edges have been colored. Then the maximum red matching has \lfloor (|H|+1)/4 \rfloor edges in the first case and at most \lfloor {|H|/4}+1 \rfloor edges in the second case. It is easy to check that both colorings can be extended to an (nK_2, P_4) -coloring of G , which completes the proof.
Among all cut vertices with degree at least three, we choose two of them, denoted by u, v , such that d(u, v) is as large as possible. Let U be the set of vertices such that any path with one end in U and one end as v must pass through u . Every vertex of U is called a descendant of u . Note that u\in U . Also, let V be the set of vertices such that any path from V to u must pass through v . Recall that every non-cut vertex has degree at most two. By the choice of u, v , every vertex of U\setminus \{u\} (and V\setminus \{v\} ) has degree one or two in H . If H is obtained from G by deleting a deletable edge set E_0 of size three, without loss of generality, assume that E_0 has no fewer end vertices in V than in U . That is, |V(E_0)\cap V|\ge |V(E_0)\cap U| . In this way, if we delete all edges incident to u and all edges with both ends in U from the original graph G , the graph induced by the remaining edges is still connected.
We see that the induced subgraph H[U\setminus\{u\}] consists of a disjoint union of paths. By Claim 3.3, the induced subgraph H[U] is formed by some paths and some cycles sharing exactly one vertex, which is u . We have the following two claims.
Claim 3.5. Every cycle (if it exists) in H[U] has length five.
Proof. If there is a cycle of length three or four in H[U] , then it forms a deletable edge set of H , which contradicts the fact that every deletable edge set of H has size at most two. If there is a cycle of length at least six in H[U] , say, uu_1u_2\dots u_ku is a cycle and k\ge 5 , then we color uu_1, u_1u_2, u_4u_5, u_5u_6 red, and u_2u_3, u_3u_4 blue. After deleting the six colored edges from G , the graph induced by the remaining edges is still connected, denoted by G' . By the inductive hypothesis, G' has an ((n-2)K_2, P_4) -coloring. Combining it with the above-colored edges, we obtain an (nK_2, P_4) -coloring of G . Thus, if a cycle appears in H[U] , then its length should be five.
Claim 3.6. The subgraph H[U] is a cycle of length five.
Proof. Assume that H[U] consists of s paths P_1, \dots, P_s , each of which has u as one of its ends, and t cycles C_1, \dots, C_t , each of which has length five. If one of the paths has length at least three, then we can find a subpath with three edges whose edge set is a deletable edge set of H , which contradicts the size of a deletable edge set. Hence each P_i has length at most two, where 1\le i\le s .
For each cycle, we color the two edges incident to u red, and the remaining three edges with one red and two blue. For each path, we color the edge incident to u red, and the remaining edge (if it exists) blue. If s\ge 1 and t = 0 , then all edges incident to u and all edges in H[U] form a deletable edge set. Since d_H(u)\ge 3 , this is the same contradiction as above. If s\ge 1 and t\ge 1 , then after deleting the colored edges of P_1 and C_1 from G , the graph induced by the remaining edges is still connected. Since P_1 and C_1 have at least six edges totally, and the maximum red matching has two edges, we may obtain an (nK_2, P_4) -coloring of G by induction. If s = 0 and t\ge 2 , then after deleting the colored edges of C_1 and C_2 from G , the graph induced by the remaining edges is still connected. Since both C_1 and C_2 are pentagons, and the maximum red matching has three edges, we again obtain an (nK_2, P_4) -coloring of G by induction. Thus, we have s = 0 and t = 1 . That is, H[U] is a pentagon.
We color all edges incident to u red, and the remaining three edges of H[U] with one red and two blue. Since d_H(u)\ge 3 , we have already colored at least six edges, and the maximum red matching has only two edges. If we delete these colored edges from G , the graph induced by the remaining edges is still connected, which has an ((n-2)K_2, P_4) -coloring by induction. It can be extended to an (nK_2, P_4) -coloring of G , a final contradiction.
The research was supported by the National Natural Science Foundation of China (Grant No. 11601527 and Grant No. 11971011).
The authors declare that they have no conflict of interest.
[1] |
H. Assiyatun, B. Rahadjeng, E. T. Baskoro, The connected size Ramsey number for matchings versus small disconnected graphs, Electron. J. Graph Theory Appl., 7 (2019), 113–119. http://dx.doi.org/10.5614/ejgta.2019.7.1.9 doi: 10.5614/ejgta.2019.7.1.9
![]() |
[2] |
J. Beck, On size Ramsey number of paths, trees, and circuits. Ⅰ, J. Graph Theory, 7 (1983), 115–129. https://doi.org/10.1002/jgt.3190070115 doi: 10.1002/jgt.3190070115
![]() |
[3] | J. A. Bondy, U. S. R. Murty, Graph theory, Springer, 2008. https://doi.org/10.1007/978-1-84628-970-5 |
[4] |
S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp, Ramsey-minimal graphs for multiple copies, Indag. Math. (N.S.), 81 (1978), 187–195. https://doi.org/10.1016/1385-7258(78)90036-7 doi: 10.1016/1385-7258(78)90036-7
![]() |
[5] | A. Davoodi, R. Javadi, A. Kamranian, G. Raeisi, On a conjecture of Erdős on size Ramsey number of star forests, arXiv: 2111.02065, 2021. Available from: https://arXiv.org/abs/2111.02065 |
[6] |
Jr. D. Dellamonica, The size‐Ramsey number of trees, Random Struct. Algor., 40 (2012), 49–73. https://doi.org/10.1002/rsa.20363 doi: 10.1002/rsa.20363
![]() |
[7] |
A. Dudek, P. Prałat, On some multicolor Ramsey properties of random graphs, SIAM J. Discrete Math., 31 (2017), 2079–2092. https://doi.org/10.1137/16M1069717 doi: 10.1137/16M1069717
![]() |
[8] |
P. Erdős, R. J. Faudree, Size Ramsey numbers involving matchings, Finite and Infinite Sets, (1984), 247–264. https://doi.org/10.1016/B978-0-444-86893-0.50019-X doi: 10.1016/B978-0-444-86893-0.50019-X
![]() |
[9] |
P. Erdős, R. J. Faudree, C. C Rousseau, R. H. Schelp, The size Ramsey number, Period. Math. Hungar., 9 (1978), 145–161. https://doi.org/10.1007/BF02018930 doi: 10.1007/BF02018930
![]() |
[10] |
R. J. Faudree, J. Sheehan, Size Ramsey numbers for small‐order graphs, J. Graph Theory, 7 (1983), 53–55. https://doi.org/10.1002/jgt.3190070107 doi: 10.1002/jgt.3190070107
![]() |
[11] |
R. J. Faudree, J. Sheehan, Size Ramsey numbers involving stars, Discrete Math., 46 (1983), 151–157. https://doi.org/10.1016/0012-365X(83)90248-0 doi: 10.1016/0012-365X(83)90248-0
![]() |
[12] | F. Harary, Z. Miller, Generalized Ramsey theory Ⅷ, The size Ramsey number of small graphs, In Studies in Pure Mathematics, (1983), 271–283. https://doi.org/10.1007/978-3-0348-5438-2_25 |
[13] |
P. E. Haxell, Y. Kohayakawa, The size-Ramsey number of trees, Israel J. Math., 89 (1995), 261–274. https://doi.org/10.1007/BF02808204 doi: 10.1007/BF02808204
![]() |
[14] |
P. E. Haxell, Y. Kohayakawa, T. Łuczak, The induced size-Ramsey number of cycles, Combin. Probab. Comput., 4 (1995), 217–239. https://doi.org/10.1017/S0963548300001619 doi: 10.1017/S0963548300001619
![]() |
[15] |
R. Javadi, F. Khoeini, G. R. Omidi, A. Pokrovskiy, On the size-Ramsey number of cycles, Combin. Probab. Comput., 28 (2019), 871–880. https://doi.org/10.1017/S0963548319000221 doi: 10.1017/S0963548319000221
![]() |
[16] |
R. Javadi, G. Omidi, On a question of Erdős and Faudree on the size Ramsey numbers, SIAM J. Discrete Math., 32 (2018), 2217–2228. https://doi.org/10.1137/17M1115022 doi: 10.1137/17M1115022
![]() |
[17] | R. Lortz, I. Mengersen, Size Ramsey results for paths versus stars, Australas. J. Combin., 18 (1998), 3–12. |
[18] |
R. Lortz, I. Mengersen, Size Ramsey results for the path of order three, Graphs Combin., 37 (2021), 2315–2331. https://doi.org/10.1007/s00373-021-02398-3 doi: 10.1007/s00373-021-02398-3
![]() |
[19] |
M. Miralaei, G. R. Omidi, M. Shahsiah, Size Ramsey numbers of stars versus cliques, J. Graph Theory, 92 (2019), 275–286. https://doi.org/10.1002/jgt.22453 doi: 10.1002/jgt.22453
![]() |
[20] |
B. Rahadjeng, E. T. Baskoro, H. Assiyatun, Connected size Ramsey numbers for matchings versus cycles or paths, Procedia Comput. Sci., 74 (2015), 32–37. https://doi.org/10.1016/j.procs.2015.12.071 doi: 10.1016/j.procs.2015.12.071
![]() |
[21] |
B. Rahadjeng, E. T. Baskoro, H. Assiyatun, Connected size Ramsey numbers of matchings and stars, AIP Conf. Proc., 1707 (2016), 020015. https://doi.org/10.1063/1.4940816 doi: 10.1063/1.4940816
![]() |
[22] |
B. Rahadjeng, E. T. Baskoro, H. Assiyatun, Connected size Ramsey number for matchings vs. small stars or cycles, Proc. Indian Acad. Sci.: Math. Sci., 127 (2017), 787–792. https://doi.org/10.1007/s12044-017-0366-z doi: 10.1007/s12044-017-0366-z
![]() |
[23] | J. Sheehan, R. J. Faudree, C. C. Rousseau, A class of size Ramsey problems involving stars, Graph Theory and Combinatorics, (1983), 273–281. |
[24] |
V. Vito, A. C. Nabila, E. Safitri, D. R. Silaban, The size Ramsey and connected size Ramsey numbers for matchings versus paths, J. Phys. Conf. Ser., 1725 (2021), 012098. https://doi.org/10.1088/1742-6596/1725/1/012098 doi: 10.1088/1742-6596/1725/1/012098
![]() |
[25] |
V. Vito, D. R. Silaban, Two types of size Ramsey numbers for matchings of small order, J. Discrete Math. Sci. Cryptogr., (2022), 1–13. https://doi.org/10.1080/09720529.2021.2000153 doi: 10.1080/09720529.2021.2000153
![]() |
[26] | S. Wang, R. Song, Y. Zhang, Y. Zhang, Connected size Ramsey numbers of matchings versus a small path or cycle, arXiv: 2205.03965, 2022. Available from: https://arXiv.org/abs/2205.03965 |