Now showing items 1-18 of 18

    • A new class of graphs that satisfies the Chen-Chvátal conjecture 

      Aboulker, P.; Matamala Vásquez, Martín; Rochet, P.; Zamora, J. (Wiley, 2018)
      A well-known combinatorial theorem says that a set of n non-collinear 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, 1997-06-10)
      In this paper we consider several notions of alternation in cellular automata: non-uniform, uniform and weak alternation. We study relations among these notions and with alternating Turing machines. It is proved that the ...
    • Convex p-partitions 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 two-dimensional 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 2-metric 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 (SPRINGER-VERLAG BERLIN, 2006)
      Let G = (V, A) be an Eulerian directed graph with an arc-labeling. 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, 2008-04-01)
      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 branch-and-cut 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 one-factorizations of complete bipartite graphs 

      Astromujoff, Natacha; Matamala Vásquez, Martín (E-JC, 2015)
      Given a one-factorization 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 3-colored grids from horizontal and vertical projections is NP-Hard: a solution to the 2-Atom 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, 2008-04)
      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, 2001-04-28)
      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 (2007-07)
      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 ...