Search

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]

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]

An edge-colored graph G is called properly connected if any two vertices are connected by a properly colored path. The proper connection number of a graph G , denoted by p c (G) , is the smallest number of colors that are needed to color G such that it is properly connected. A separating vertex of G is bad if it is contained in at least three blocks, each of which contains at most three vertices. Let G be a graph of order n without bad vertices. In this paper, we show that if the degree sums of any three nonadjacent vertices of a graph G is at least 3 n / 4 and n > 48 , then p c (G) = 2 , which generalizes the results due to Borozan et al. (2012) and Chang et al. (2019). [ABSTRACT FROM AUTHOR]

Let f (d) be the smallest value for which every bridgeless graph G with diameter d admits a strong orientation G ⇀ such that the diameter of G ⇀ is at most f (d). Chvátal and Thomassen (JCT-B, 1978) established general bounds for f (d) and proved that f (2) = 6. Kwok et al. (JCT-B, 2010) showed that 9 ≤ f (3) ≤ 11. In this paper, we determine that f (3) = 9. [ABSTRACT FROM AUTHOR]

For 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 in color i, for some 1 ≤ i ≤ k . Let C m be a cycle of length m and W n a wheel of order n + 1 . In this paper, we show that R (C 4 , C 4 , W n) ≤ n + 4 n + 5 + 3 for n = 42 , 48 , 49 , 50 , 51 , 52 or n ≥ 56 . Furthermore, we prove that R (C 4 , C 4 , W ℓ 2 - ℓ) ≤ ℓ 2 + ℓ + 2 for ℓ ≥ 9 , and if ℓ is a prime power, then the equality holds. [ABSTRACT FROM AUTHOR]

For given 3-uniform hypergraphs H and G , the Ramsey number R (H , G) is the smallest number N such that each red-blue coloring of the edges of the complete 3-uniform hypergraph K N 3 contains either a red copy of H or a blue copy of G . Let C n 3 , P n 3 and S n 3 denote the 3-uniform loose cycle, loose path and star with n edges, respectively. The 2-color Ramsey number of 3-uniform loose path and loose cycle has been determined completely by several researchers. In this paper, we prove that R (P m 3 , S n 3) = 2 n + 1 + m - 1 2 for all m, n with n ≥ 2 m ≥ 2 and R (P m 3 , S n 3) = 2 m + 1 for all m, n with m ≥ 9 4 n . [ABSTRACT FROM AUTHOR]

The generalized Turán number ex (n , K s , F) denotes the maximum number of copies of K s in an n -vertex F -free graph. Let kF denote k disjoint copies of F. Gerbner et al. (2019) [8] gave a lower bound for ex (n , K 3 , 2 C 5) and obtained the magnitude of ex (n , K s , k K r). In this paper, we determine the exact value of ex (n , K 3 , 2 C 5) and described the unique extremal graph for large n. Moreover, we also determine the exact value of ex (n , K r , (k + 1) K r) which generalizes some known results. [ABSTRACT FROM AUTHOR]

For two graphs G 1 and G 2 , the star-critical Ramsey number r ∗ (G 1 , G 2) is the minimum integer k such that any red/blue edge-coloring of K r - 1 ⊔ K 1 , k contains a red copy of G 1 or a blue copy of G 2 , where r is the classical Ramsey number R (G 1 , G 2) and K r - 1 ⊔ K 1 , k is the graph obtained from a K r - 1 and an additional vertex v by joining v to k vertices of K r - 1 . Let C n denote a cycle of order n and W m a wheel of order m + 1 . Hook (2010) proved that r ∗ (C n , W 3) = 2 n for n ≥ 5 . In this paper, it is shown that r ∗ (C n , W m) = 2 n for m odd, n ≥ m ≥ 5 and n ≥ 60 . [ABSTRACT FROM AUTHOR]

Let G be a finite connected undirected graph and G⇀ a strong orientation of G. The diameter of G⇀, denoted by diam(G⇀), is the maximum directed distance between any two vertices of G⇀. The oriented diameter of G is defined as diam⇀(G)=min{diam(G⇀)∣G⇀is a strong orientation ofG}. In this paper, we show that diam⇀(G)≤⌈n∕2⌉ for any maximal outerplanar graph G of order n≥3, with four exceptions, and the upper bound is sharp. [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 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]

For two given sets C1 and C2 of cycles, the Ramsey number R(C1,C2) is the smallest integer N such that for any graph G on N vertices, either G contains a cycle from C1 or G¯ contains a cycle from C2. In this paper, we determine all Ramsey numbers R(C1,C2), which confirms a conjecture due to Hansson, and extends the well‐known Ramsey numbers for two cycles. [ABSTRACT FROM AUTHOR]

In this article, the random vibration test and finite-element simulation analysis of SAC305 solder joints in BGA packaged electronic chips were carried out. A failure model for BGA solder joints was established based on the life data. And vulnerable parts in electronic chips were analyzed. First, the random vibration test was conducted. Second, a lognormal distribution model of solder joints by means of the life data was established and analyzed based on the fracture mechanics theory. Finally, the finite-element simulation model of BGA packaged electronic chip was established and discussed. Failure characteristics of solder joints at different positions in electronic chips were compared and the failure mode of the solder joint was discussed using the simulation result and the observation result with scanning electron microscope (SEM). The results show that the life of each single solder joint in BGA packaged electronic chips follows a logarithmic normal distribution under the random vibration. Solder balls located at the four outermost corners of the chip are subjected to the greatest stress, which are the weakest parts in electronic chips. Cracks in solder joints are generated near the package side and emerged from the edge of the intermetallic compound (IMC) layer with the largest curvature. [ABSTRACT FROM AUTHOR]

For two given graphs G 1 and G 2 , the planar Ramsey number P R (G 1 , G 2) is the smallest integer N such that every planar graph G on N vertices either contains a copy of G 1 or its complement contains a copy of G 2 . In this paper, we determine all planar Ramsey numbers for the complete graphs versus trees. [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]

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]

For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer n such that for any graph G of order n, either G contains G1 or its complement G¯ contains G2. Let Pn,Sn and Tn denote a path, a star and a tree of order n, respectively. A generalized wheel, denoted by Ws,m, is the join of a complete graph Ks and a cycle Cm. In this paper, we show that R(Tn,Ws,4)=(n-1)(s+1)+1 for n≥3,s≥2 and R(Tn,Ws,5)=(n-1)(s+2)+1 for n≥3,s≥1. These generalize some known results on Ramsey numbers for a tree versus a wheel. [ABSTRACT FROM AUTHOR]

The core problem of Ontology mapping and various kinds of ontology engineering applications is the calculation of similarity between concepts in ontology. From the machine learning point of view, by means of learning the sample set, it gets the optimal ontology similarity calculation function, so that each pair of concepts mapped to a positive real number, thus reflected the similarities between concepts. After representing the ontology using graph, the goal of ontology learning is to obtain a real-valued function, which maps each pair of vertices into real axes and uses distances to reflect the similarities between concepts of vertices. In this paper, we present an ontology learning algorithm in view of ontology geometry distance computation and deep learning tricks. The iteration procedure is designed and the experiments show the effectiveness of given ontology algorithm. [ABSTRACT FROM AUTHOR]

For a graph G = ( V , E ) , the eccentric connectivity index of G , denoted by ξ c ( G ), is defined as ξ c ( G ) = ∑ v ∈ V ɛ ( v ) d ( v ) , where ɛ( v ) and d ( v ) are the eccentricity and the degree of v in G , respectively. In this paper, we first establish the sharp lower bound for the eccentric connectivity index in terms of the order and the minimum degree of a connected G , and characterize some extremal graphs, which generalize some known results. Secondly, we characterize the extremal trees having the maximum or minimum eccentric connectivity index for trees of order n with given degree sequence. Finally, we give a sharp lower bound for the eccentric connectivity index in terms of the order and the radius of a unicyclic G , and characterize all extremal graphs. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n and k an integer not great than n. Erdős and Sós conjectured that if G has at least n ( k − 2 ) / 2 edges, then G contains all trees of order k. Loebl, Komlós and Sós conjectured that if at least n / 2 vertices of G have degree at least k − 1 , then G contains all trees of order k. In this paper, it is shown that both the conjectures are true for graphs with independence number two, and our results generalize some known results. [ABSTRACT FROM AUTHOR]

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]

A graph G is a fractional $ (a,b,n) $ (a , b , n) -critical graph if removing any n vertices from G, the resulting subgraph still admits a fractional $ [a,b] $ [ a , b ] -factor. In this paper, we determine the exact tight isolated toughness bound for fractional $ (a,b,n) $ (a , b , n) -critical graphs. To be specific, a graph G is fractional $ (a,b,n) $ (a , b , n) -critical if $ \delta (G)\ge a+n $ δ (G) ≥ a + n and $ I(G)>a-1+\frac {n+1}{n_{a,b}} $ I (G) > a − 1 + n + 1 n a , b , where $ n_{a,b}\ge 2 $ n a , b ≥ 2 is an integer satisfies $ (n_{a,b}-1)a\le b\le n_{a,b}a-1 $ (n a , b − 1) a ≤ b ≤ n a , b a − 1. Furthermore, the sharpness of bounds is showcased by counterexamples. Our contribution improves a result from [W. Gao, W. Wang, and Y. Chen, Tight isolated toughness bound for fractional $ (k,n) $ (k , n) -critical graphs, Discrete Appl. Math. 322 (2022), 194–202] which established the tight isolated toughness bound for fractional $ (k,n) $ (k , n) -critical graphs. [ABSTRACT FROM AUTHOR]

In this article, the kinetic stabilization processes of ultrathin polystyrene (PS) films with different molecular weights ( M w ) and interfacial conditions were monitored by controlling the cooling rate. We found that, for the high M w PS ultrathin film, the fictive temperature ( T f ) of liquid-cooled sample shows large change in a broad range of cooling rates while the kinetic stability proves no obvious variation. By using the low M w PS ultrathin film, the kinetic stability begins to show cooling rate dependence, which indicates the modification of kinetic stability of shorter polymer chains is easier. With the aid of fluorescence resonance energy transfer (FRET) method, the variations of inter-chain proximity of polymer chains with the cooling rate were investigated for both oligomer and high M w PS thin films, and the former is more remarkable. Given that the further the inter-chain proximity, the higher the degree of excess free volume, there are more space for the rearrangement of chains of low M w polymer ultrathin films to reach energy-minimum configurations during cooling. Additionally, the shift of T g,dyn after cooling can be enlarged or removed by introducing a mobile interface or burying the free surface. These results suggest that the kinetic stability of liquid-cooled ultrathin films may stay unchanged when fictive temperature varies obviously, and it can be modified by controlling the molecular weight of polymer and the interfacial condition. [ABSTRACT FROM AUTHOR]

As an efficient theoretical tool, graph theory is widely used in computing chemistry. In terms of index computation on molecular graphs, the researchers can learn the potential properties of chemical compounds, including drugs, materials, and organics. In this paper, by means of distance computation, we study the eccentric version indices of cycloalkanes which occur quite frequently in the chemical drugs and other compounds. The promising prospects of the application for the physical, chemical, medical, and pharmacy engineering are illustrated by theoretical conclusions obtained in this article. [ABSTRACT FROM AUTHOR]

Consider two graphs X and Y , each with n vertices. 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) , where 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. Recently, Alon, Defant and Kravitz showed that if X and Y are two independent random graphs in G (n , p) , then the threshold probability guaranteeing the connectedness of FS (X , Y) is p 0 = n − 1 / 2 + o (1) , and suggested to investigate the general asymmetric situation, that is, X ∈ G (n , p 1) and Y ∈ G (n , p 2). In this paper, we show that if p 1 p 2 ≥ p 0 2 = n − 1 + o (1) and p 1 , p 2 ≥ w (n) p 0 , where w (n) → 0 as n → ∞ , then FS (X , Y) is connected with high probability, which extends the result on p 1 = p 2 = p , due to Alon, Defant and Kravitz. [ABSTRACT FROM AUTHOR]

For two given graphs G 1 and G 2 , the Ramsey number R ( G 1 , G 2 ) is the smallest integer N such that for any graph of order N , either G contains a copy of G 1 or its complement contains a copy of G 2 . Let C m be a cycle of length m and K 1 , n a star of order n + 1 . Parsons (1975) [6] shows that R ( C 4 , K 1 , n ) ≤ n + ⌊ n − 1 ⌋ + 2 for all n ≥ 2 and the equality holds if n is the square of a prime power. Let q be a prime power. In this paper, we first construct a graph Γ q on q 2 − 1 vertices without C 4 by using the Galois field F q , and then we prove that R ( C 4 , K 1 , ( q − 1 ) 2 + t ) = ( q − 1 ) 2 + q + t for q ≥ 4 is even and t = 1 , 0 , − 2 , and R ( C 4 , K 1 , q ( q − 1 ) − t ) = q 2 − t for q ≥ 5 is odd and t = 2 , 4 , . . . , 2 ⌈ q 4 ⌉ . [ABSTRACT FROM AUTHOR]

For two given graphs G 1 and G 2 , the Ramsey number R ( G 1 , G 2 ) is the smallest integer N such that for any graph of order N , either G contains a copy of G 1 or its complement contains a copy of G 2 . Let C m be a cycle of length m and K 1 , n a star of order n + 1 . Parsons (1975) shows that R ( C 4 , K 1 , n ) ≤ n + ⌊ n − 1 ⌋ + 2 and if n is the square of a prime power, then the equality holds. In this paper, by discussing the properties of polarity graphs whose vertices are points in the projective planes over Galois fields, we prove that R ( C 4 , K 1 , q 2 − t ) = q 2 + q − ( t − 1 ) if q is an odd prime power, 1 ≤ t ≤ 2 ⌈ q 4 ⌉ and t ≠ 2 ⌈ q 4 ⌉ − 1 , which extends a result on R ( C 4 , K 1 , q 2 − t ) obtained by Parsons (1976). [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]

We consider proper edge colorings of a graph G using colors of the set { 1 , … , k } . Such a coloring is called neighbor sum distinguishing if for any u v ∈ E ( G ) , the sum of colors of the edges incident to u is different from the sum of the colors of the edges incident to v . The smallest value of k in such a coloring of G is denoted by ndi Σ ( G ) . Let mad ( G ) and Δ ( G ) denote the maximum average degree and the maximum degree of a graph G , respectively. In this paper we show that, for a graph G without isolated edges, if mad ( G ) < 8 3 , then ndi Σ ( G ) ≤ max { Δ ( G ) + 1 , 7 } ; and if mad ( G ) < 3 , then ndi Σ ( G ) ≤ max { Δ ( G ) + 2 , 7 } . [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n ≥ 3 . The remoteness ρ = ρ ( G ) is the maximum, over all vertices, of the average distance from a vertex to all others. The radius r = r ( G ) is the minimum, over all vertices, of the eccentricity of a vertex. Aouchiche and Hansen (2011) conjectured that ρ − r ≥ 3 − n 4 if n is odd and ρ − r ≥ 2 n − n 2 4 ( n − 1 ) if n is even. In this paper, we confirm this conjecture. In addition, we completely characterize extremal graphs attaining the lower bound. [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]

A graph G is a fractional $ (a,b,n) $ (a , b , n) -critical graph if removing any n vertices from G, the resulting subgraph still admits a fractional $ [a,b] $ [ a , b ] -factor. In this paper, we determine the exact tight isolated toughness bound for fractional $ (a,b,n) $ (a , b , n) -critical graphs. To be specific, a graph G is fractional $ (a,b,n) $ (a , b , n) -critical if $ \delta (G)\ge a+n $ δ (G) ≥ a + n and $ I(G)>a-1+\frac {n+1}{n_{a,b}} $ I (G) > a − 1 + n + 1 n a , b , where $ n_{a,b}\ge 2 $ n a , b ≥ 2 is an integer satisfies $ (n_{a,b}-1)a\le b\le n_{a,b}a-1 $ (n a , b − 1) a ≤ b ≤ n a , b a − 1. Furthermore, the sharpness of bounds is showcased by counterexamples. Our contribution improves a result from [W. Gao, W. Wang, and Y. Chen, Tight isolated toughness bound for fractional $ (k,n) $ (k , n) -critical graphs, Discrete Appl. Math. 322 (2022), 194–202] which established the tight isolated toughness bound for fractional $ (k,n) $ (k , n) -critical graphs. [ABSTRACT FROM AUTHOR]

Abstract: For two given graphs and , the planar Ramsey number is the smallest integer such that for any planar graph on vertices, either contains or its complement contains . Let denote a cycle of length and a complete graph of order . Sun, Yang, Lin and Song conjectured that and the conjecture was proved for . In this paper, it is shown that which confirms the conjecture for . [Copyright &y& Elsevier]

Isolated toughness of graph G is formulated by minimizing the ratio | S | / i (G − S) over all S ⊆ V (G) with i (G − S) ≥ 2 , where i (G − S) is the number of isolated vertices after removing vertex subset S from G. The previous works reveal that there exist explicit correlations between isolated toughness and fractional critical graphs (a.k.a. the graph admits a fractional factor after deleting given number of vertices). However, among the existing isolated toughness bounds, the term with respect to n (the number of removed vertices) is always at least n. In this paper, the exactly sharp isolated toughness bound for fractional (k , n) -critical graph is determined which reveals that the coefficient of term with regard to n can be reduced to 1/2. It is well acknowledged that some tight toughness related bounds can reach to the extreme value, while others cannot. We give an explanation why these tight bounds in various settings possess such pattern differences. [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 order and a wheel of order . Surahmat, Baskoro and Tomescu conjectured that for odd, and . In this paper, we confirm the conjecture for . [Copyright &y& Elsevier]

Abstract: A graph is 3-domination-critical (3-critical, for short), if its domination number is 3 and the addition of any edge decreases by 1. In this paper, we show that every 3-critical graph with independence number 4 and minimum degree 3 is Hamilton-connected. Combining the result with those in [Y.J. Chen, F. Tian, B. Wei, Hamilton-connectivity of 3-domination critical graphs with , Discrete Mathematics 271 (2003) 1–12; Y.J. Chen, F. Tian, Y.Q. Zhang, Hamilton-connectivity of 3-domination critical graphs with , European Journal of Combinatorics 23 (2002) 777–784; Y.J. Chen, T.C.E. Cheng, C.T. Ng, Hamilton-connectivity of 3-domination critical graphs with , Discrete Mathematics 308 (2008) (in press)], we solve the following conjecture: a connected 3-critical graph is Hamilton-connected if and only if , where is the toughness of . [Copyright &y& Elsevier]

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]

Abstract: For two given graphs and , the Ramsey number is the smallest positive integer such that for any graph of order , either contains or the complement of contains . Let denote a star of order and a wheel of order . In this paper, we show that for and . [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]

Abstract: Let be a graph. A signed dominating function on G is a function such that for each , where is the closed neighborhood of . The weight of a signed dominating function f is . A signed dominating function f is minimal if there exists no signed dominating function g such that and for each . The upper signed domination number of a graph G, denoted by , equals the maximum weight of a minimal signed dominating function of G. In this paper, we establish an tight upper bound for in terms of minimum degree and maximum degree. Our result is a generalization of those for regular graphs and nearly regular graphs obtained in [O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996) 287–293] and [C.X. Wang, J.Z. Mao, Some more remarks on domination in cubic graphs, Discrete Math. 237 (2001) 193–197], respectively. [Copyright &y& Elsevier]

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 we show that for and , with the former result confirming a conjecture due to Erdös, Faudree, Rousseau and Schelp that for and in the case where . [Copyright &y& Elsevier]

Abstract: A graph G is 3-domination critical if its domination number is 3 and the addition of any edge decreases by 1. Let G be a 3-domination critical graph with toughness more than one. It was proved that G is Hamilton-connected for the cases [Y.J. Chen, F. Tian, B. Wei, Hamilton-connectivity of 3-domination critical graphs with , Discrete Math. 271 (2003) 1–12] and [Y.J. Chen, F. Tian, Y.Q. Zhang, Hamilton-connectivity of 3-domination critical graphs with , European J. Combin. 23 (2002) 777–784]. In this paper, we show G is Hamilton-connected for the case . [Copyright &y& Elsevier]

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 m and a complete graph of order . It was conjectured that for and . We show that and , and the latter result confirms the conjecture in the case when . [Copyright &y& Elsevier]

Abstract: Let denote a tree of order and a wheel of order . In this paper, we show the Ramsey numbers for , where if , if or and , and otherwise; for . [Copyright &y& Elsevier]

Abstract: A subset of the vertex set of a graph is called acyclic if the subgraph it induces in contains no cycles. is called an acyclic dominating set of if it is both acyclic and dominating. The minimum cardinality of an acyclic dominating set, denoted by , is called the acyclic domination number of . Hedetniemi et al. [Acyclic domination, Discrete Math. 222 (2000) 151–165] introduced the concept of acyclic domination and posed the following open problem: if is the minimum degree of , is for any graph whose diameter is two? In this paper, we provide a negative answer to this question by showing that for any positive , there is a graph with diameter two such that . [Copyright &y& Elsevier]

Abstract: A graph G is said to be cyclable if for each orientation D of G, there exists a set such that reversing all the arcs with one end in S results in a hamiltonian digraph. Let G be 4-connected simple graph of even order . In this paper, we show that if for any with , then G is cyclable. [Copyright &y& Elsevier]

Abstract: Let be a graph. A subset of is called a dominating set if each vertex of has at least one neighbor in . The domination number equals the minimum cardinality of a dominating set in . A minus dominating function on is a function such that for each , where is the closed neighborhood of . The minus domination number of is . It was incorrectly shown in [X. Yang, Q. Hou, X. Huang, H. Xuan, The difference between the domination number and minus domination number of a cubic graph, Applied Mathematics Letters 16 (2003) 1089–1093] that there is an infinite family of cubic graphs in which the difference can be made arbitrary large. This note corrects the mistakes in the proof and poses a new problem on the upper bound for in cubic graphs. [Copyright &y& Elsevier]

For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest positive integer n such that for any graph G of order n, either G contains G1 or the complement of G contains G2. Let Sn denote a star of order n and Wm a wheel of order m+1. This paper shows that R(Sn,W6)=2n+1 for n≥3 and R(Sn,Wm)=3n-2 for m odd and n≥m-1≥2. [Copyright &y& Elsevier]