19 results on '"Chen, Yaojun"'
Search Results
2. Generalizations of some Nordhaus–Gaddum‐type results on spectral radius.
- Author
-
Lu, Junying, Wang, Lanchao, and Chen, Yaojun
- Subjects
GENERALIZATION ,SUBGRAPHS ,COMPLETE graphs - Abstract
Let G $G$ be a simple graph and λ(G) $\lambda (G)$ the spectral radius of G $G$. For k≥2 $k\ge 2$, a k $k$‐edge decomposition (H1,...,Hk) $({H}_{1},{\rm{\ldots }},{H}_{k})$ is k $k$ spanning subgraphs such that their edge sets form a k $k$‐partition of the edge set of G $G$. In this paper, we obtain some sharp lower and upper bounds for λ(H1)+⋯+λ(Hk) $\lambda ({H}_{1})+\,\cdots \,+\lambda ({H}_{k})$ in terms of the clique number of Hi ${H}_{i}$ and the size of G $G$, and discuss what k $k$‐edge decomposition (H1,...,Hk) $({H}_{1},{\rm{\ldots }},{H}_{k})$ can maximize λ(H1)+⋯+λ(Hk) $\lambda ({H}_{1})+\cdots \,+\lambda ({H}_{k})$ when G $G$ is a complete graph. These generalize some Nordhaus–Gaddum‐type results on spectral radius for k=2 $k=2$, due to Nosal, Hong and Shu, and Nikiforov. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
3. Turán number for odd‐ballooning of trees.
- Author
-
Zhu, Xiutao and Chen, Yaojun
- Subjects
- *
RAMSEY numbers , *COMPLETE graphs , *TREES - Abstract
The Turán number ex(n,H) $\text{ex}(n,H)$ is the maximum number of edges in an H $H$‐free graph on n $n$ vertices. Let T $T$ be any tree. The odd‐ballooning of T $T$, denoted by To ${T}_{o}$, is a graph obtained by replacing each edge of T $T$ with an odd cycle containing the edge, and all new vertices of the odd cycles are distinct. In this paper, we determine the exact value of ex(n,To) $\text{ex}(n,{T}_{o})$ for sufficiently large n $n$ and To ${T}_{o}$ being good, which generalizes all the known results on ex(n,To) $\text{ex}(n,{T}_{o})$ for T $T$ being a star, due to Erdős, Füredi, Gould, and Gunderson (1995), Hou, Qiu, and Liu (2018), and Yuan (2018), and provides some counterexamples with chromatic number three to a conjecture of Keevash and Sudakov (2004), on the maximum number of edges not in any monochromatic copy of H $H$ in a 2‐edge‐coloring of a complete graph of order n $n$. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
4. The Connectedness of the Friends-and-Strangers Graph of a Lollipop and Others.
- Author
-
Wang, Lanchao and Chen, Yaojun
- Subjects
- *
LOLLIPOPS , *BIJECTIONS , *COMPLETE graphs , *MATHEMATICAL connectedness - Abstract
Let X and Y be any two graphs of order n. The friends-and-strangers graph FS (X , Y) of X and Y is a graph with vertex set consisting of all bijections σ : V (X) → V (Y) , in which two bijections σ , σ ′ are adjacent if and only if they differ precisely on two adjacent vertices of X, and the corresponding mappings are adjacent in Y. The most fundamental question that one can ask about these friends-and-strangers graphs is whether or not they are connected. Let Lollipop n - k , k be a lollipop graph of order n obtained by identifying one end of a path of order n - k + 1 with a vertex of a complete graph of order k. Defant and Kravitz started to study the connectedness of FS (Lollipop n - k , k , Y) . In this paper, we give a sufficient and necessary condition for FS (Lollipop n - k , k , Y) to be connected for all 2 ≤ k ≤ n , which interpolates between two previous results on paths and complete graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. Gallai and [formula omitted]-uniform Ramsey numbers of complete bipartite graphs.
- Author
-
Liu, Yuchen and Chen, Yaojun
- Subjects
- *
RAMSEY numbers , *HYPERGRAPHS , *BIPARTITE graphs , *COMPLETE graphs , *GRAPH coloring , *INTEGERS - Abstract
A Gallai coloring of a complete graph is a coloring of the edges without rainbow triangles (all edges colored differently). Given a graph H and a positive integer k , the Gallai Ramsey number G R k (H) is the minimum integer N such that every Gallai k -coloring of K N contains a monochromatic copy of H. A uniform coloring of a complete multipartite graph is a coloring of the edges such that the edges between any two parts receive the same color. Given a graph H and positive integers k and ℓ , the ℓ -uniform Ramsey number R k ℓ (H) is the minimum integer N such that any uniform k -coloring of any complete multipartite graph on N vertices with each part of cardinality no more than ℓ , contains a monochromatic copy of H. Let K m , n denote a complete bipartite graph. Wu et al. conjectured that G R k (K m , n) = (n − 1) (k − 2) + R 2 1 (K m , n) if R 2 1 (K m , n) ≥ 3 m − 2 , where k ≥ 3 and m ≥ n ≥ 2. In this paper, we show that G R k (K m , n) = (n − 1) (k − 2) + R 2 m − 1 (K m , n) for all integers k ≥ 3 and m ≥ n ≥ 2. Based on this result, we improve the known general bounds for G R k (K m , n) , and confirm the conjecture for some complete bipartite graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
6. Generalized Turán Number of Even Linear Forests.
- Author
-
Zhu, Xiutao, Zhang, Fangfang, and Chen, Yaojun
- Subjects
COMPLETE graphs ,RAMSEY numbers - Abstract
The generalized Turán number e x (n , K s , H) is defined to be the maximum number of copies of a complete graph K s in any H-free graph on n vertices. Let F be an even linear forest, that is, F consists of paths of even order. In this paper, we determine the value of e x (n , K s , F) , which generalizes or improves some known results on generalized Turán number and classical Turán number. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
7. The maximum number of triangles in [formula omitted]-free graphs.
- Author
-
Zhu, Xiutao, Chen, Yaojun, Gerbner, Dániel, Győri, Ervin, and Karim, Hilal Hama
- Subjects
- *
COMPLETE graphs , *TRIANGLES , *HYPERGRAPHS , *FRIENDSHIP - Abstract
The generalized Turán number ex (n , K s , H) is the maximum number of complete graph K s in an H -free graph on n vertices. Let F k be the friendship graph consisting of k triangles. Erdős and Sós (1976) determined the value of ex (n , K 3 , F 2). Alon and Shikhelman (2016) proved that ex (n , K 3 , F k) ≤ (9 k − 15) (k + 1) n. In this paper, by using a method developed by Chung and Frankl in hypergraph theory, we determine the exact value of ex (n , K 3 , F k) and the extremal graph for any F k when n ≥ 4 k 3 . [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
8. On three color Ramsey numbers [formula omitted].
- Author
-
Zhang, Xuemei, Chen, Yaojun, and Cheng, T.C. Edwin
- Subjects
- *
RAMSEY numbers , *GRAPH coloring , *COMPLETE graphs , *PATHS & cycles in graph theory , *MATHEMATICAL bounds - Abstract
Abstract For k given graphs G 1 , G 2 , ... , G k , k ≥ 2 , the k -color Ramsey number, denoted by R (G 1 , G 2 , ... , G k) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of G i colored with i , for some 1 ≤ i ≤ k. Let C m be a cycle of length m and K 1 , n a star of order n + 1. In this paper, firstly we give a general upper bound of R (C 4 , C 4 , ... , C 4 , K 1 , n). In particular, for the 3-color case, we have R (C 4 , C 4 , K 1 , n) ≤ n + 4 n + 5 + 3 and this bound is tight in some sense. Furthermore, we prove that R (C 4 , C 4 , K 1 , n) ≤ n + 4 n + 5 + 2 for all n = ℓ 2 − ℓ and ℓ ≥ 2 , and if ℓ is a prime power, then the equality holds. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
9. Rainbow subgraphs in Hamiltonian cycle decompositions of complete graphs.
- Author
-
Liu, Yuchen and Chen, Yaojun
- Subjects
- *
RAMSEY numbers , *SUBGRAPHS , *COMPLETE graphs , *HAMILTONIAN graph theory - Abstract
A Hamiltonian cycle decomposition of a complete graph K 2 n + 1 is an n -edge-coloring of K 2 n + 1 such that each color class is a Hamiltonian cycle. For a given Hamiltonian cycle decomposition, a subgraph of K 2 n + 1 is called rainbow if all its edges are colored differently. Let H be any subgraph of K 2 n + 1 consisting of n edges. In 1999, Wu conjectured that K 2 n + 1 has a Hamiltonian cycle decomposition such that H is rainbow. In this paper, we show that the conjecture is true in the cases that | H | ≤ n + 1 , or H is a linear forest, or n ≤ 5. Using this result, we partially confirm a conjecture on restricted size Ramsey numbers due to Miralaei and Shahsiah in 2020. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
10. Generalized Turán number for linear forests.
- Author
-
Zhu, Xiutao and Chen, Yaojun
- Subjects
- *
GRAPH algorithms , *LOGICAL prediction , *COMPLETE graphs , *RAMSEY numbers - Abstract
The generalized Turán number ex (n , K s , H) is defined to be the maximum number of copies of a complete graph K s in any H -free graph on n vertices. Let F be a linear forest consisting of k paths of orders ℓ 1 , ℓ 2 ,... , ℓ k. By characterizing the structure of the F -free graph with large minimum degree, we determine the value of ex (n , K s , F) for n = Ω (| F | s) and k ≥ 2 except some ℓ i = 3 , and the corresponding extremal graphs. Our result confirms a conjecture, due to Yuan and Zhang (2021), on classical Turán number of any linear forest for n = Ω (| F | 2) and each ℓ i ≠ 3 , and improves some known results on classical Turán number of linear forest. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
11. All Complete Graph-Wheel Planar Ramsey Numbers.
- Author
-
Zhang, Yanbo, Zhou, Guofei, and Chen, Yaojun
- Subjects
COMPLETE graphs ,PLANAR graphs ,RAMSEY numbers ,INTEGERS ,MATHEMATICAL analysis - Abstract
For two given graphs $$G_1$$ and $$G_2$$ , the planar Ramsey number $$PR(G_1,G_2)$$ is the smallest integer $$N$$ such that for any planar graph $$G$$ of order $$N$$ , either $$G$$ contains $$G_1$$ or the complement of $$G$$ contains $$G_2$$ . Let $$K_m$$ denote a complete graph of order $$m$$ and $$W_n$$ a wheel of order $$n+1$$ . In this paper, we determine all planar Ramsey numbers $$PR(K_m,W_n)$$ . [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
12. Bounds for two multicolor Ramsey numbers concerning quadrilaterals.
- Author
-
Zhang, Xuemei, Chen, Yaojun, and Cheng, T.C. Edwin
- Subjects
- *
RAMSEY numbers , *QUADRILATERALS , *COMPLETE graphs , *FINITE fields , *RANDOM graphs - Abstract
For k given graphs H 1 , ... , H k , k ≥ 2 , the k -color Ramsey number, denoted by R (H 1 , ... , H k) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of H i colored with i , for some 1 ≤ i ≤ k. Let C m be a cycle of length m , K 1 , n a star of order n + 1 and W n a wheel of order n + 1. In this paper, by using algebraic and probabilistic methods, we first give two lower bounds for (k + 1) -color Ramsey number R (C 4 , ... , C 4 , K 1 , n) for some special n , which shows the upper bound due to Zhang et al. (2019) is tight in some sense, and then establish a general lower bound for R (C 4 , ... , C 4 , K 1 , n) in terms of n and k , which extends the classical result of Burr et al. (1989). Moreover, we show that R (C 4 , ... , C 4 , K 1 , n) = R (C 4 , ... , C 4 , W n) for sufficiently large n. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
13. The Ramsey number for a cycle of length six versus a clique of order eight
- Author
-
Chen, Yaojun, Edwin Cheng, T.C., and Xu, Ran
- Subjects
- *
RAMSEY numbers , *GRAPH theory , *COMPLETE graphs , *RAMSEY theory , *COMBINATORICS , *MATHEMATICAL analysis - Abstract
Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of length and a complete graph of order . In this paper, it is shown that . [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
14. Inverting the Turán problem with chromatic number.
- Author
-
Zhu, Xiutao and Chen, Yaojun
- Subjects
- *
COMPLETE graphs , *SUBGRAPHS , *GRAPH coloring , *LOGICAL prediction - Abstract
For a graph G and a family of graphs H , the Turán number e x (G , H) is defined to be the maximum number of edges among all H -free subgraphs of G. Inverting this problem, Briggs and Cox (2019) [5] studied the extremal function ε H (k) = s u p { e (G) | e x (G , H) < k } , where e (G) is the size of G , and suggested to investigate the extremal function φ H (k) = s u p { χ (G) | e x (G , H) < k } , where χ (G) denotes the chromatic number of G. Let K n be a complete graph of order n and H a given graph. In this paper, we establish a tight general upper bound for φ H (k) and conjecture φ H (k) = m a x { n | e x (K n , H) < k } for H ≠ 2 K 2. We also confirm this conjecture for many instances of H. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
15. Gallai–Ramsey numbers for multiple triangles.
- Author
-
Zhang, Fangfang, Zhu, Xiutao, and Chen, Yaojun
- Subjects
- *
RAMSEY numbers , *TRIANGLES , *COMPLETE graphs , *GRAPH coloring , *INTEGERS - Abstract
A Gallai coloring of a complete graph is an edge-coloring such that no triangle has all its edges colored differently. A Gallai k -coloring is a Gallai coloring that uses at most k colors. Given an integer k ≥ 2 , and graphs H 1 , H 2 , ... , H k , the Gallai-Ramsey number G R (H 1 , H 2 , ... , H k) is the least positive integer N such that every Gallai k -coloring of the complete graph K N contains a monochromatic copy of H i in color i for some i ∈ { 1 , 2 , ... , k }. Let m G denote the union of m disjoint copies of G. This paper studies the Gallai–Ramsey number G R (t 1 K 3 , ... , t k K 3) for all integers t 1 ≥ t 2 ≥ ⋯ ≥ t k ≥ 1. The case t 1 = t 2 = ⋯ = t k = 1 was obtained by Chung and Graham (1983). In this paper, we obtain a general bound of G R (t 1 K 3 , ... , t k K 3) for all t 1 ≥ t 2 ≥ ⋯ ≥ t k ≥ 1 , and prove that both the upper and lower bounds can be attained for some t i , i ∈ { 1 , ... , k }. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
16. Connectedness of friends-and-strangers graphs of complete bipartite graphs and others.
- Author
-
Wang, Lanchao, Lu, Junying, and Chen, Yaojun
- Subjects
- *
COMPLETE graphs , *BIPARTITE graphs , *RANDOM graphs , *BIJECTIONS - Abstract
Let X and Y be any two graphs of order n. The friends-and-strangers graph FS (X , Y) of X and Y is a graph with vertex set consisting of all bijections σ : V (X) ↦ V (Y) , in which two bijections σ , σ ′ are adjacent if and only if they differ precisely on two adjacent vertices of X , and the corresponding images are adjacent in Y. The most fundamental question that one can ask about these friends-and-strangers graphs is whether or not they are connected. Let K k , n − k be a complete bipartite graph of order n. In 1974, Wilson characterized the connectedness of FS (K 1 , n − 1 , Y) by using algebraic methods. In this paper, by using combinatorial methods, we investigate the connectedness of FS (K k , n − k , Y) for any Y and all k ≥ 2 , including Y being a random graph, as suggested by Defant and Kravitz, and pose some open problems. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
17. Multicolor bipartite Ramsey numbers for quadrilaterals and stars.
- Author
-
Zhang, Xuemei, Weng, Chunyan, and Chen, Yaojun
- Subjects
- *
RAMSEY numbers , *QUADRILATERALS , *BIPARTITE graphs , *COMPLETE graphs , *FINITE fields - Abstract
For bipartite graphs H 1 , ... , H μ , μ ≥ 2 , the μ -color bipartite Ramsey number, denoted by R b (H 1 , ... , H μ) , is the least positive integer N such that if we arbitrarily color the edges of a complete bipartite graph K N , N with μ colors, then it contains a monochromatic copy of H i in color i for some i , 1 ≤ i ≤ μ. Let C 4 and K 1 , n be a quadrilateral and a star on n + 1 vertices, respectively. In this paper, we show that the (μ + 1) -color bipartite Ramsey number R b (C 4 , ... , C 4 , K 1 , n) ≤ n + ⌈ 1 2 μ 2 (4 n + μ 2 + 2 μ − 7) + 4 ⌉ + μ 2 + μ 2 − 1. Moreover, using algebraic methods, we construct Ramsey graphs or near Ramsey graphs and determine infinitely many values of R b (C 4 , ... , C 4 , K 1 , n) , which reach the upper bound if μ = 1 , 2 and are at most ⌊ μ 2 ⌋ less than the upper bound if μ ≥ 3. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
18. Gallai–Ramsey number of odd cycles with chords.
- Author
-
Zhang, Fangfang, Song, Zi-Xia, and Chen, Yaojun
- Subjects
- *
RAMSEY numbers , *ODD numbers , *COMPLETE graphs , *RAMSEY theory , *INTEGERS - Abstract
A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai k -coloring is a Gallai coloring that uses at most k colors. For an integer k ≥ 1 , the Gallai–Ramsey number G R k (H) of a given graph H is the least positive integer N such that every Gallai k -coloring of the complete graph K N contains a monochromatic copy of H. Let C m denote the cycle on m ≥ 4 vertices and let Θ m denote the family of graphs obtained from C m by adding an additional edge joining two non-consecutive vertices. We prove that G R k (Θ 2 n + 1) = n ⋅ 2 k + 1 for all k ≥ 1 and n ≥ 3. This implies that G R k (C 2 n + 1) = n ⋅ 2 k + 1 all k ≥ 1 and n ≥ 3. Our result yields a unified proof for the Gallai–Ramsey number of all odd cycles on at least five vertices. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
19. Gallai-Ramsey number of even cycles with chords.
- Author
-
Zhang, Fangfang, Song, Zi-Xia, and Chen, Yaojun
- Subjects
- *
RAMSEY numbers , *ODD numbers , *COMPLETE graphs , *NUMBER theory , *INTEGERS , *TRIANGLES - Abstract
For a graph H and an integer k ≥ 1 , the k -color Ramsey number R k (H) is the least integer N such that every k -coloring of the edges of the complete graph K N contains a monochromatic copy of H. Let C m denote the cycle on m ≥ 4 vertices and let Θ m denote the family of graphs obtained from C m by adding an additional edge joining two non-consecutive vertices. Unlike Ramsey number of odd cycles, little is known about the general behavior of R k (C 2 n) except that R k (C 2 n) ≥ (n − 1) k + n + k − 1 for all k ≥ 2 and n ≥ 2. In this paper, we study Ramsey number of even cycles with chords under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. For an integer k ≥ 1 , the Gallai-Ramsey number G R k (H) of a graph H is the least positive integer N such that every Gallai k -coloring of the complete graph K N contains a monochromatic copy of H. We prove that G R k (Θ 2 n) = (n − 1) k + n + 1 for all k ≥ 2 and n ≥ 3. This implies that G R k (C 2 n) = (n − 1) k + n + 1 all k ≥ 2 and n ≥ 3. Our result yields a unified proof for the Gallai-Ramsey number of all even cycles on at least four vertices. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.