Search

Given a graph G and a graph property P we say that G is minimal with respect to P if no proper induced subgraph of G has the property P. An HC-obstruction is a minimal 2-connected non-Hamiltonian graph. Given a graph H , a graph G is H -free if G has no induced subgraph isomorphic to H. The main motivation for this paper originates from a theorem of Duffus, Gould, and Jacobson (1981), which characterizes all the minimal connected graphs with no Hamiltonian path. In 1998, Brousek characterized all the claw-free HC-obstructions. On a similar note, Chiba and Furuya (2021), characterized all (not only the minimal) 2-connected non-Hamiltonian { K 1 , 3 , N 3 , 1 , 1 } -free graphs. Recently, Cheriyan, Hajebi, and two of us (2022), characterized all triangle-free HC-obstructions and all the HC-obstructions which are split graphs. A wheel is a graph obtained from a cycle by adding a new vertex with at least three neighbors in the cycle. In this paper we characterize all the HC-obstructions which are wheel-free graphs. [ABSTRACT FROM AUTHOR]

For graphs G 1 and G 2 , the Ramsey number R ( G 1 , G 2 ) is the smallest integer N such that, for any graph G of order N , G contains G 1 as a subgraph or the complement of G contains G 2 as a subgraph. Let T n denote a tree of order n , W n a wheel of order n + 1 and F n a fan of order 2 n + 1 . We establish Ramsey numbers for fans and trees versus wheels of even order, thereby extending several known results. In particular, we prove that R ( F n , W m ) = 6 n + 1 for odd m ≥ 3 and n ≥ ( 5 m + 3 ) / 4 , and that R ( T n , W m ) = 3 n − 2 for odd m ≥ 3 and n ≥ m − 2 , and T n being a tree for which the Erdős–Sós Conjecture holds. [ABSTRACT FROM AUTHOR]

Given two graphs G , H and a positive integer k , the Gallai-Ramsey number gr k (G : H) is the minimum integer N such that for all n ≥ N , every exact k -edge-coloring of K n contains either a rainbow copy of G or a monochromatic copy of H. A fan F q is obtained from a matching of size q by adding a vertex adjacent to all vertices in the matching; while a wheel graph W s is obtained from a cycle of size s − 1 by adding a vertex adjacent to all vertices on the cycle. In this paper, we determine either the exact values or some bounds for the Gallai-Ramsey numbers gr k (P 5 : H) (k ≥ 3) where H is either a fan or a wheel graph. [ABSTRACT FROM AUTHOR]

Abstract: Given two graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or its complement contains . Let denote a cycle of order and a wheel of order . In this paper, it is shown that for odd, and , and for odd and . [Copyright &y& Elsevier]

Abstract: Orthogonal Latin squares (OLS) are fundamental combinatorial objects with important theoretical properties and interesting applications. OLS can be represented by integer points satisfying a certain system of equalities. The convex hull of these points is the OLS polytope. This paper adds to the description of the OLS polytope by providing non-trivial facets arising from wheels. Specifically, for each wheel of size five, we identify the variables that can be added to the induced inequality, thus obtaining all distinct families of maximally lifted wheel inequalities. Each of these families induces facets of the OLS polytope which can be efficiently separated in polynomial time. [Copyright &y& Elsevier]

Abstract: We characterize all of the ways to represent the wheel matroids and whirl matroids using frame matroids of signed graphs. The characterization of wheels is in terms of topological duality in the projective plane and the characterization of whirls is in terms of topological duality in the annulus. [Copyright &y& Elsevier]

Abstract: For two given graphs F and H, the Ramsey number is the smallest positive integer p such that for every graph G on p vertices the following holds: either G contains F as a subgraph or the complement of G contains H as a subgraph. In this paper, we study the Ramsey numbers , where is a path on n vertices and is the graph obtained from a cycle on m vertices by adding a new vertex and edges joining it to all the vertices of the cycle. We present the exact values of for the following values of n and m: or 5 and ; and or 7; and (m is odd, ) or (m is even, ); odd and or or ; odd and with . Moreover, we give nontrivial lower bounds and upper bounds for for the other values of m and n. [Copyright &y& Elsevier]

Abstract: In this paper we show that the Ramsey number for even m and . [Copyright &y& Elsevier]

Abstract: For given graphs G and the Ramsey number is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains In this paper, we investigate the Ramsey number , where G is a tree and H is a wheel or a complete graph . We show that if , then for , even n and for and odd n. We also show that . [Copyright &y& Elsevier]

Abstract: In this paper, we prove that if every vertex of a simple graph has degree at least , then it has a subgraph that is isomorphic to a subdivision of a -wheel. We then extend a result of Dirac showing that every graph with a chromatic number exceeding n has a subgraph that is a subdivision of the n-wheel. [Copyright &y& Elsevier]

Abstract: We study the Ramsey number for a star on vertices and a wheel on vertices. We show that the Ramsey number for , and , where and odd. In addition, we give the following lower bound for where is even: for all . [Copyright &y& Elsevier]

The k-wheel Wk is the graph obtained as a join of a vertex and the cycle of length k. It is proved that a subdivided wheel G embeds isometrically into a hypercube if and only if G is the subdivision graph S(K4) of K4 or G is obtained from the wheel Wk (k⩾3) by subdividing any of its outer-edges with an odd number of vertices. [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 order and a wheel of order . In this paper, we show that for odd, and , which was conjectured by Surahmat, Baskoro and Tomescu. [Copyright &y& Elsevier]

Abstract: For graphs and , the Ramsey number is the smallest positive integer such that every graph F of order contains or the complement of F contains . For the path and the wheel , it is proved that if m is even, , and and if m is odd, , and . [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer n such that for any graph G of order n, either G contains or the complement of G contains . Let denote a path of order n and a wheel of order . In this paper, we show that for m even and and for m odd and . [Copyright &y& Elsevier]