Search

Given an r -graph (or r -uniform hypergraph) F , the anti-Ramsey number ar (n , r , F) is the minimum number c of colors such that for any edge-coloring of the complete r -graph K n r on n vertices with at least c colors, there is a subgraph F of K n r whose edges have distinct colors. Let S 3 (r) be the linear star of size three in r -graphs. In this paper, we obtain the exact anti-Ramsey number ar (n , r , S 3 (r)) for all r ≥ 3 and sufficiently large n. An r -graph is star-like if all of its edges share at least one common vertex. Moreover, let F be an r -graph which is a vertex-disjoint union of k + 1 star-like r -graphs F 0 , F 1 , ... , F k , where F 0 = S 3 (r) and each F i (i = 1 , ... , k) contains a subgraph isomorphic F 0. We prove that for all r ≥ 3 , k ≥ 1 and sufficiently large n , ar (n , r , F) = ( n r ) − ( n − k r ) + ar (n − k , r , S 3 (r)). [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 a positive integer r and a vertex v of a graph G , let I G ( r ) ( v ) denote the set of independent sets of G that have exactly r elements and contain v . Motivated by a problem of Holroyd and Talbot, Hurlbert and Kamat conjectured that for any r and any tree T , there exists a leaf z of T such that | I T ( r ) ( v ) | ≤ | I T ( r ) ( z ) | for each vertex v of T . They proved the conjecture for r ≤ 4 . We show that for any integer k ≥ 3 , there exists a tree T k that has a vertex x such that x is not a leaf of T k , | I T k ( r ) ( z ) | < | I T k ( r ) ( x ) | for any leaf z of T k and any integer r with 5 ≤ r ≤ 2 k + 1 , and 2 k + 1 is the largest integer s for which I T k ( s ) ( x ) is non-empty. [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]

In 1996, Jendrol’ and Madaras constructed a plane triangulation with minimum degree 5 in which the minimum vertex degree h ( S 5 ) of 5-stars is arbitrarily large. This construction has minor ( 5 , 5 , 5 , 5 ) -stars, that is 5-vertices with four 5-neighbors. It has been open if forbidding minor ( 5 , 5 , 5 , 5 ) -stars makes h ( S 5 ) finite. We prove that every normal plane map with minimum degree 5 and no minor ( 5 , 5 , 5 , 5 ) -stars satisfies h ( S 5 ) ≤ 13 and construct such a map with h ( S 5 ) = 12 . [ABSTRACT FROM AUTHOR]

A classical conjecture of Erdős and Sós asks to determine the Turán number of a tree. We consider variants of this problem in the settings of hypergraphs and multi-hypergraphs. In particular, for all k and r , with r ≥ k (k − 2) , we show that any r -uniform hypergraph H with more than n (k − 1) r + 1 hyperedges contains a Berge copy of any tree with k edges different from the k -edge star. This bound is sharp when r + 1 divides n and for such values of n we determine the extremal hypergraphs. [ABSTRACT FROM AUTHOR]

We consider normal plane maps M 4 ∗ with minimum degree at least 4 and no adjacent 4-vertices. The height of a star is the maximum degree of its vertices. By h ( S k ) and h ( S k ( m ) ) with 1 ≤ k ≤ 4 we denote the minimum height of arbitrary k -stars and k -stars centered at vertices of degree at most 5, respectively, in a given M 4 ∗ . Mohar, Škrekovski, and Voss proved (2003) that every M 4 ∗ satisfies h ( S 4 ) ≤ 107 . We improve this result by proving that h ( S 4 ) ≤ 23 and construct an M 4 ∗ with h ( S 4 ) = 18 . On the other hand, we show that h ( S 4 ( m ) ) = ∞ . Also, we prove that every M 4 ∗ satisfies h ( S 3 ) ≤ 10 and h ( S 3 ( m ) ) ≤ 11 , where both 10 and 11 are sharp. [ABSTRACT FROM AUTHOR]

Let C k denote a cycle of length k , and let S k denote a star with k edges. For multigraphs F , G , and H , a decomposition of F is a set of edge-disjoint subgraphs of F whose union is F , and a ( G , H ) -decomposition of F is a decomposition of F into copies of G and H using at least one of each. In this paper, necessary and sufficient conditions for the existence of a ( C k , S k ) -decomposition of the complete bipartite multigraph are given. [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 G of order N , either G contains G 1 as a subgraph or the complement of G contains G 2 as a subgraph. Let T n be a tree of order n , S n a star of order n , and F m a fan of order 2 m + 1 , i.e., m triangles sharing exactly one vertex. In this paper, we prove that R ( T n , F m ) = 2 n − 1 for n ≥ 3 m 2 − 2 m − 1 , and if T n = S n , then the range can be replaced by n ≥ max { m ( m − 1 ) + 1 , 6 ( m − 1 ) } , which is tight in some sense. [ABSTRACT FROM AUTHOR]

Abstract: Let denote a cycle of length , and let denote a star with edges. For graphs , , and , a of is a decomposition of into copies of and using at least one of each. In this paper, necessary and sufficient conditions for the existence of a -decomposition of the complete bipartite graph with a 1-factor removed are given. [Copyright &y& Elsevier]

Abstract: Let be a graph and let , denote nonempty families of graphs. We write if in any -colouring of edges of with red and blue, there is a red subgraph isomorphic to some graph from or a blue subgraph isomorphic to some graph from . The graph without isolated vertices is said to be a -minimal graph if and for every . The set of all -minimal graphs (up to isomorphism) is called the Ramsey set . We present a procedure, which on the basis of the set of some special graphs, generates an infinite family of -minimal graphs, where and is a family of 2-connected graphs. Moreover, graphs obtained by this procedure can be obtained in linear time with respect to their order. In particular, we present how to obtain infinitely many graphs from Ramsey sets , , for every and , and from Ramsey sets , for and . We show minimal graphs with respect to the number of vertices, which belong to the family , for . We also present graphs which can be used to the construction of infinitely many graphs belonging to the Ramsey set , where and is some family of 2-connected graphs consisting of more than one graph. [Copyright &y& Elsevier]

Abstract: Lebesgue (1940) [13] proved that each plane normal map with minimum degree 5 has a 5-vertex such that the degree-sum (the weight) of its every four neighbors is at most 26. In other words, every has a 4-star of weight at most 31 centered at a 5-vertex. Borodin–Woodall (1998) [3] improved this 31 to the tight bound 30. We refine the tightness of Borodin–Woodall’s bound 30 by presenting six s such that (1) every 4-star at a 5-vertex in them has weight at least 30 and (2) for each of the six possible types , , , , , and of 4-stars with weight 30, the 4-stars of this type at 5-vertices appear in precisely one of these six s. [Copyright &y& Elsevier]

Abstract: We prove that every normal plane map has a -edge, or a -path, or a -path, or a -path, or a -star, or a -star with and , or a -star. Moreover, none of the above options can be strengthened or dropped. In particular, this extends or strengthens several known results and disproves a related conjecture of Harant and Jendrol’ (2007) [10]. [Copyright &y& Elsevier]

Abstract: In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite graph into paths and stars with edges each. In particular, we find necessary and sufficient conditions for accomplishing this when and , and we give a complete solution when . We also apply the results to show that for nonnegative integers and and positive integers and with , there exists a decomposition of the complete graph into copies of and copies of if and only if . [Copyright &y& Elsevier]

Abstract: For a set of connected graphs, a spanning subgraph of a graph is an -factor if every component of is isomorphic to some member of . Amahashi and Kano [A. Amahashi, M. Kano, On factors with given components, Discrete Math. 42 (1982) 1–6] proved that a graph satisfying for every has a -factor, where is the number of isolated vertices in and denotes the star with edges. Here we exclude small stars from the set and prove that a graph satisfying for every has a -factor. [Copyright &y& Elsevier]

Abstract: Let denote a path of length and let denote a star with edges. As usual denotes the complete graph on vertices. In this paper we investigate the decomposition of into paths and stars, and prove the following results. Theorem A. Let and be nonnegative integers and let be a positive integer. There exists a decomposition of into copies of and copies of if and only if and . Theorem B. Let and be nonnegative integers, let and be positive integers such that and , and let one of the following conditions hold: [(1)] , [(2)] . Then there exists a decomposition of into copies of and copies of . [Copyright &y& Elsevier]

Abstract: Given an integer , a graph and a spanning subgraph of (the backbone of ), a -backbone coloring of is a proper vertex coloring of , in which the colors assigned to adjacent vertices in differ by at least . We study the case where the backbone is either a collection of pairwise disjoint stars or a matching. We show that for a star backbone of the minimum number for which a -backbone coloring of with colors in exists can roughly differ by a multiplicative factor of at most from the chromatic number . For the special case of matching backbones this factor is roughly . We also show that the computational complexity of the problem “Given a graph with a star backbone , and an integer , is there a -backbone coloring of with colors in ?” jumps from polynomially solvable to NP-complete between and (the case is even NP-complete for matchings). We finish the paper by discussing some open problems regarding planar graphs. [Copyright &y& Elsevier]

Abstract: Some classes of configurations in projective planes with polarity are constructed. As the main result, lower bounds for the Ramsey numbers are derived from these geometric structures, which improve some bounds due to Parsons about 30 years ago, and also yield a new class of optimal values: whenever q is a power of 2. Moreover, the constructions also imply a known result on bipartite Ramsey numbers. [Copyright &y& Elsevier]

Abstract: An x-star trade consists of two disjoint decompositions of some simple graph H into copies of , the graph known as the x-star. The number of vertices of H is referred to as the foundation of the trade, while the number of copies of in each of the decompositions is called the volume of the trade. We determine all values of x, and s for which there exists a -trade of volume s and foundation . [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: 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]

A graph H is defined to be light in a family H of graphs if there exists a finite number w(H,H) such that each G∈H which contains H as a subgraph, contains also a subgraph KH such that the sum of degrees (in G) of the vertices of K (that is, the weight of K in G) is at most w(H,H). In this paper we study the conditions related to the weight of fixed subgraphs of the plane graphs which can enforce the existence of light graphs in some families of plane graphs. For the families of plane graphs and triangulations whose edges are of weight ⩾w we study the necessary and sufficient conditions for the lightness of certain graphs according to values of w. [Copyright &y& Elsevier]