Search

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]