Efficient Location of Resources in Cylindrical Networks
The location of resources in a network satisfying some optimization property is a classical combinatorial problem that can be modeled and solved by using graphs. Key tools in this problem are the domination-type properties, which have been defined and widely studied in different types of graph model...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2018-01-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | http://www.mdpi.com/2073-8994/10/1/24 |
| _version_ | 1797999464776990720 |
|---|---|
| author | José Juan Carreño José Antonio Martínez María Luz Puertas |
| author_facet | José Juan Carreño José Antonio Martínez María Luz Puertas |
| author_sort | José Juan Carreño |
| collection | DOAJ |
| description | The location of resources in a network satisfying some optimization property is a classical combinatorial problem that can be modeled and solved by using graphs. Key tools in this problem are the domination-type properties, which have been defined and widely studied in different types of graph models, such as undirected and directed graphs, finite and infinite graphs, simple graphs and hypergraphs. When the required optimization property is that every node of the network must have access to exactly one node with the desired resource, the appropriate models are the efficient dominating sets. However, the existence of these vertex sets is not guaranteed in every graph, so relaxing some conditions is necessary to ensure the existence of some kind of dominating sets, as efficient as possible, in a larger number of graphs. In this paper, we study independent
[
1
,
2
]
-sets, a generalization of efficient dominating sets defined by Chellali et al., in the case of cylindrical networks. It is known that efficient dominating sets exist in very special cases of cylinders, but the particular symmetry of these graphs will allow us to provide regular patterns that guarantee the existence of independent
[
1
,
2
]
-sets in every cylinder, except in one single case, and to compute exact values of the optimal parameter, the independent
[
1
,
2
]
-number, in cylinders of selected sizes. |
| first_indexed | 2024-04-11T11:05:03Z |
| format | Article |
| id | doaj.art-56e4a633c80043248bfeeaab5746ce22 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-04-11T11:05:03Z |
| publishDate | 2018-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-56e4a633c80043248bfeeaab5746ce222022-12-22T04:28:24ZengMDPI AGSymmetry2073-89942018-01-011012410.3390/sym10010024sym10010024Efficient Location of Resources in Cylindrical NetworksJosé Juan Carreño0José Antonio Martínez1María Luz Puertas2Department of Applied Mathematics for Information and Communication Technologies, Universidad Politécnica de Madrid, Calle Alan Turing s\n, 28031 Madrid, SpainDepartment of Computer Science, Universidad de Almería, Carretera Sacramento s\n, 04120 Almería, SpainDepartment of Mathematics, Universidad de Almería, Carretera Sacramento s\n, 04120 Almería, SpainThe location of resources in a network satisfying some optimization property is a classical combinatorial problem that can be modeled and solved by using graphs. Key tools in this problem are the domination-type properties, which have been defined and widely studied in different types of graph models, such as undirected and directed graphs, finite and infinite graphs, simple graphs and hypergraphs. When the required optimization property is that every node of the network must have access to exactly one node with the desired resource, the appropriate models are the efficient dominating sets. However, the existence of these vertex sets is not guaranteed in every graph, so relaxing some conditions is necessary to ensure the existence of some kind of dominating sets, as efficient as possible, in a larger number of graphs. In this paper, we study independent [ 1 , 2 ] -sets, a generalization of efficient dominating sets defined by Chellali et al., in the case of cylindrical networks. It is known that efficient dominating sets exist in very special cases of cylinders, but the particular symmetry of these graphs will allow us to provide regular patterns that guarantee the existence of independent [ 1 , 2 ] -sets in every cylinder, except in one single case, and to compute exact values of the optimal parameter, the independent [ 1 , 2 ] -number, in cylinders of selected sizes.http://www.mdpi.com/2073-8994/10/1/24cartesian product of graphsefficient dominationtropical matrix algebra |
| spellingShingle | José Juan Carreño José Antonio Martínez María Luz Puertas Efficient Location of Resources in Cylindrical Networks Symmetry cartesian product of graphs efficient domination tropical matrix algebra |
| title | Efficient Location of Resources in Cylindrical Networks |
| title_full | Efficient Location of Resources in Cylindrical Networks |
| title_fullStr | Efficient Location of Resources in Cylindrical Networks |
| title_full_unstemmed | Efficient Location of Resources in Cylindrical Networks |
| title_short | Efficient Location of Resources in Cylindrical Networks |
| title_sort | efficient location of resources in cylindrical networks |
| topic | cartesian product of graphs efficient domination tropical matrix algebra |
| url | http://www.mdpi.com/2073-8994/10/1/24 |
| work_keys_str_mv | AT josejuancarreno efficientlocationofresourcesincylindricalnetworks AT joseantoniomartinez efficientlocationofresourcesincylindricalnetworks AT marialuzpuertas efficientlocationofresourcesincylindricalnetworks |