Browsing by Author "7055a996e0784e4b83db90caa6525b47"
Now showing items 118 of 18

A new class of graphs that satisfies the ChenChvátal conjecture
Aboulker, P.; Matamala Vásquez, Martín; Rochet, P.; Zamora, J. (Wiley, 2018)A wellknown combinatorial theorem says that a set of n noncollinear points in the plane determines at least n distinct lines. Chen and Chvatal conjectured that this theorem extends to metric spaces, with an appropriated ... 
Alternation on cellular automata
Matamala Vásquez, Martín (ELSEVIER, 19970610)In this paper we consider several notions of alternation in cellular automata: nonuniform, uniform and weak alternation. We study relations among these notions and with alternating Turing machines. It is proved that the ... 
Convex ppartitions of bipartite graphs
Grippo, Luciano N.; Matamala Vásquez, Martín; Safe, Martín D.; Stein, Maya (Elsevier, 2016)A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p >= 1, all partitions of the vertex set of a bipartite graph into p convex sets ... 
Dynamic of cyclic automata over Z2
Matamala Vásquez, Martín; Moreno, Eduardo (2004)Let K be the twodimensional grid. Let q be an integer greater than 1 and let Q={0; : : : ; q−1}. Let s :Q → Q be de0ned by s( ) = ( + 1) mod q, ∀ ∈ Q. In this work we study the following dynamic F on QZ2 . For x ∈ QZ2 ... 
Graphs admitting antimagic labeling for arbitrary sets of positive integers
Matamala Vásquez, Martín; Zamora, José (Elsevier, 2017)A connected graph G=(V,E) with m edges is called universal antimagic if for each set B of m positive integers there is an bijective function f:E→B such that the function f˜:V→N defined at each vertex v as the sum of all ... 
Graphs admitting antimagic labeling for arbitrary sets of positive numbers
Matamala Vásquez, Martín; Zamora, José (Elsevier, 2020)Hartsfield and Ringel in 1990 conjectured that any connected graph with q >= 2 edges has an edge labeling f with labels in the set {1,..., q}, such that for every two distinct vertices u and v, f(u) not equal= f(v), where ... 
Injective Colorings with Arithmetic Constraints
Astromujoff, N.; Chapelle, M.; Matamala Vásquez, Martín; Todinca, I.; Zamora, J. (Springer, 2015)An injective coloring of a graph is a vertex labeling such that two vertices sharing a common neighbor get different labels. In this work we introduce and study what we call additive colorings. An injective coloring of a ... 
Lines in bipartite graphs and in 2metric spaces
Matamala Vásquez, Martín; Zamora, José (Wiley, 2020)The line generated by two distinct points, x and y, in a finite metric space M=(V,d), is the set of points given by {z is an element of V:d(x,y)=d(x,z)+d(z,y)ord(x,y)=d(x,z)d(z,y)}. It is denoted by xy over bar M. A ... 
Minimal de Bruijn sequence in a language with forbidden substrings
Moreno Araya, Eduardo; Matamala Vásquez, Martín (2004)Let be the following strategy to construct a walk in a labeled digraph: at each vertex, we follow the unvisited arc of minimum label. In this work we study for which languages, applying the previous strategy over the ... 
Minimal Eulerian circuit in a labeled digraph
Moreno, Eduardo; Matamala Vásquez, Martín (SPRINGERVERLAG BERLIN, 2006)Let G = (V, A) be an Eulerian directed graph with an arclabeling. In this work we study the problem of finding an Eulerian circuit of lexicographically minimal label among all Eulerian circuits of the graph. We prove that ... 
Navigating in a Graph by Aid of Its Spanning Tree
Dragan, Feodor F.; Matamala Vásquez, Martín (2008)Let G = (V,E) be a graph and T be a spanning tree of G. We consider the following strategy in advancing in G from a vertex x towards a target vertex y: from a current vertex z (initially, z = x), unless z = y, go to a ... 
A new family of expansive graphs
Matamala Vásquez, Martín; Zamora, José (ELSEVIER SCIENCE BV, 20080401)An affine graph is a pair (G, ) where G is a graph and is an automorphism assigning to each vertex of G one of its neighbors. On one hand, we obtain a structural decomposition of any affine graph (G, ) in terms of the ... 
The pickup and delivery problem with transfers: Formulation and a branchandcut solution method
Cortés, Cristián E.; Matamala Vásquez, Martín; Contardo, Claudio (ELSEVIER, 2010)In this paper, a strict formulation of a generalization of the classical pickup and delivery problem is presented. Here, we add the flexibility of providing the option for passengers to transfer from one vehicle to another ... 
A quantitative approach to perfect onefactorizations of complete bipartite graphs
Astromujoff, Natacha; Matamala Vásquez, Martín (EJC, 2015)Given a onefactorization F of the complete bipartite graph Kn;n, let pf(F) de note the number of Hamiltonian cycles obtained by taking pairwise unions of perfect matchings in F. Let pf(n) be the maximum of pf(F) over ... 
Reconstructing 3colored grids from horizontal and vertical projections is NPHard: a solution to the 2Atom problem in discrete tomography
Duerr, Christoph; Guinez, Flavio; Matamala Vásquez, Martín (SIAM PUBLICATIONS, 2012)We consider the problem of coloring a grid using k colors with the restriction that each row and each column has a specific number of cells of each color. This problem has been known as the (k  1)atom problem in the ... 
Some remarks about factors of graphs
Correa, José R.; Matamala Vásquez, Martín (JOHN WILEY, 200804)A (g, f)factor of a graph is a subset F of E such that for all v is an element of V, g(v) <= deg(F)(V) <= f(v). Lovasz gave a necessary and sufficient condition for the existence of a (g, f)factor. We extend, to the case ... 
Some remarks on cycles in graphs and digraphs
Loebl, Martin; Matamala Vásquez, Martín (ELSEVIER SCIENCE BV, 20010428)We surveyseveral recent results on cycles of graphs and directed graphs of the following form: ‘Does there exist a set of cycles with a property P that generates all the cycles by operation O?’. 
Vertex partitions and maximum degenerate subgraphs
Matamala Vásquez, Martín (200707)Let G be a graph with maximum degree d â‰¥ 3 and Ï‰(G) â‰¤ d, where Ï‰(G) is the clique number of the graph G. Let p1 and p2 be two positive integers such that d = p1 + p2. In this work, we prove that G has a vertex ...