Strong Geodetic Problem in Networks
In order to model certain social network problems, the strong geodetic problem and its related invariant, the strong geodetic number, are introduced. The problem is conceptually similar to the classical geodetic problem but seems intrinsically more difficult. The strong geodetic number is compared w...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2020-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2139 |
| _version_ | 1797718037998075904 |
|---|---|
| author | Manuel Paul Klavžar Sandi Xavier Antony Arokiaraj Andrew Thomas Elizabeth |
| author_facet | Manuel Paul Klavžar Sandi Xavier Antony Arokiaraj Andrew Thomas Elizabeth |
| author_sort | Manuel Paul |
| collection | DOAJ |
| description | In order to model certain social network problems, the strong geodetic problem and its related invariant, the strong geodetic number, are introduced. The problem is conceptually similar to the classical geodetic problem but seems intrinsically more difficult. The strong geodetic number is compared with the geodetic number and with the isometric path number. It is determined for several families of graphs including Apollonian networks. Applying Sierpiński graphs, an algorithm is developed that returns a minimum path cover of Apollonian networks corresponding to the strong geodetic number. It is also proved that the strong geodetic problem is NP-complete. |
| first_indexed | 2024-03-12T08:45:10Z |
| format | Article |
| id | doaj.art-bda61bb38c1e42a58ded0d198a3b84ca |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:45:10Z |
| publishDate | 2020-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-bda61bb38c1e42a58ded0d198a3b84ca2023-09-02T16:29:33ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922020-02-0140130732110.7151/dmgt.2139dmgt.2139Strong Geodetic Problem in NetworksManuel Paul0Klavžar Sandi1Xavier Antony2Arokiaraj Andrew3Thomas Elizabeth4Department of Information Science, College of Computing Science and Engineering, Kuwait University, KuwaitFaculty of Mathematics and Physics, University of Ljubljana, SloveniaDepartment of Mathematics, Loyola College, Chennai, IndiaDepartment of Mathematics, Loyola College, Chennai, IndiaDepartment of Mathematics, Loyola College, Chennai, IndiaIn order to model certain social network problems, the strong geodetic problem and its related invariant, the strong geodetic number, are introduced. The problem is conceptually similar to the classical geodetic problem but seems intrinsically more difficult. The strong geodetic number is compared with the geodetic number and with the isometric path number. It is determined for several families of graphs including Apollonian networks. Applying Sierpiński graphs, an algorithm is developed that returns a minimum path cover of Apollonian networks corresponding to the strong geodetic number. It is also proved that the strong geodetic problem is NP-complete.https://doi.org/10.7151/dmgt.2139geodetic problemstrong geodetic problemapollonian networkssierpiński graphscomputational complexity05c1205c7068q17 |
| spellingShingle | Manuel Paul Klavžar Sandi Xavier Antony Arokiaraj Andrew Thomas Elizabeth Strong Geodetic Problem in Networks Discussiones Mathematicae Graph Theory geodetic problem strong geodetic problem apollonian networks sierpiński graphs computational complexity 05c12 05c70 68q17 |
| title | Strong Geodetic Problem in Networks |
| title_full | Strong Geodetic Problem in Networks |
| title_fullStr | Strong Geodetic Problem in Networks |
| title_full_unstemmed | Strong Geodetic Problem in Networks |
| title_short | Strong Geodetic Problem in Networks |
| title_sort | strong geodetic problem in networks |
| topic | geodetic problem strong geodetic problem apollonian networks sierpiński graphs computational complexity 05c12 05c70 68q17 |
| url | https://doi.org/10.7151/dmgt.2139 |
| work_keys_str_mv | AT manuelpaul stronggeodeticprobleminnetworks AT klavzarsandi stronggeodeticprobleminnetworks AT xavierantony stronggeodeticprobleminnetworks AT arokiarajandrew stronggeodeticprobleminnetworks AT thomaselizabeth stronggeodeticprobleminnetworks |