Completeness-resolvable graphs

DOI10.1007/S00373-021-02447-XzbMATH Open1484.05058arXiv2101.02838OpenAlexW4210771375MaRDI QIDQ2115145FDOQ2115145

Xuanlong Ma, Min Feng, Huiling Xu

Publication date: 15 March 2022

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

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.

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

zbMATH Keywords

distancebipartite graphsedge coveringsresolving setscompleteness-resolvable graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12) 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)

Cites Work

• Resolvability in graphs and the metric dimension of a graph
• Base size, metric dimension and other invariants of groups and graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Landmarks in graphs
• On Metric Generators of Graphs
• Mastermind
• On the metric dimension of Cartesian powers of a graph

Cited In (7)

• Completeness and related properties of the graph topology on function spaces
• Computational graph completion
• On resolvable tree-decompositions of complete graphs
• Conditional resolvability in graphs: a survey
• Title not available (Why is that?)
• Graph cores via universal completability
• Uniform resource networks. I: Complete graphs

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)