close

Вход

Забыли?

вход по аккаунту

?

1.4940811

код для вставкиСкачать
On size tripartite Ramsey numbers of P3 versus mK1,n
Anie Lusiani, Edy Tri Baskoro, and Suhadi Wido Saputro
Citation: AIP Conference Proceedings 1707, 020010 (2016);
View online: https://doi.org/10.1063/1.4940811
View Table of Contents: http://aip.scitation.org/toc/apc/1707/1
Published by the American Institute of Physics
On Size Tripartite Ramsey Numbers of P3 versus mK1,n
Anie Lusiani∗ , Edy Tri Baskoro† and Suhadi Wido Saputro∗∗
∗
Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institute Teknologi
Bandung, Jl. Ganesa 10 Bandung 40132 Indonesia, Email: [email protected]
†
Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institute Teknologi
Bandung, Jl. Ganesa 10 Bandung 40132 Indonesia, Email: [email protected]
∗∗
Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institute
Teknologi Bandung, Jl. Ganesa 10 Bandung 40132 Indonesia, Email: [email protected]
Abstract. Let Kl×t be a complete, balanced, multipartite graph consisting of l partite sets and t vertices in each partite set. For
simple graphs G and H, the size multipartite Ramsey number m j (G, H) is the smallest natural number t such that any arbitrary
red-blue coloring on the edges of Kl×t contains a red G or a blue H as a subgraph. In particular, if j = 3 then m3 (G, H) is
called the size tripartite Ramsey number of G and H. In this paper, we determine the exact values of the size tripartite numbers
m3 (P3 , mK1,n ) for all integers m ≥ 1 and n ≥ 3, where P3 is a path of order 3 and mK1,n is a disjoint union of m copies of a
star K1,n .
Keywords: path, size tripartite Ramsey number, star
PACS: 02.10.Ox
INTRODUCTION
The graph Ks×t represents the complete, balanced, multipartite graph consisting of s partite sets having exactly t
vertices in each partite set. The notion of size multipartite Ramsey numbers was introduced by Burger and Vuuren
in 2004 [1]. They determined the size multipartite Ramsey numbers for a combination of two complete graphs in
Definition 1.
Definition 1. (Size multipartite Ramsey numbers)
Let j, l, n, s and t be natural numbers with n, s ≥ 2. Then the size multipartite Ramsey number m j (Kn×l , Ks×t ) is the
smallest natural number ζ such that an arbitrary coloring of the edges of K j×ζ , using the two colors red and blue,
necessarily forces a red Kn×l or a blue Ks×t as subgraph.
Burger and Vuuren have given result that the size multipartite Ramsey number m j (Kn×l , Ks×t ) exists for any n, s ≥ 2
and l,t ≥ 1 if only if j ≥ r(n, s). They also provided a simple lower bound for size multipartite Ramsey numbers.
There are also some results for m j (Kn×l , Ks×t ) for certain j, n, l, s, and t. Day et al.[2] and Burger et al.[1] determined
the exact values of m j (K2×2 , H) where H ∼
= K2×2 or K3×1 . Syafrizal et al.[4] have written the results in following table.
TABLE 1. The size multipartite Ramsey
numbers m j (K2×2 , H) for some H
j
m j (K2×2 , K2×2 )
∞∗
5†
3†
2†
2†
2†
1†
1
2
3
4
5
6
≥7
∗
†
m j (K2×2 , K3×1 )
∞∗
∞∗
3∗
2∗
2∗
2∗
1∗
Due to Burger et al.[1]
Due to Day et al.[2]
Proceedings of The 7th SEAMS UGM International Conference on Mathematics and Its Applications 2015
AIP Conf. Proc. 1707, 020010-1–020010-5; doi: 10.1063/1.4940811
© 2016 AIP Publishing LLC 978-0-7354-1354-2/$30.00
020010-1
In 2005, Syafrizal et al.[3] generalized this concept by removing the completeness requirement. In this concept, any
red-blue coloring of Ks×t necessarilly forces a red G or a blue H, where G and H are any graphs. This generalized
concept is denoted by m j (G, H).
Syafrizal et al. have determined the size multipartite Ramsey numbers of paths versus paths [3, 5]. They proved that
⎧ n
j ;
for s = 2, 3 and n ≥ 3,
⎪
⎪
⎨ 4 ;
for s = 4, j ≥ 2, and n = 2,
j
m j (Ps , Pn ) =
n
+
1;
for s = 4, j = 2, and n ≥ 3,
⎪
⎪
⎩ 2n+1
j ;
for s = 4, j ≥ 3, and n ≥ 3.
They also determined the size multipartite Ramsey numbers of paths versus cycles [3, 5, 6], paths versus cocktail
party graphs [7], paths versus complete balanced multipartite graphs K j×2 for j = 2, 3 [7, 9], paths versus trees [10],
and lower bounds for m j (Pn , K j×b ), where j ≥ 3, b ≥ 2 [8].
In 2007, Syafrizal et al.[4] initiated to determine the size multipartite Ramsey number of paths versus a star, namely
m j (Ps , K1,n ) for s = 2, 3 and j ≥ 3. In 2014, Surahmat and Syafrizal [11] obtained some results for m3 (Ps , K1,n ) where
s = 3, 4, 5, 6, which can be seen in Theorem 1.
Theorem 1. [11]
If n ≥ 2, then m3 (Ps , K1,n ) = n+3
2 for s = 3, 4, 5. Additionally, if n = 8 + 10k, positive integers k, then m3 (P6 , K1,n ) =
n+3
.
2
Now we consider s = 3. In this paper, we use the generalizing concept of the size tripartite Ramsey number of G
and H, m3 (G, H). We determine an exact value of the size tripartite Ramsey numbers m3 (P3 , mK1,n ) for all integers
m ≥ 1 and n ≥ 3, where P3 is a path of order 3 and mK1,n is a disjoint union of m copies of a star K1,n . For m = 1, we
improve the Surahmat’s result in Theorem 1 with our result in Theorem 2.
In order to do so, we call some basic definitions as follow. Let G be a finite and simple graph. Let vertex and edge
sets of graph G are denoted by V (G) and E(G), respectively. A matching of a graph G is defined as a set of edges
without a common vertex. Let e = uv be an edge in G, then u is called adjacent to v. The neighborhood NG (v) of a
vertex v is the set of vertices adjacent to v in G. The degree dG (x) of a vertex x is |NG (x)|. The maximum degree of G
is denoted by (G), where (G) = max{dG (v)|v ∈ V (G)}. A star K1,n is the graph on n + 1 vertices with one vertex
of degree n, called the center of this star, and n vertices of degree 1, called the leaves.
MAIN RESULTS
In this section, we determine an exact value of size tripartite Ramsey numbers of a P3 versus mK1,n for all integers
m ≥ 1 and n ≥ 3. Our first and second results are related to m3 (P3 , K1,n ) for m = 1 and m = 2, respectively, which can
be seen in Theorem 2 and 3.
Theorem 2. For n ≥ 3,
m3 (P3 , K1,n ) =
Proof.
We define
t=
2 n4 ;
2 n4 + 1;
2 n4 ;
2 n4 + 1;
n ≡ 3(mod 4),
otherwise.
n ≡ 3(mod 4),
otherwise.
First, let us consider a factorization K3×(t−1) = F1 ⊕ F2 . We will show that there exist F1 which doesn’t contain P3 and
F2 doesn’t contain K1,n . We can choose F1 is a maximal matching of K3×(t−1) . It follows that (F2 ) < n which implies
F2 K1,n . Therefore, m3 (P3 , K1,n ) ≥ t.
Now, we define a factorization K3×t = F3 ⊕ F4 . We will show that when F3 doesn’t contain P3 , F4 contains K1,n .
Since F3 doesn’t contain P3 , then F3 is a matching of K3×t . Then we obtain that (F4 ) ≥ n which implies F4 ⊃ K1,n .
Therefore, m3 (P3 , K1,n ) ≤ t.
Theorem 3. For n ≥ 3, m3 (P3 , 2K1,n ) = 23 (n + 1).
020010-2
Proof.
We define t = 23 (n + 1).
Let us consider a factorization K3×(t−1) = F1 ⊕F2 , such that F1 doesn’t contain P3 . We will show that F2 doesn’t contain
2K1,n . Since |V (F2 )| = 3(t − 1) = 3( 23 (n + 1) − 1) = 3 23 (n + 1) − 3 < 2(n + 1) = |V (2K1,n )|, we obtain F2 2K1,n .
Therefore, m3 (P3 , 2K1,n ) ≥ t.
Now, we consider a factorization F = K3×t = F3 ⊕ F4 such that F3 doesn’t contain P3 which implies F3 is
a matching of K3×t . Let Ai be an i − th partite (1 ≤ i ≤ 3) and ai j ∈ Ai , for 1 ≤ j ≤ t. Let (a11 , a21 ) be
an edge in F3 . Then we have two induced subgraphs by {a11 } ∪ (A2 − {a21 }) ∪ {a31 , a32 , ..., a3 t } and by
2
{a21 } ∪ (A1 − {a11 }) ∪ {a3( t +1) , a3( t +2) , ..., a3t } in F4 which is isomorphic to 2K1,(t−1)+ t . Then we obtain
2
2
2
n + 1; n ≡ 4(mod 3),
F4 ⊃ 2K1,n , because (t − 1) + 2t =
n;
otherwise.
Therefore, m3 (P3 , 2K1,n ) ≤ t.
In Theorem 4, we provide the size tripartite Ramsey number of P3 versus mK1,n for m ≥ 3 as follows.
Theorem 4. For n ≥ 3 and m = 3k + p, where p ∈ {0, 1, 2} and positive integers k,
m3 (P3 , mK1,n ) = k(n + 1) + 3p (n + 1).
Proof.
We distinguish the following three cases.
Case 1. p = 0.
We define t = k(n + 1).
First, let us consider a factorization K3×(t−1) = F1 ⊕ F2 such that F1 doesn’t contain P3 . We will show that F2 doesn’t
contain mK1,n . Since |V (F2 )| = 3(t − 1) = 3k(n + 1) − 3 < 3k(n + 1) = |V (mK1,n )|, we obtain F2 mK1,n . Therefore,
m3 (P3 , mK1,n ) ≥ t.
Now, let us consider a factorization K3×t = F3 ⊕ F4 such that F3 doesn’t contain P3 , which implies F3 is a matching
of K3×t . Let V (K3×t ) =
3
i=1
Ai such that Ai ∩ A j = 0/ for i = j and |Ai | = k(n + 1). We decompose Ai = (
k
j=1
Ai j ) ∪ Ai
where Ai = {ai1 , ai2 , ..., aik } and |Ai j | = n. For 1 ≤ i, s ≤ 3 and 1 ≤ j ≤ k, there exists an induced subgraph in F4 by
{ai j } ∪ As j , with s − i ≡ 1(mod 3), which is isomorphic to K1,n . Then, F4 ⊃ 3kK1,n = mK1,n . Hence, m3 (P3 , mK1,n ) ≤ t.
Case 2. p = 1.
We define t = k(n + 1) + 13 (n + 1).
Let us consider a factorization K3×(t−1) = F1 ⊕ F2 such that F1 doesn’t contain P3 . We will show that F2 doesn’t contain
mK1,n . Since |V (F2 )| = 3(t − 1) = 3k(n + 1) + 13 (n + 1) − 3 < (3k + 1)(n + 1) = m(n + 1) = |V (mK1,n )|, we obtain
F2 mK1,n . Therefore, m3 (P3 , mK1,n ) ≥ t.
Now, we consider a factorization K3×t = F3 ⊕ F4 such that F3 doesn’t contain P3 which implies F3 matching of K3×t .
Since |V (F4 )| = 3t = 3k(n + 1) + 3 13 (n + 1) ≥ (3k + 1)(n + 1) = m(n + 1) = |V (mK1,n )|, F4 may be contain mK1,n .
We will show that F4 ⊇ mK1,n recursively for m = 3k + 1 where k ≥ 1 in two subcases as follows. Let V (K3×t ) =
such that Ai ∩ A j = 0/ for i = j and |Ai | = k(n + 1) + 13 (n + 1).
Subcase 2.1. k = 1.
So, m = 4. The number of vertices in every partite is t = (n + 1) + 13 (n + 1).
3
Ai
i=1
t−2
2 ; for t is even,
We decompose A1 , A2 , A3 as follows. Let A1 = B1 ∪ B2 ∪C, with |B1 | = |B2 | =
t−3
2 ; for t is odd,
2; for t is even,
and |C| =
For i = {2, 3}, let Ai = Di ∪ Ei ∪ Gi where |Di | = t − n − 1, |Ei | = n, and |Gi | = 1.
3; for t is odd.
Then there exists an induced subgraph in F4 by C ∪ Ei , where i = {2, 3} which is isomorphic to K2,n,n for t
is even or K3,n,n for t is odd. Note that both K2,n,n and K3,n,n contain 2K1,n . The centers of two stars are in
C and their leaves are in E2 ∪ E3 . The others induced subgraphs in F4 are by B1 ∪ D2 ∪ G3 and B2 ∪ D3 ∪ G2 .
Both induced subgraphs are isomorphic to Kt−2,t−n,t−n for t is even and Kt−3,t−n,t−n for t is odd. Since
020010-3
FIGURE 1.
Decomposition of K3×t to be have 4K1,n
1
3 1
|B1 | + |D2 | = |B2 | + |D3 | ≥ t−3
2 + t − n − 1 = 2 n − 1 + 2 3 (n + 1) ≥ n, ∀n, we obtain that both of Kt−2,t−n,t−n
and Kt−3,t−n,t−n contain 2K1,n . The centers of these stars are in G2 and G3 , and their leaves recpectively are in B2 ∪ D3
and B1 ∪ D2 . Therefore, F4 ⊇ 4K1,n .
Subcase 2.2. k ≥ 2.
We have t = (n + 1) + 13 (n + 1) + (k − 1)(n + 1).
We decompose partite Ai as Ai1 and Ai2 , where |Ai1 | = (n + 1) + 13 (n + 1) and |Ai2 | = (k − 1)(n + 1), for i = {1, 2, 3}.
We define X1 and X2 as induced subgarphs of K3×t by Ai1 and Ai2 , for i = {1, 2, 3}, respectively. By using the same
technique of decomposition in Subcase 2.1 for X1 and Case 1 for X2 , we obtain that X1 ⊇ 4K1,n and X2 ⊇ 3(k − 1)K1,n ,
respectively. It follows that F4 ⊇ (3k + 1)K1,n , where k ≥ 2.
Thus, from both subcases above, we obtain F4 ⊇ mK1,n for m = 3k + 1 where k ≥ 1. Therefore, m3 (P3 , mK1,n ) ≤ t.
Case 3. p = 2.
We define t = k(n + 1) + 23 (n + 1).
Let us consider a factorization K3×(t−1) = F1 ⊕ F2 such that F1 doesn’t contain P3 . We will show that F2 doesn’t contain
mK1,n . Since |V (F2 )| = 3(t − 1) = 3k(n + 1) + 3 23 (n + 1) − 3 < (3k + 2)(n + 1) = m(n + 1) = |V (mK1,n )|, we obtain
F2 mK1,n . Therefore, m3 (P3 , mK1,n ) ≥ t.
Now, we consider a factorization K3×t = F3 ⊕ F4 such that F3 doesn’t contain P3 which implies F3 is a matching
of K3×t . Let t = t1 + t2 where t1 = k(n + 1) and t2 = 23 (n + 1). Let V (K3×t ) =
such that |Ai | = t1 + t2 . We decompose Ai = (
k
j=1
3
i=1
Ai where Ai ∩ A j = 0/ for i = j
Ai j ) ∪ Ai ∪ Bi where Ai = {ai1 , ai2 , ..., aik }, Bi = {bi1 , bi2 , ..., bit2 } and
|Ai j | = n. For 1 ≤ i, s ≤ 3 and 1 ≤ j ≤ k, there exists an induced subgraph in F4 by {ai j } ∪ As j , with s − i ≡ 1(mod
3), which is isomorphic to K1,n . This implies F4 contains 3kK1,n . In F4 there also exists two induced subgraphs
by {b11 } ∪ (B2 − {b21 }) ∪ {b31 , b32 , ..., b3 t2 } and {b21 } ∪ (B1 − {b11 }) ∪ {b3( t2 +1) , b3( t2 +2) , ..., b3t2 } which are
2
2 2
n + 1; n ≡ 4(mod 3),
t2
isomorphic to K1,(t −1)+ t2 . Then F4 also contains 2K1,n , because (t2 − 1) + 2 =
2
n;
otherwise,
2
Therefore, F4 contains (3k + 2)K1,n = mK1,n . Hence, m3 (P3 , mK1,n ) ≤ t.
ACKNOWLEDGMENTS
This research was supported by Research Grant "Program Riset dan Inovasi KK-ITB", Ministry of Research, Technology and Higher Education, Indonesia.
020010-4
REFERENCES
A. P. Burger and J. H. van Vuuren, Ramsey numbers in complete balanced multipartite graphs. Part II: Size Numbers, Discrete
Math. 283, 45–49 (2004).
2. D. Day, W. Goddard, M. A. Henning and H. C. Swart, Multipartite Ramsey numbers, Ars Combin. 58, 23–31 (2001).
3. Syafrizal Sy, E. T. Baskoro, and S. Uttunggadewa, The size multipartite Ramsey numbers for paths, J. Combin. Math. Combin.
55, 103–107 (2005).
4. Syafrizal Sy, E. T. Baskoro, and S. Uttunggadewa, The size multipartite Ramsey numbers for small paths versus other graphs,
Far East J. Appl. Math. 28 Issue 1, 131–138 (2007).
5. Syafrizal Sy, E. T. Baskoro, S. Uttunggadewa and H. Assiyatun, Path-path size multipartite Ramsey numbers, J. Combin.
Math. Combin. Comput. 71, 265–271 (2009).
6. Syafrizal Sy, On size multipartite Ramsey numbers for paths versus cycle of three or four vertices, Far East J. Appl. Math.
Volume 44 No.2, 109–116 (2010).
7. Syafrizal Sy, On size multipartite Ramsey numbers for small paths versus cocktail party graphs, Far East J. Appl. Math.
Volume 55 No.1, 53–60 (2011).
8. Syafrizal Sy and E. T. Baskoro, Lower bounds for size multipartite Ramsey numbers m j (Pn , K j×b ), American Institute of
Physics Proceeding Volume 1450, 259–261 (2011).
9. Syafrizal Sy, The size multipartite Ramsey numbers of paths with respect to complete balanced multipartite graphs, Far East
J. Appl. Math. Volume 62 No.2, 107–115 (2012).
10. Syafrizal Sy, Tree-path size bipartite Ramsey numbers, Far East J. Math. Sci. Volume 76 No.1, 139–145 (2013).
11. Surahmat and Syafrizal Sy, Star-path size multipartite Ramsey numbers, Applied Math. Sciences (Bulgaria) Volume 8 No.75,
3733–3736 (2014).
1.
020010-5
Документ
Категория
Без категории
Просмотров
2
Размер файла
118 Кб
Теги
4940811
1/--страниц
Пожаловаться на содержимое документа