Completeness-resolvable graphs

DOI10.1007/S00373-021-02447-XMaRDI QIDQ2115145zbMATH OpenOpenAlexFDO

Authors Min Feng, Huiling Xu, Xuanlong Ma

Publication date 15 March 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

bipartite graphscompleteness-resolvable graphdistanceedge coveringsresolving sets

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Combinatorics of partially ordered sets (06A07)

Abstract: Given a connected graph $G=(V(G),E(G))$, the length of a shortest path from a vertex $u$ to a vertex $v$ is denoted by $d(u,v)$. For a proper subset $W$ of $V(G)$, let $m(W)$ be the maximum value of $d(u,v)$ as $u$ ranging over $W$ and $v$ ranging over $V(G)setminusW$. The proper subset $W=w_1,ldots,w_{|W|}$ is a {em completeness-resolving set} of $G$ if ${\displaystyle }$ Psi_W: V(G)setminus W longrightarrow [m(W)]^{|W|},qquad ulongmapsto (d(w_1,u),ldots,d(w_{|W|},u)) ${\displaystyle }$ is a bijection, where ${\displaystyle }$ [m(W)]^{|W|}={(a_{(1)},ldots,a_{(|W|)})mid 1leq a_{(i)}leq m(W) ext{ for each }i=1,ldots,|W|}. ${\displaystyle }$ A graph is {em completeness-resolvable} if it admits a completeness-resolving set. In this paper, we first construct the set of all completeness-resolvable graphs by using the edge coverings of some vertices in given bipartite graphs, and then establish posets on some subsets of this set by the spanning subgraph relationship. Based on each poset, we find the maximum graph and give the lower and upper bounds for the number of edges in a minimal graph. Furthermore, minimal graphs satisfying the lower or upper bound are characterized.

Recommendations

• Resolvability and the upper dimension of graphs
• The metric dimensions of a complete \(n\)-partite graph and its Cartesian product with a path
• scientific article; zbMATH DE number 1998282
• scientific article; zbMATH DE number 2197925
• On the connected metric dimension of graphs and their complements

Cites work

• Base size, metric dimension and other invariants of groups and graphs
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• Landmarks in graphs
• Mastermind
• On Metric Generators of Graphs
• On the metric dimension of Cartesian powers of a graph
• On the Metric Dimension of Cartesian Products of Graphs
• Resolvability in graphs and the metric dimension of a graph

Cited in

(7)

• Conditional resolvability in graphs: a survey
• Uniform resource networks. I: Complete graphs
• Computational graph completion
• Graph cores via universal completability
• On resolvable tree-decompositions of complete graphs
• Completeness and related properties of the graph topology on function spaces
• scientific article; zbMATH DE number 6542389 (Why is no real title available?)

This page was built for publication: Completeness-resolvable graphs

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