Catálogo de publicaciones - libros

We give an algebraic characterization of all convex polygons that are 2-flat foldable to a square, that is, we determine all shapes of convex developments of a doubly-covered square.

A folding of a simple polygon into a convex polyhedron is accomplished by glueing portions of the perimeter of the polygon together to form a polyhedron. A polygon is a of a polygon if can be folded to exactly cover the surface of times, with no part of the surface of left over. In this paper we focus on a specific type of flat 2-foldings, flat 2-foldings that ; that is, foldings of that cover both sides of exactly once. We determine, for any , all the possible flat 2-foldings of a regular -gon. We finish our paper studying the set of polygons that are flat 2-foldable to regular polygons.

Let ≥ 7. Then there exists a uniform covering of 2-paths with 6-paths in if and only if ≡ 0,1,2 (mod 5).

To a regular -gon into a convex polyhedron is to form the polyhedron by gluing portions of the perimeter of the -gon together, the -gon is a net of the polyhedron. In this paper we identify all convex polyhedra which are foldable from an equilateral triangle.

An of a graph = (,) is a matching such that no two edges of are joined by an edge of E/ In general, the problem of finding a maximum induced matching of a graph is known to be NP-hard. In random -regular graphs, the problem of finding a maximum induced matching has been studied for ∈ {3, 4, ..., 10 }. This was due to Duckworth et al.(2002) where they gave the asymptotically almost sure lower bounds and upper bonds on the size of maximum induced matchings in such graphs. The asymptotically almost sure lower bounds were achieved by analysing a degree-greedy algorithm using the differential equation method, whilst the asymptotically almost sure upper bounds were obtained by a direct expectation argument. In this paper, using the , we will show the asymptotically almost sure existence of an induced matching of certain size in random -regular graphs, for ∈ {3,4, 5}. This result improves the known asymptotically almost sure lower bound obtained by Duckworth et al.(2002).

We deal with the problem of labeling the vertices, edges and faces of a special class of plane graphs with 3-sided internal faces in such a way that the label of a face and the labels of the vertices and edges surrounding that face all together add up to the weight of that face. These face weights then form an arithmetic progression with common difference .

In this survey paper we present a general framework for coloring problems that was introduced in a joint paper which the author presented at WG2003. We show how a number of different types of coloring problems, most of which have been motivated from frequency assignment, fit into this framework. We give a survey of the existing results, mainly based on and strongly biased by joint work of the author with several different groups of coauthors, include some new results, and discuss several open problems for each of the variants.

The of a graph is the minimum number of edges in whose removal results in a planar graph. In this paper, we show that the skewness of the generalized Petersen graph (3, ) is , where ≥ 4. As a byproduct, it is shown that for ≥ 4, , where () denotes the crossing number of .

A (,)- is a diregular digraph of degree ≥ 4, diameter ≥ 3 and the number of vertices  +  + ... + . The existence problem of (,)-digraphs is one of difficult problem. In this paper, we will present some new necessary conditions for the existence of such digraphs.

A graph whose vertices can be represented by distinct points in the plane such that points representing adjacent vertices are 1 unit apart is called a . Not all graphs are unit distance graphs. However, if every edge of a graph is subdivided by inserting a new vertex, then the resulting graph is a unit-distance graph. The minimum number of new vertices to be inserted in the edges of a graph to obtain a unit-distance graph is called the , denoted by sd(). We show here in a different and easier way the known result sd() = ( − 1)( − ) when ≥ (–1). This result is used to show that the subdivision number of the complete graph is asymptotic to (), its number of edges. Likewise, the subdivision number of the complete bipartite graph is asymptotic to , its number of edges. More generally, the subdivision number of the complete -partite graph is asymptotic to its number of edges.