Graphs with distinguishing sets of size k
The size of a resolving set R of a non-trivial connected graph Γ of order n ≥ 2 is the number of edges in the induced subgraph <R>.The minimum cardinality of a resolving set of size k of graph Γ is called the metric dimension of size k, denoted by β(k)(Γ). We study the existence of resolving s...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-01-01
|
| Series: | Kuwait Journal of Science |
| Subjects: | |
| Online Access: | https://www.sciencedirect.com/science/article/pii/S2307410823002146 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850122964053262336 |
|---|---|
| author | Muhammad Naeem Azhar Muhammad Fazil Imran Javaid Muhammad Murtaza |
| author_facet | Muhammad Naeem Azhar Muhammad Fazil Imran Javaid Muhammad Murtaza |
| author_sort | Muhammad Naeem Azhar |
| collection | DOAJ |
| description | The size of a resolving set R of a non-trivial connected graph Γ of order n ≥ 2 is the number of edges in the induced subgraph <R>.The minimum cardinality of a resolving set of size k of graph Γ is called the metric dimension of size k, denoted by β(k)(Γ). We study the existence of resolving sets of size k in some families of graphs and investigate their properties. We find bounds on the metric dimension of size k of a graph Γ. We give the necessary condition for the metric dimension of size k and size (k + 1) of a graph Γ, to satisfy the inequality β(k+1)(Γ) − β(k)(Γ) ≤ 1. We will disprove a conjecture on bounds of the metric dimension of size k. For every positive integers k, l, and n such that k + 1 ≤ l ≤ n, we give a realizable result of a graph Γ of order n and l = β(k)(Γ). |
| format | Article |
| id | doaj-art-942e3686fa3e445e9cda22bebc031c5a |
| institution | OA Journals |
| issn | 2307-4116 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Kuwait Journal of Science |
| spelling | doaj-art-942e3686fa3e445e9cda22bebc031c5a2025-08-20T02:34:43ZengElsevierKuwait Journal of Science2307-41162024-01-01511100170https://doi.org/10.1016/j.kjs.2023.12.008Graphs with distinguishing sets of size kMuhammad Naeem Azhar0Muhammad Fazil1Imran Javaid2Muhammad Murtaza3Dept. of Mathematics, The Islamia University of Bahawalpur, Bahawalpur, 63100, PakistanDept. of Basic Sciences and Humanities, Bahauddin Zakariya University, Multan, 60800, PakistanCASPAM, Bahauddin Zakariya University, Multan, 60800, PakistanFederal Govt. Sir Syed College, Rawalpindi, PakistanThe size of a resolving set R of a non-trivial connected graph Γ of order n ≥ 2 is the number of edges in the induced subgraph <R>.The minimum cardinality of a resolving set of size k of graph Γ is called the metric dimension of size k, denoted by β(k)(Γ). We study the existence of resolving sets of size k in some families of graphs and investigate their properties. We find bounds on the metric dimension of size k of a graph Γ. We give the necessary condition for the metric dimension of size k and size (k + 1) of a graph Γ, to satisfy the inequality β(k+1)(Γ) − β(k)(Γ) ≤ 1. We will disprove a conjecture on bounds of the metric dimension of size k. For every positive integers k, l, and n such that k + 1 ≤ l ≤ n, we give a realizable result of a graph Γ of order n and l = β(k)(Γ).https://www.sciencedirect.com/science/article/pii/S2307410823002146induced subgraphmetric dimensionmetric dimension of size kresolving setresolving set of size k |
| spellingShingle | Muhammad Naeem Azhar Muhammad Fazil Imran Javaid Muhammad Murtaza Graphs with distinguishing sets of size k Kuwait Journal of Science induced subgraph metric dimension metric dimension of size k resolving set resolving set of size k |
| title | Graphs with distinguishing sets of size k |
| title_full | Graphs with distinguishing sets of size k |
| title_fullStr | Graphs with distinguishing sets of size k |
| title_full_unstemmed | Graphs with distinguishing sets of size k |
| title_short | Graphs with distinguishing sets of size k |
| title_sort | graphs with distinguishing sets of size k |
| topic | induced subgraph metric dimension metric dimension of size k resolving set resolving set of size k |
| url | https://www.sciencedirect.com/science/article/pii/S2307410823002146 |
| work_keys_str_mv | AT muhammadnaeemazhar graphswithdistinguishingsetsofsizek AT muhammadfazil graphswithdistinguishingsetsofsizek AT imranjavaid graphswithdistinguishingsetsofsizek AT muhammadmurtaza graphswithdistinguishingsetsofsizek |