Extremal mixed metric dimension with respect to the cyclomatic number

Jelena Sedlar and Riste Škrekovski

Applied Mathematics and Computation, 2021, vol. 404, issue C

Abstract: In a graph G, the cardinality of the smallest ordered set of vertices that distinguishes every element of V(G)∪E(G) is called the mixed metric dimension of G, and it is denoted by mdim(G). In [12] it was conjectured that every graph G with cyclomatic number c(G) satisfies mdim(G)≤L1(G)+2c(G) where L1(G) is the number of leaves in G. It is already proven that the equality holds for all trees and more generally for graphs with edge-disjoint cycles in which every cycle has precisely one vertex of degree ≥3. In this paper we determine that for every Θ-graph G, the mixed metric dimension mdim(G) equals 3 or 4, with 4 being attained if and only if G is a balanced Θ-graph. Thus, for balanced Θ-graphs the above inequality is also tight. We conclude the paper by further conjecturing that there are no other graphs, besides the ones mentioned here, for which the equality mdim(G)=L1(G)+2c(G) holds.

Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300321003283
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:404:y:2021:i:c:s0096300321003283

DOI: 10.1016/j.amc.2021.126238

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().