Binary locating-dominating sets in rotationally-symmetric convex polytopes

DOI10.3390/SYM10120727MaRDI QIDQ2337871zbMATH OpenOpenAlexWikidataFDO

Authors Hassan Raza, Sakander Hayat, Xiang-Feng Pan

Publication date 20 November 2019

Published in Symmetry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/sym10120727

zbMATH Keywords

binary locating-domination numberdominating setILP modelsrotationally-symmetric convex polytopes

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Applications of graph theory (05C90)

Review text

Summary: A convex polytope or simply polytope is the convex hull of a finite set of points in Euclidean space \(\mathbb{R}^d\). Graphs of convex polytopes emerge from geometric structures of convex polytopes by preserving the adjacency-incidence relation between vertices. In this paper, we study the problem of binary locating-dominating number for the graphs of convex polytopes which are symmetric rotationally. We provide an integer linear programming (ILP) formulation for the binary locating-dominating problem of graphs. We have determined the exact values of the binary locating-dominating number for two infinite families of convex polytopes. The exact values of the binary locating-dominating number are obtained for two rotationally-symmetric convex polytopes families. Moreover, certain upper bounds are determined for other three infinite families of convex polytopes. By using the ILP formulation, we show tightness in the obtained upper bounds.

Recommendations

• The binary locating-dominating number of some convex polytopes
• Binary linear programming approach to graph convex covering problems
• The open-locating-dominating number of some convex polytopes
• The convex and weak convex domination number of convex polytopes
• A polyhedral approach to locating-dominating sets in graphs

Cites work

• Computation of topological indices of certain networks
• Computing the metric dimension of convex polytopes generated by wheel related graphs
• Domination and location in acyclic graphs
• Extremal cardinalities for identifying and locating-dominating codes in graphs
• Fault-tolerant locating-dominating sets
• Generalized domination and efficient domination in graphs
• scientific article; zbMATH DE number 5717189 (Why is no real title available?)
• scientific article; zbMATH DE number 4081585 (Why is no real title available?)
• scientific article; zbMATH DE number 125446 (Why is no real title available?)
• scientific article; zbMATH DE number 1343532 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 2068110 (Why is no real title available?)
• scientific article; zbMATH DE number 861343 (Why is no real title available?)
• scientific article; zbMATH DE number 6119641 (Why is no real title available?)
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• LD-graphs and global location-domination in bipartite graphs
• Locating and total dominating sets in trees
• Minimal doubly resolving sets and the strong metric dimension of some convex polytopes
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Minimum fault-tolerant, local and strong metric dimension of graphs.
• New variable neighborhood search based 0-1 MIP heuristics
• On classes of regular graphs with constant metric dimension
• On families of convex polytopes with constant metric dimension
• On locating--dominating sets in infinite grids
• On the ensemble of optimal dominating and locating-dominating codes in a graph
• On the fault-tolerant metric dimension of convex polytopes
• On the metric dimension of rotationally-symmetric convex polytopes
• On the metric dimension of two families of convex polytopes
• Open neighborhood locating-dominating in trees
• The binary locating-dominating number of some convex polytopes
• Valency-based topological descriptors of chemical networks and their applications
• Vertex-magic total labeling of generalized Petersen graphs and convex polytopes

Cited in

(6)

• Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications
• Resolvability and fault-tolerant resolvability structures of convex polytopes
• The binary locating-dominating number of some convex polytopes
• The open-locating-dominating number of some convex polytopes
• Total Roman domination on the digraphs
• On the binary locating-domination number of regular and strongly-regular graphs

This page was built for publication: Binary locating-dominating sets in rotationally-symmetric convex polytopes

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