The general position problem and strong resolving graphs
The general position number gp(G) of a connected graph G is the cardinality of a largest set S of vertices such that no three pairwise distinct vertices from S lie on a common geodesic. It is proved that gp(G) ≥ ω(GSR), where GSR is the strong resolving graph of G, and ω(GSR) is its clique number. T...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2019-10-01
|
| Series: | Open Mathematics |
| Subjects: | |
| Online Access: | http://www.degruyter.com/view/j/math.2019.17.issue-1/math-2019-0088/math-2019-0088.xml?format=INT |
| _version_ | 1818020243192152064 |
|---|---|
| author | Klavžar Sandi Yero Ismael G. |
| author_facet | Klavžar Sandi Yero Ismael G. |
| author_sort | Klavžar Sandi |
| collection | DOAJ |
| description | The general position number gp(G) of a connected graph G is the cardinality of a largest set S of vertices such that no three pairwise distinct vertices from S lie on a common geodesic. It is proved that gp(G) ≥ ω(GSR), where GSR is the strong resolving graph of G, and ω(GSR) is its clique number. That the bound is sharp is demonstrated with numerous constructions including for instance direct products of complete graphs and different families of strong products, of generalized lexicographic products, and of rooted product graphs. For the strong product it is proved that gp(G ⊠ H) ≥ gp(G)gp(H), and asked whether the equality holds for arbitrary connected graphs G and H. It is proved that the answer is in particular positive for strong products with a complete factor, for strong products of complete bipartite graphs, and for certain strong cylinders. |
| first_indexed | 2024-04-14T08:02:10Z |
| format | Article |
| id | doaj.art-85e6f7f89a0a40d9a1a246958cc51969 |
| institution | Directory Open Access Journal |
| issn | 2391-5455 |
| language | English |
| last_indexed | 2024-04-14T08:02:10Z |
| publishDate | 2019-10-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Open Mathematics |
| spelling | doaj.art-85e6f7f89a0a40d9a1a246958cc519692022-12-22T02:04:51ZengDe GruyterOpen Mathematics2391-54552019-10-011711126113510.1515/math-2019-0088math-2019-0088The general position problem and strong resolving graphsKlavžar Sandi0Yero Ismael G.1Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, SloveniaDepartamento de Matemáticas, Universidad de Cádiz, Algeciras, SpainThe general position number gp(G) of a connected graph G is the cardinality of a largest set S of vertices such that no three pairwise distinct vertices from S lie on a common geodesic. It is proved that gp(G) ≥ ω(GSR), where GSR is the strong resolving graph of G, and ω(GSR) is its clique number. That the bound is sharp is demonstrated with numerous constructions including for instance direct products of complete graphs and different families of strong products, of generalized lexicographic products, and of rooted product graphs. For the strong product it is proved that gp(G ⊠ H) ≥ gp(G)gp(H), and asked whether the equality holds for arbitrary connected graphs G and H. It is proved that the answer is in particular positive for strong products with a complete factor, for strong products of complete bipartite graphs, and for certain strong cylinders.http://www.degruyter.com/view/j/math.2019.17.issue-1/math-2019-0088/math-2019-0088.xml?format=INTgeneral position problemstrong resolving graphgraph products05c1205c76 |
| spellingShingle | Klavžar Sandi Yero Ismael G. The general position problem and strong resolving graphs Open Mathematics general position problem strong resolving graph graph products 05c12 05c76 |
| title | The general position problem and strong resolving graphs |
| title_full | The general position problem and strong resolving graphs |
| title_fullStr | The general position problem and strong resolving graphs |
| title_full_unstemmed | The general position problem and strong resolving graphs |
| title_short | The general position problem and strong resolving graphs |
| title_sort | general position problem and strong resolving graphs |
| topic | general position problem strong resolving graph graph products 05c12 05c76 |
| url | http://www.degruyter.com/view/j/math.2019.17.issue-1/math-2019-0088/math-2019-0088.xml?format=INT |
| work_keys_str_mv | AT klavzarsandi thegeneralpositionproblemandstrongresolvinggraphs AT yeroismaelg thegeneralpositionproblemandstrongresolvinggraphs AT klavzarsandi generalpositionproblemandstrongresolvinggraphs AT yeroismaelg generalpositionproblemandstrongresolvinggraphs |