Catálogo de publicaciones - libros

For a planar point set in general position, we study the ratio between the maximum area of an empty triangle with vertices in and the area of the convex hull of .

Let ,,, be positive integers such that 1 ≤ ≤ , 1≤ ≤ and 1≤ ≤ . Then we give a necessary and sufficient condition for a configuration with red points and blue points on a line to have an interval containing precisely red points and blue points.

Kano et al. proved that if , , ..., are pairwise disjoint collections of points in general position, then there exist spanning trees , , ..., , of , , ..., , respectively, such that the edges of  ∪  ∪ ... ∪  intersect in at most ( – 1) – ( – 1)/2 points. In this paper we show that this result is asymptotically tight within a factor of 3/2. To prove this, we consider collections, that is, collections such that the points in : =  ∪  ∪ ... ∪  are in convex position, and the points of the ’s alternate in the convex hull of .

Let ≥ 1 be an integer and let be a graph having a sufficiently large order . Suppose that is even, the minimum degree of is at least + 2, and the degree sum of each pair of nonadjacent vertices in is at least + , where = 3 for odd and = 4 for even . Then has a – factor (i.e. a – regular spanning subgraph) which is edge-disjoint from a given Hamiltonian cycle. The lower bound on the degree condition is sharp. As a consequence, we have an Ore-type condition for graphs to have a – factor containing a given Hamiltonian cycle.

A topological graph is a graph drawn in the plane so that its edges are represented by Jordan arcs. is called , if any two edges have at most one point in common. It is shown that the maximum number of edges of a simple topological graph with vertices and no pairwise disjoint edges is (log) edges. The assumption that is simple cannot be dropped: for every , there exists a complete topological graph of vertices, whose any two edges cross at most twice.

For a graph , a subset ⊆ (), is said to be a of if if ∖ is acyclic. The cardinality of smallest decycling set of is called the of and it is denoted by ().

Bau and Beineke posed the following problems: Which cubic graphs with | | = 2 satisfy ? In this paper, we give an answer to this problem.

In this paper, we consider the problem of packing two or more equal area polygons with disjoint interiors into a convex body in such that each of them has at most a given number of sides. We show that for a convex quadrilateral of area 1, there exist internally disjoint triangles of equal area such that the sum of their areas is at least . We also prove results for other types of convex polygons . Furthermore we show that in any centrally symmetric convex body of area 1, we can place two internally disjoint -gons of equal area such that the sum of their areas is at least . We conjecture that this result is true for any convex bodies.

We consider the problem for directed planar graphs. We show that planar digraphs with diameter 2 and maximum out-degree and in-degree , ≥ 41, cannot have more than 2 vertices. We show that 2 is the best possible upper bound by constructing planar digraphs of diameter 2 having exactly 2 vertices.

Furthermore, we give upper and lower bounds for the largest possible order of planar digraphs with diameter greater than 2.

For a graph = (,), a bijection from () ∪ () into { 1,2, ..., ∣ () ∣ + ∣ () ∣ } is called (,)-edge-antimagic total labeling of if the edge-weights () = () + () + (), ∈ (), form an arithmetic progression with initial term and common difference . An (,)-edge-antimagic total labeling is called super (,)-edge-antimagic total if (()) = { 1,2,..., ∣ () ∣ } .

We study super (,)-edge-antimagic total properties of stars and caterpillar .

For given graphs G and H, the (,) is the smallest positive integer such that every graph of vertices satisfies the following property: either contains or the complement of contains . In this paper, we show that the Ramsey number for ≥ 6.

05C55, 05D10.