Edge metric dimensions via hierarchical product and integer linear programming

DOI10.1007/S11590-020-01669-XMaRDI QIDQ2047193zbMATH OpenOpenAlexFDO

Authors Sandi Klavžar, M. Tavakoli

Publication date 19 August 2021

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.04045

zbMATH Keywords

integer linear programmingmetric dimensionhierarchical productmolecular graphedge metric dimension

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Abstract: If $S=v_1,ldots,v_k$ is an ordered subset of vertices of a connected graph $G$ and $e$ is an edge of $G$, then the vector $r_G(e|S)=(d_G(v_1,e),ldots,d_G(v_k,e))$ is the edge metric $S$-representation of $e$. If the vertices of $G$ have pairwise different edge metric $S$-representations, then $S$ is an edge metric generator for $G$. The cardinality of a smallest edge metric generator is the edge metric dimension $medim(G)$ of $G$. A general sharp upper bound on the edge metric dimension of hierarchical products $G(U)sqcapH$ is proved. Exact formula is derived for the case when $|U|=1$. An integer linear programming model for computing the edge metric dimension is proposed. Several examples are provided which demonstrate how these two methods can be applied to obtain the edge metric dimensions of some applicable graphs.

Recommendations

• Some binary products and integer linear programming for \(k\)-metric dimension of graphs
• Uniquely identifying the edges of a graph: the edge metric dimension
• Edge metric dimension of some graph operations
• On the edge metric dimension of graphs
• On the edge dimension of a graph

Cites work

• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 7389745 (Why is no real title available?)
• A new graph product and its spectrum
• Base size, metric dimension and other invariants of groups and graphs
• Counting clar structures of \((4,6)\)-fullerenes
• Distribution of some graph invariants over hierarchical product of graphs
• Edge metric dimension of some generalized Petersen graphs
• Edge metric dimension of some graph operations
• Further new results on strong resolving partitions for graphs
• Landmarks in graphs
• Local metric dimension of graphs: generalized hierarchical products and some applications
• Mathematical aspects of fullerenes
• Metric dimension and pattern avoidance in graphs
• Mixed metric dimension of graphs
• On graphs with the maximum edge metric dimension
• On metric dimensions of symmetric graphs obtained by rooted product
• On the Metric Dimension of Cartesian Products of Graphs
• On the edge dimension of a graph
• On the edge metric dimension of convex polytopes and its related graphs
• On the metric dimension and fractional metric dimension of the hierarchical product of graphs
• On the metric dimension of corona product graphs
• On the metric dimension of corona product of graphs
• On the metric dimension of directed and undirected circulant graphs
• On the metric dimension of the folded \(n\)-cube
• On the strong partition dimension of graphs
• Partition dimension of rooted product graphs
• Prime factorization and domination in the hierarchical product of graphs
• Resolvability in graphs and the metric dimension of a graph
• Some variants of the Szeged index under rooted product of graphs
• Strong metric dimension of rooted product graphs
• Structure-activity maps for visualizing the graph variables arising in drug design
• The generalized hierarchical product of graphs
• The local metric dimension of a graph
• The similarity of metric dimension and local metric dimension of rooted product graph
• The strong metric dimension of graphs and digraphs
• Uniquely identifying the edges of a graph: the edge metric dimension
• \(k\)-metric antidimension: a privacy measure for social graphs

Cited in

(8)

• The doubly metric dimension of cylinder graphs and torus graphs
• The doubly metric dimensions of cactus graphs and block graphs
• Local edge metric dimensions via corona products and integer linear programming
• On metric dimensions of hypercubes
• Global forcing number for maximal matchings in corona products
• Mixed metric dimension of some graphs
• On a conjecture about the local metric dimension of graphs
• On approximation algorithm for the edge metric dimension problem

This page was built for publication: Edge metric dimensions via hierarchical product and integer linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2047193)