Pasar al contenido principal

OPTIMIZACION MATEMATICA Y COMBINATORIA EN REDES

PID2019-105824GB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD DE CADIZ

Resultados relacionados

Resultados totales (Incluyendo duplicados): 20
Encontrada(s) 1 página(s)

RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Mutual-visibility problems on graphs of diameter two

  • Cicerone, S.
  • Di Stefano, G.
  • Klavžar, S.
  • González Yero, Ismael
The mutual-visibility problem in a graph G asks for the cardinality of a largest set of vertices S⊆V(G) so that for any two vertices x,y∈S there is a shortest x,y-path P so that all internal vertices of P are not in S. This is also said as x,y are visible with respect to S, or S-visible for short. Variations of this problem are known, based on the extension of the visibility property of vertices that are in and/or outside S. Such variations are called total, outer and dual mutual-visibility problems. This work is focused on studying the corresponding four visibility parameters in graphs of diameter two, throughout showing bounds and/or closed formulae for these parameters. The mutual-visibility problem in the Cartesian product of two complete graphs is equivalent to (an instance of) the celebrated Zarankiewicz's problem. Here we study the dual and outer mutual-visibility problem for the Cartesian product of two complete graphs and all the mutual-visibility problems for the direct product of such graphs as well. We also study all the mutual-visibility problems for the line graphs of complete and complete bipartite graphs. As a consequence of this study, we present several relationships between the mentioned problems and some instances of the classical Turán problem. Moreover, we study the visibility problems for cographs and several non-trivial diameter-two graphs of minimum size.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Incidence dimension and 2-packing number in graphs

  • Bozovic, Dragana
  • Kelenc, Aleksander
  • Peterin, Iztok
  • González Yero, Ismael
Let G = (V, E) be a graph. A set of vertices A is an incidence generator for G if for any two distinct edges e, f is an element of E(G) there exists a vertex from A which is an endpoint of either e or f. The smallest cardinality of an incidence generator for G is called the incidence dimension and is denoted by dim(I)(G). A set of vertices P subset of V(G) is a 2-packing of G if the distance in G between any pair of distinct vertices from P is larger than two. The largest cardinality of a 2-packing of G is the packing number of G and is denoted by rho(G). In this article, the incidence dimension is introduced and studied. The given results show a close relationship between dim(I)(G) and rho(G). We first note that the complement of any 2-packing in graph G is an incidence generator for G, and further show that either dim(I)(G) = |V(G)-|rho(G) or dim(I)(G) = |V(G)-|rho(G) - 1 for any graph G. In addition, we present some bounds for dim(I)(G) and prove that the problem of determining the incidence dimension of a graph is NP-hard., Dragana Bozovic, Aleksander Kelenc and Iztok Peterin are partially supported by the Slovenian Research Agency by the project No. J1-1693 and J1-9109. Ismael G. Yero has been partially supported by the Spanish Ministry of Science and Innovation through the grant PID2019-105824GB-I00.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

A note on the metric and edge metric dimensions of 2-connected graphs

  • Knor, Martin
  • Škrekovski, Riste
  • González Yero, Ismael
For a given graph G, the metric and edge metric dimensions of G, dim(G) and edim(G), are the cardinalities of the smallest possible subsets of vertices in V(G) such that they uniquely identify the vertices and the edges of G, respectively, by means of distances. It is already known that metric and edge metric dimensions are not in general comparable. Infinite families of graphs with pendant vertices in which the edge metric dimension is smaller than the metric dimension are already known. In this article, we construct a 2-connected graph G such that dim(G) = a and edim(G) = b for every pair of integers a, b, where 4 ≤ b < a. For this we use subdivisions of complete graphs, whose metric dimension is in some cases smaller than the edge metric dimension. Along the way, we present an upper bound for the metric and edge metric dimensions of subdivision graphs under some special conditions., 7 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Traversing a graph in general position

  • Klavžar, Sandi
  • Krishnakumar, Aditi
  • Tuite, James
  • González Yero, Ismael
Let G be a graph. Assume that to each vertex of a set of vertices S subset of V(G) a robot is assigned. At each stage one robot can move to a neighbouring vertex. Then S is a mobile general position set of G if there exists a sequence of moves of the robots such that all the vertices of G are visited while maintaining the general position property at all times. The mobile general position number of G is the cardinality of a largest mobile general position set of G. We give bounds on the mobile general position number and determine exact values for certain common classes of graphs, including block graphs, rooted products, unicyclic graphs, Kneser graphs K(n, 2) and line graphs of complete graphs., 13 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Total Mutual-Visibility in Graphs with Emphasis on Lexicographic and Cartesian Products

  • Kuziak, Dorota
  • Rodríguez Velázquez, Juan A.
Given a connected graph G, the total mutual-visibility number of G, denoted μt(G) , is the cardinality of a largest set S⊆ V(G) such that for every pair of vertices x, y∈ V(G) there is a shortest x, y-path whose interior vertices are not contained in S. Several combinatorial properties, including bounds and closed formulae, for μt(G) are given in this article. Specifically, we give several bounds for μt(G) in terms of the diameter, order and/or connected domination number of G and show characterizations of the graphs achieving the limit values of some of these bounds. We also consider those vertices of a graph G that either belong to every total mutual-visibility set of G or does not belong to any of such sets, and deduce some consequences of these results. We determine the exact value of the total mutual-visibility number of lexicographic products in terms of the orders of the factors, and the total mutual-visibility number of the first factor in the product. Finally, we give some bounds and closed formulae for the total mutual-visibility number of Cartesian product graphs., 17 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Variety of mutual-visibility problems in graphs

  • Cicerone, Serafino
  • Di Stefano, Gabriele
  • Drožđek, Lara
  • Hedžet, Jaka
  • Klavžar, Sandi
  • González Yero, Ismael
If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u,v-path P such that V(P)∩X⊆{u,v}. If each two vertices from X are X-visible, then X is a mutual-visibility set. The mutual-visibility number of G is the cardinality of a largest mutual-visibility set of G and has been already investigated. In this paper a variety of mutual-visibility problems is introduced based on which natural pairs of vertices are required to be X-visible. This yields the total, the dual, and the outer mutual-visibility numbers. We first show that these graph invariants are related to each other and to the classical mutual-visibility number, and then we prove that the three newly introduced mutual-visibility problems are computationally difficult. According to this result, we compute or bound their values for several graphs classes that include for instance grid graphs and tori. We conclude the study by presenting some inter-comparison between the values of such parameters, which is based on the computations we made for some specific families.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Resolving vertices of graphs with differences

  • Peterin, I.
  • Sedlar, J.
  • Škrekovski, R.
  • González Yero, Ismael
The classical (vertex) metric dimension of a graph G is defined as the cardinality of a smallest set S⊆V(G) such that any two vertices x and y from G have different distances to least one vertex from S. The k-metric dimension is a generalization of that notion where it is required that any pair of vertices has different distances to at least k vertices from S. In this paper, we introduce the weak k-metric dimension of a graph G, which is defined as the cardinality of a smallest set of vertices S such that the sum of the distance differences from any pair of vertices to all vertices of S is at least k. This dimension is “stronger” than the classical metric dimension, yet “weaker” than k-metric dimension, and it can be formulated as an ILP problem. The maximum k for which the weak k-metric dimension is defined is denoted by κ(G). We first prove several properties of the weak k-metric dimension regarding the presence of true or false twin vertices in a graph. Using those properties, the κ(G) is found for some basic graph classes, such as paths, stars, cycles, and complete (bipartite) graphs. We also find κ(G) for trees and grid graphs using the observation that the distance difference increases by the increase of the cardinality of a set S. For all these graph classes we further establish the exact value of the weak k-metric dimension for all k≤κ(G)., European Commission (European Union) European Regional Development Fund (European Union) Ministerio de Ciencia e Innovación (España) Javna Agencija za Raziskovalno Dejavnost RS (Slovenia), 22 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Resolvability and Convexity Properties in the Sierpiński Product of Graphs

  • Henning, M.A.
  • Klavžar, S.
  • González Yero, Ismael
Let G and H be graphs and let f: V(G) → V(H) be a function. The Sierpiński product of G and H with respect to f, denoted by G⊗ fH , is defined as the graph on the vertex set V(G) × V(H) , consisting of |V(G)| copies of H; for every edge gg′ of G there is an edge between copies gH and g′H of H associated with the vertices g and g′ of G, respectively, of the form (g, f(g′)) (g′, f(g)) . The Sierpiński metric dimension and the upper Sierpiński metric dimension of two graphs are determined. Closed formulas are determined for Sierpiński products of trees, and for Sierpiński products of two cycles where the second factor is a triangle. We also prove that the layers with respect to the second factor in a Sierpiński product graph are convex., 17 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Hub location with congestion and time-sensitive demand

  • Domínguez Bravo, Carmen Ana
  • Fernández Areizaga, Elena
  • Lüer Villagra, Armin
This work studies the effect of hub congestion and time-sensitive demand on a hub-and-spoke location/allocation system. The Hub Location with Congestion and Time-sensitive Demand Problem is introduced, which combines these two main characteristics. On the one hand, hubs can be activated at several service levels, each of them characterized by a maximum capacity, expressed as the amount of flow that may circulate through the hub, which is associated with a hub transit time. On the other hand, alternative levels are available for served commodities, where each demand level is characterized by its amount of demand, unit revenue, and maximum service time. In this problem the efficiency of a hub-and-spoke system is given by the maximum net profit it may produce. To the best of our knowledge this is the first work where hub congestion and time-sensitive demand are jointly considered. Two alternative mixed-integer linear programming formulations are proposed. They include a new set of constraints, which are necessary to guarantee the consistency of the obtained solutions under the presence of the capacity-type constraints derived from hub service levels and served demand levels. The efficiency of the formulations is analyzed through a set of computational experiments. The results of the computational experiments allow to study the structure of the obtained solutions and to analyze how the different parameters affect them.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

The Edge Partition Dimension of Graphs

  • Kuziak, Dorota
  • Maritz, Elizabeth
  • Vetrìk, Tomas
  • González Yero, Ismael
Theedgemetric dimension wasintroduced in 2018 and since then, it has been extensively studied. In this paper, we present a different way to obtain resolving structures in graphs in order to gain more insight into the study of edge resolving sets andresolving partitions. We define the edge partition dimension of a connected graph and bound it for graphs of given order andfor graphswithgivenmaximumdegree. Weobtainexactvaluesoftheedgepartitiondimensionformultipartite graphs. Some relations between the edge partition dimension and partition dimension/edge metric dimension are also presented. Moreover, several open problems for further research are stated.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Mutual-visibility in strong products of graphs via total mutual-visibility

  • Cicerone, Serafino
  • Di Stefano, Gabriele
  • Klavžar, Sandi
  • González Yero, Ismael
Let G be a graph and X ⊆ V(G). Then X is a mutual-visibility set if each pair of vertices from X is connected by a geodesic with no internal vertex in X. The mutualvisibility number µ(G) of G is the cardinality of a largest mutual-visibility set. In this paper, the mutual-visibility number of strong product graphs is investigated. As a tool for this, total mutual-visibility sets are introduced. Along the way, basic properties of such sets are presented. The (total) mutual-visibility number of strong products is bounded from below in two ways, and determined exactly for strong grids of arbitrary dimension. Strong prisms are studied separately and a couple of tight bounds for their mutual-visibility number are given.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Integer interval DEA: An axiomatic derivation of the technology and an additive, slacks-based model

  • Arana Jiménez, Manuel
  • Sánchez Gil, María del Carmen
  • Younesi, Atefeh
  • Lozano, Sebastián
The present paper studies the efficiency assessment of Decision-Making Units (DMUs) when their inputs and outputs are de- scribed under uncertainty of the type of integer interval data. An axiomatic derivation of the production possibility set (PPS) is presented. An additive, slacks-based data envelopment analysis (DEA) model is formulated, consisting of two phases. This has required the use of adequate arithmetic and LU-partial orders for integer intervals. This novel integer interval DEA approach is the first step towards DEA models under fuzzy integer intervals, with the extension of the corresponding arithmetic and LU-partial or- ders to fuzzy integer intervals. The proposed method is applied on a dataset, taken from the literature, that involves both continuous and integer interval variables., The first and second authors are partially supported by grant PID2019-105824GB-I00. The fourth author acknowledges the financial support of the Spanish Ministry of Science, Innovation and Universities, grant PGC2018-095786-B-I00.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Nonlocal Metric Dimension of Graphs

  • Klavžar, Sandi
  • Kuziak, Dorota
Nonlocal metric dimension dim nℓ(G) of a graph G is introduced as the cardinality of a smallest nonlocal resolving set, that is, a set of vertices which resolves each pair of non-adjacent vertices of G. Graphs G with dim nℓ(G) = 1 or with dim nℓ(G) = n(G) - 2 are characterized. The nonlocal metric dimension is determined for block graphs, for corona products, and for wheels. Two upper bounds on the nonlocal metric dimension are proved. An embedding of an arbitrary graph into a supergraph with a small nonlocal metric dimension and small diameter is presented., 14 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Tesis doctoral (DoctoralThesis)

New models and solution algorithms for Hub Location and related problems, Nuevos modelos y algoritmos para Localizaci´on de Concentradores y problemas relacionados

  • Zerega Oyarzún, Nicolás Alberto
Esta tesis se enmarca en el área de optimización de redes. Específicamente, desarrolla nuevos modelos y algoritmos de resolución exacta para Problemas de Localización de Concentradores y problemas relacionados con el diseño de redes. La tesis está estructurada en seis capítulos, donde las principales contribuciones científicas se desarrollan en los Capítulos 3-5. El Capítulo 1 ofrece una visión general del área, establece los objetivos principales de la tesis y resume sus resultados principales. El Capítulo 2 introduce el tema principal de esta tesis. Revisa la literatura relevante, destacando tanto los avances teóricos como las aplicaciones prácticas de los Problemas de Localización de Concentradores, junto con extensiones de los modelos fundamentales y trabajos recientes. El Capítulo 3 introduce una novedosa formulación basada en flujo de 2 índices para los Problemas de Localización de Concentradores, que puede adaptarse a una gran clase de modelos de Localización de Concentradores. Debido a su pequeño número de variables, puede ser manejada directamente sin recurrir a reformulaciones donde algunas de las variables son proyectadas. La formulación propuesta es tanto computacionalmente eficiente como versátil para manejar extensiones. El capítulo también desarrolla un nuevo algoritmo de solución que hemos llamado Branch-and-Solve. Las dos principales contribuciones del capítulo son: (i) una formulación fuerte de 2 índices que produce cotas del LP ajustadas, y (ii) el algoritmo Branch-and-Solve, que es novedoso en la literatura de Localización de Concentradores y muestra tanto versatilidad como eficiencia. El Capítulo 4 se centra en el Problema de Localización de Concentradores con Asignación Múltiple. El punto de partida de este capítulo son las adaptaciones al Problema de Localización de Concentradores con Asignación Múltiple de la formulación basada en caminos de 4 índices y la formulación supermodular de 2 índices de Contreras y Fernández (2014). Ambas formulaciones son reforzadas y se demuestra que ambos refuerzos producen la misma cota del LP. Además, demostramos que la cota del LP reforzada coincide con la mejor cota conocida de las formulaciones existentes para el Problema de Localización de Concentradores con Asignación Múltiple. El Capítulo 5 introduce un nuevo Problema de Flujo Multicommodity en el que partes de las rutas de transporte son subcontratadas a proveedores externos. Esto puede modelarse como un problema binivel, el cual se muestra que es NP-duro incluso sin restricciones explícitas de capacidad. Desarrollamos varias formulaciones no lineales y sus linealizaciones, junto con un estudio detallado de las propiedades, características y complejidad del problema. Experimentos computacionales proporcionan información práctica, ilustrando la relevancia y aplicabilidad de las decisiones de subcontratación en el diseño de redes. El Capítulo 6 presenta un resumen de la tesis, junto con algunas conclusiones y direcciones para investigaciones futuras., This thesis is framed within the field of network optimization. Specifically, it develops new models and exact resolution algorithms for Hub Location and related network design problems. The thesis is structured in six chapters, where the main scientific contributions are developed in Chapters 3-5. Chapter 1 gives an overview of the area, states the primary objectives of the thesis, and summarizes its main results. Chapter 2 introduces the main topic of this thesis. It reviews relevant literature, highlighting both theoretical advances and practical applications of Hub Location Problems, along with extensions of the fundamental models and recent work. Chapter 3 introduces a novel 2-index flow based formulation for Hub Location Problems which can be adapted to a large class of Hub Location models. Due to its small number of variables, it can be handled directly without resorting to reformulations where some of the variables are projected out. The proposed formulation is both computationally efficient and versatile in handling extensions. The chapter also develops a new solution algorithm that we have called Branch-and-Solve. The two main contributions of the chapter are: (i) a strong 2-index formulation that produces tight LP bounds, and (ii) the Branch-and-Solve algorithm, which is novel in the Hub Location literature and shows both versatility and efficiency. Chapter 4 focuses on the Multiple Allocation Hub Location Problem. The starting point of this chapter are the adaptations to the Multiple Allocation Hub Location Problem of the path-based 4-index formulation and the supermodular 2-index formulation of Contreras and Fern´andez (2014). Both formulations are reinforced and it is shown that both reinforcements produce the same LP bound. Moreover, we prove that the reinforced LP bound coincides with the best-known LP bound of existing formulations for the Multiple Allocation Hub Location Problem (Hamacher et al., 2004; Mar´ın et al., 2006). Chapter 5 introduces a novel Multicommodity Flow Problem in which parts of transportation paths are outsourced to third-party providers. This can be modeled as a bilevel problem, which is shown to be NP-hard even without explicit capacity constraints. We develop several non-linear formulations and linearizations, along with a detailed study of the problem’s properties, characteristics and complexity. Computational experiments provide practical insights, illustrating the relevance and applicability of outsourcing decisions in network design. Chapter 6 presents a summary of the thesis, along with some conclusions, and future research directions.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

New formulations and solutions for the strategic berth template problem

  • Fernández Areizaga, Elena
  • Muñoz Márquez, Manuel
This paper develops new formulations for the Strategic Berth Template Problem, which combines strategic and operational decisions for medium-term berth planning of a given set of cyclically calling ships. The strategic decisions determine the ship calls that will be served, whereas the operational ones establish the berth template that will be applied in a cyclic fashion in the planning horizon. The proposed formulations use binary variables that classify served ships depending on whether or not their service starts in their arrival cycle or in the next one. This helps modeling the problem, since a closed linear expression can be obtained for the waiting times. Constraints imposing that the availability of the berths is respected at each time period can be derived by defining additional binary variables pointing to the starting service times of the served ships. Aggregating such variables over all berths leads to a relaxed formulation, which can be solved in remarkably small computing times. Furthermore, the solution of an auxiliary subproblem produces feasible solutions to the original problem as well as a simple optimality check. Disaggregating the initial service time variables for the different berths leads to a valid formulation. Numerical results from extensive computational tests over a set of benchmark instances from the literature are presented and analyzed. The obtained results assess the excellent performance of the proposed formulations, which outperform existing ones. (c) 2021 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ ), This research was partially funded by the Spanish Ministry of Economy and Competitiveness and ERDF funds [Grant PID2019-105824GB-I0 0 (MINECO/FEDER) ] . This support is gratefully ac-knowledged. The authors are thankful to Eduardo Lalla-Ruiz who kindly made available to us the set of benchmark instances.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Lower (total) mutual-visibility number in graphs

  • Brešar, B.
  • González Yero, Ismael
Given a graph G, a set X of vertices in G satisfying that between every two vertices in X (respectively, in G) there is a shortest path whose internal vertices are not in X is a mutual-visibility (respectively, total mutual-visibility) set in G. The cardinality of a largest (total) mutual-visibility set in G is known under the name (total) mutual-visibility number, and has been studied in several recent works. In this paper, we propose two lower variants of these concepts, defined as the smallest possible cardinality among all maximal (total) mutual-visibility sets in G, and denote them by μ−(G) and μt−(G), respectively. While the total mutual-visibility number is never larger than the mutual-visibility number in a graph G, we prove that both differences μ−(G)−μt−(G) and μt−(G)−μ−(G) can be arbitrarily large. We characterize graphs G with some small values of μ−(G) and μt−(G), and prove a useful tool called the Neighborhood Lemma, which enables us to find upper bounds on the lower mutual-visibility number in several classes of graphs. We compare the lower mutual-visibility number with the lower general position number, and find a close relationship with the Bollobás-Wessel theorem when this number is considered in Cartesian products of complete graphs. Finally, we also prove the NP-completeness of the decision problem related to μt−(G)
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

Further Contributions on the Outer Multiset Dimension of Graphs

  • Klavžar, Sandi
  • Kuziak, Dorota
  • González Yero, Ismael
The outer multiset dimension dim ms(G) of a graph G is the cardinality of a smallest set of vertices that uniquely recognize all the vertices outside this set by using multisets of distances to the set. It is proved that dim ms(G) = n(G) - 1 if and only if G is a regular graph with diameter at most 2. Graphs G with dim ms(G) = 2 are described and recognized in polynomial time. A lower bound on the lexicographic product of G and H is proved when H is complete or edgeless, and the extremal graphs are determined. It is proved that dimms(Ps□Pt)=3 for s≥ t≥ 2., 15 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

A Steiner general position problem in graph theory

  • Klavžar, Sandi
  • Kuziak, Dorota
  • Peterin, Iztok
  • González Yero, Ismael
Let $G$ be a graph. The Steiner distance of $W\subseteq V(G)$ is the minimum size of a connected subgraph of $G$ containing $W$. Such a subgraph is necessarily a tree called a Steiner $W$-tree. The set $A\subseteq V(G)$ is a $k$-Steiner general position set if $V(T_B)\cap A = B$ holds for every set $B\subseteq A$ of cardinality $k$, and for every Steiner $B$-tree $T_B$. The $k$-Steiner general position number $\sgp_k(G)$ of $G$ is the cardinality of a largest $k$-Steiner general position set in $G$. Steiner cliques are introduced and used to bound $\sgp_k(G)$ from below. The $k$-Steiner general position number is determined for trees, cycles and joins of graphs. Lower bounds are presented for split graphs, infinite grids and lexicographic products. The lower bound for the latter product leads to an exact formula for the general position number of an arbitrary lexicographic product.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

On vertices contained in all or in no metric basis

  • Hakanen, Anni
  • Junnila, Ville
  • Laihonen, Tero
  • González Yero, Ismael
A set R⊆V(G) is a resolving set of a graph G if for all distinct vertices v,u∈V(G) there exists an element r∈R such that d(r,v)≠d(r,u). The metric dimension dim(G) of the graph G is the cardinality of a smallest resolving set of G. A resolving set with cardinality dim(G) is called a metric basis of G. We consider vertices that are in all metric bases, and we call them basis forced vertices. We give several structural properties of sparse and dense graphs where basis forced vertices are present. In particular, we give bounds for the maximum number of edges in a graph containing basis forced vertices. Our bound is optimal whenever the number of basis forced vertices is even. Moreover, we provide a method of constructing fairly sparse graphs with basis forced vertices. We also study vertices which are in no metric basis in connection to cut-vertices and pendants. Furthermore, we show that deciding whether a vertex is in all metric bases is co-NP-hard, and deciding whether a vertex is in no metric basis is NP-hard., 17 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación Artículo científico (JournalArticle)

On the (k,l)-anonymity of networks via their k-metric antidimension

  • Fernández Areizaga, Elena
  • Kuziak, Dorota
  • Muñoz Márquez, Manuel
  • González Yero, Ismael
This work focuses on the (k,l)-anonymity of some networks as a measure of their privacy against active attacks. Two different types of networks are considered. The first one consists of graphs with a predetermined structure, namely cylinders, toruses, and 2-dimensional Hamming graphs, whereas the second one is formed by randomly generated graphs. In order to evaluate the (k,l)-anonymity of the considered graphs, we have computed their k-metric antidimension. To this end, we have taken a combinatorial approach for the graphs with a predetermined structure, whereas for randomly generated graphs we have developed an integer programming formulation and computationally tested its implementation. The results of the combinatorial approach, as well as those from the implementations indicate that, according to the (k,l)-anonymity measure, only the 2-dimensional Hamming graphs and some general random dense graphs are achieving some higher privacy properties., MINECO Universidad de Cádiz, Número de páginas: 18