Articles producció científica> Enginyeria Informàtica i Matemàtiques

UNIVERSAL LINES IN GRAPHS

  • Dades identificatives

    Identificador: imarina:9225139
    Autors:
    Rodriguez-Velazquez, Juan Alberto
    Resum:
    In a metric space M = (X, d), a line induced by two distinct points x, x ' is an element of X, denoted by L-M{x, x'}, is the set of points given byL-M{x, x'} = {z is an element of X : d(x, x') = d(x, z) + d(z, x') or d(x, x') = |d(x, z) - d(z, x')|}.A line L-M{x, x'} gis universal whenever L-M{x, x'} = X.Chen and Chvatal [Disc. Appl. Math. 156 (2008), 2101-2108.] conjectured that in any finite metric space M = (X, d) either there is a universal line, or there are at least |X| different (nonuniversal) lines. A particular problem derived from this conjecture consists of investigating the properties of M that determine the existence of a universal line, and the problem remains interesting even if we can check that M has at least |X| different lines. Since the vertex set of any connected graph, equipped with the shortest path distance, is a metric space, the problem automatically becomes of interest in graph theory. In this paper, we address the problem of characterizing graphs that have universal lines. We consider several scenarios in which the study can be approached by analysing the existence of such lines in primary subgraphs. We first discuss the wide class of separable graphs, and then describe some particular cases, including those of block graphs, rooted product graphs and corona graphs. We also discuss important classes of nonseparable graphs, including Cartesian product graphs, join graphs and lexicographic product graphs.
  • Altres:

    Autor segons l'article: Rodriguez-Velazquez, Juan Alberto
    Departament: Enginyeria Informàtica i Matemàtiques
    Autor/s de la URV: Rodríguez Velázquez, Juan Alberto
    Paraules clau: Universal lines Product graphs Metric spaces Lines in graphs Distance in graph
    Resum: In a metric space M = (X, d), a line induced by two distinct points x, x ' is an element of X, denoted by L-M{x, x'}, is the set of points given byL-M{x, x'} = {z is an element of X : d(x, x') = d(x, z) + d(z, x') or d(x, x') = |d(x, z) - d(z, x')|}.A line L-M{x, x'} gis universal whenever L-M{x, x'} = X.Chen and Chvatal [Disc. Appl. Math. 156 (2008), 2101-2108.] conjectured that in any finite metric space M = (X, d) either there is a universal line, or there are at least |X| different (nonuniversal) lines. A particular problem derived from this conjecture consists of investigating the properties of M that determine the existence of a universal line, and the problem remains interesting even if we can check that M has at least |X| different lines. Since the vertex set of any connected graph, equipped with the shortest path distance, is a metric space, the problem automatically becomes of interest in graph theory. In this paper, we address the problem of characterizing graphs that have universal lines. We consider several scenarios in which the study can be approached by analysing the existence of such lines in primary subgraphs. We first discuss the wide class of separable graphs, and then describe some particular cases, including those of block graphs, rooted product graphs and corona graphs. We also discuss important classes of nonseparable graphs, including Cartesian product graphs, join graphs and lexicographic product graphs.
    Àrees temàtiques: Mathematics (miscellaneous) Mathematics Matemática / probabilidade e estatística
    Accès a la llicència d'ús: https://creativecommons.org/licenses/by/3.0/es/
    Adreça de correu electrònic de l'autor: juanalberto.rodriguez@urv.cat
    Identificador de l'autor: 0000-0002-9082-7647
    Data d'alta del registre: 2024-10-26
    Versió de l'article dipositat: info:eu-repo/semantics/acceptedVersion
    Enllaç font original: https://www.tandfonline.com/doi/abs/10.2989/16073606.2021.1950862
    URL Document de llicència: https://repositori.urv.cat/ca/proteccio-de-dades/
    Referència a l'article segons font original: Quaestiones Mathematicae. 45 (10): 1485-1500
    Referència de l'ítem segons les normes APA: Rodriguez-Velazquez, Juan Alberto (2022). UNIVERSAL LINES IN GRAPHS. Quaestiones Mathematicae, 45(10), 1485-1500. DOI: 10.2989/16073606.2021.1950862
    DOI de l'article: 10.2989/16073606.2021.1950862
    Entitat: Universitat Rovira i Virgili
    Any de publicació de la revista: 2022
    Tipus de publicació: Journal Publications
  • Paraules clau:

    Mathematics,Mathematics (Miscellaneous)
    Universal lines
    Product graphs
    Metric spaces
    Lines in graphs
    Distance in graph
    Mathematics (miscellaneous)
    Mathematics
    Matemática / probabilidade e estatística
  • Documents:

  • Cerca a google

    Search to google scholar