IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i19p3539-d928228.html
   My bibliography  Save this article

Identifying the Exact Value of the Metric Dimension and Edge Dimension of Unicyclic Graphs

Author

Listed:
  • Enqiang Zhu

    (Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China)

  • Shaoxiang Peng

    (Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China)

  • Chanjuan Liu

    (School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China)

Abstract

Given a simple connected graph G , the metric dimension dim ( G ) (and edge metric dimension edim ( G ) ) is defined as the cardinality of a smallest vertex subset S ⊆ V ( G ) for which every two distinct vertices (and edges) in G have distinct distances to a vertex of S . It is an interesting topic to discuss the relation between these two dimensions for some class of graphs. This paper settles two open problems on this topic for unicyclic graphs. We recently learned that Sedlar and Škrekovski settled these problems, but our work presents the results in a completely different way. By introducing four classes of subgraphs, we characterize the structure of a unicyclic graph G such that dim ( G ) and edim ( G ) are equal to the cardinality of any minimum branch-resolving set for unicyclic graphs. This generates an approach to determine the exact value of the metric dimension (and edge metric dimension) for a unicyclic graph.

Suggested Citation

  • Enqiang Zhu & Shaoxiang Peng & Chanjuan Liu, 2022. "Identifying the Exact Value of the Metric Dimension and Edge Dimension of Unicyclic Graphs," Mathematics, MDPI, vol. 10(19), pages 1-14, September.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:19:p:3539-:d:928228
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/19/3539/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/19/3539/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Meiqin Wei & Jun Yue & Lily Chen, 2022. "The effect of vertex and edge deletion on the edge metric dimension of graphs," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 331-342, August.
    2. Martin Knor & Jelena Sedlar & Riste Škrekovski, 2022. "Remarks on the Vertex and the Edge Metric Dimension of 2-Connected Graphs," Mathematics, MDPI, vol. 10(14), pages 1-16, July.
    3. Bo Deng & Muhammad Faisal Nadeem & Muhammad Azeem, 2021. "On the Edge Metric Dimension of Different Families of Möbius Networks," Mathematical Problems in Engineering, Hindawi, vol. 2021, pages 1-9, March.
    4. Yuezhong Zhang & Suogang Gao, 2020. "On the edge metric dimension of convex polytopes and its related graphs," Journal of Combinatorial Optimization, Springer, vol. 39(2), pages 334-350, February.
    5. Sedlar, Jelena & Škrekovski, Riste, 2021. "Bounds on metric dimensions of graphs with edge disjoint cycles," Applied Mathematics and Computation, Elsevier, vol. 396(C).
    6. David G. L. Wang & Monica M. Y. Wang & Shiqiang Zhang, 2022. "Determining the edge metric dimension of the generalized Petersen graph P(n, 3)," Journal of Combinatorial Optimization, Springer, vol. 43(2), pages 460-496, March.
    7. Tanveer Iqbal & Muhammad Rafiq & Muhammad Naeem Azhar & Muhammad Salman & Imran Khalid & Ali Ahmad, 2022. "On the Edge Resolvability of Double Generalized Petersen Graphs," Journal of Mathematics, Hindawi, vol. 2022, pages 1-14, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sedlar, Jelena & Škrekovski, Riste, 2022. "Metric dimensions vs. cyclomatic number of graphs with minimum degree at least two," Applied Mathematics and Computation, Elsevier, vol. 427(C).
    2. Nie, Kairui & Xu, Kexiang, 2023. "Mixed metric dimension of some graphs," Applied Mathematics and Computation, Elsevier, vol. 442(C).
    3. Martin Knor & Jelena Sedlar & Riste Škrekovski, 2022. "Remarks on the Vertex and the Edge Metric Dimension of 2-Connected Graphs," Mathematics, MDPI, vol. 10(14), pages 1-16, July.
    4. Sedlar, Jelena & Škrekovski, Riste, 2021. "Extremal mixed metric dimension with respect to the cyclomatic number," Applied Mathematics and Computation, Elsevier, vol. 404(C).
    5. Asad Khan & Ghulam Haidar & Naeem Abbas & Murad Ul Islam Khan & Azmat Ullah Khan Niazi & Asad Ul Islam Khan, 2023. "Metric Dimensions of Bicyclic Graphs," Mathematics, MDPI, vol. 11(4), pages 1-17, February.
    6. Sedlar, Jelena & Škrekovski, Riste, 2021. "Bounds on metric dimensions of graphs with edge disjoint cycles," Applied Mathematics and Computation, Elsevier, vol. 396(C).
    7. Knor, Martin & Majstorović, Snježana & Masa Toshi, Aoden Teo & Škrekovski, Riste & Yero, Ismael G., 2021. "Graphs with the edge metric dimension smaller than the metric dimension," Applied Mathematics and Computation, Elsevier, vol. 401(C).
    8. Hassan Raza, 2021. "Computing Open Locating-Dominating Number of Some Rotationally-Symmetric Graphs," Mathematics, MDPI, vol. 9(12), pages 1-12, June.
    9. Sakander Hayat & Asad Khan & Yubin Zhong, 2022. "On Resolvability- and Domination-Related Parameters of Complete Multipartite Graphs," Mathematics, MDPI, vol. 10(11), pages 1-16, May.
    10. Ali N. A. Koam & Ali Ahmad & Muhammad Ibrahim & Muhammad Azeem, 2021. "Edge Metric and Fault-Tolerant Edge Metric Dimension of Hollow Coronoid," Mathematics, MDPI, vol. 9(12), pages 1-14, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2022:i:19:p:3539-:d:928228. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.