URV's Author/s:  Rodríguez Velázquez, Juan Alberto

Author, as appears in the article.:  Alberto RodriguezVelazquez, Juan;

Author's mail:  juanalberto.rodriguez@urv.cat

Author identifier:  0000000290827647

Journal publication year:  2022

Publication Type:  Journal Publications

APA:  Alberto RodriguezVelazquez, Juan; (2022). UNIVERSAL LINES IN GRAPHS. Quaestiones Mathematicae, 45(10), 14851500. DOI: 10.2989/16073606.2021.1950862

Papper original source:  Quaestiones Mathematicae. 45 (10): 14851500

Abstract:  In a metric space M = (X, d), a line induced by two distinct points x, x ' is an element of X, denoted by LM{x, x'}, is the set of points given byLM{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 LM{x, x'} gis universal whenever LM{x, x'} = X.Chen and Chvatal [Disc. Appl. Math. 156 (2008), 21012108.] 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.

Article's DOI:  10.2989/16073606.2021.1950862

Link to the original source:  https://www.tandfonline.com/doi/abs/10.2989/16073606.2021.1950862

Papper version:  info:eurepo/semantics/acceptedVersion

licence for use:  https://creativecommons.org/licenses/by/3.0/es/

Department:  Enginyeria Informàtica i Matemàtiques

Licence document URL:  https://repositori.urv.cat/ca/protecciodedades/

Thematic Areas:  Mathematics (miscellaneous) Mathematics Matemática / probabilidade e estatística

Keywords:  Universal lines Product graphs Metric spaces Lines in graphs Distance in graph

Entity:  Universitat Rovira i Virgili

Record's date:  20240907
