REVIEW 7 cited by
The multiset dimension of graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We introduce a variation of metric dimension, called the multiset dimension. The representation multiset of a vertex $v$ with respect to $W$ (which is a subset of the vertex set of a graph $G$), $r_m (v|W)$, is defined as a multiset of distances between $v$ and the vertices in $W$. If $r_m (u |W) \neq r_m(v|W)$ for every pair of distinct vertices $u$ and $v$, then $W$ is called an m-resolving set of $G$. If $G$ has an m-resolving set, then the cardinality of a smallest m-resolving set is called the multiset dimension of $G$, denoted by $md(G)$. If $G$ does not contain an m-resolving set, we write $md(G) = \infty$. In this paper we present basic results on the multiset dimension. We obtain some (sharp) bounds for multiset dimension of arbitrary graphs in term of its metric dimension, order, or diameter. We provide some necessary conditions for a graph to have finite multiset dimension, with an example of an infinite family of graphs where those necessary conditions are also sufficient. We also show that the multiset dimension of any graph other than a path is at least $3$ and finally we provide two families of graphs having the multiset dimension $3$.
Forward citations
Cited by 7 Pith papers
-
The Multiset Dimension of Graphs: Extremal Values and King Grids
Multiset dimension attains the trivial upper bound n(G) for the first time at order 11 (eight graphs), equals 4 on every n×n king grid n ≥ 5, and equals n on every 3×n king strip n ≥ 6.
-
Multiset Metric Dimension of Binomial Random Graphs
For binomial random graphs with average degree n^x, the multiset metric dimension is w.h.p. at most n^{y4} for x≤1/8 and at least n^{y1} for x≤1/2, where y1,y4 are explicit constants, and it is infinite for x>1/2.
-
On the $(k,\ell)$-multiset anonymity measure for social graphs
The paper defines and analyzes k-multiset antiresolving sets, the basis for a multiset variant of (k, ℓ)-anonymity, and provides an ILP to compute the minimum attacker set size.
-
Multiset Partition Dimension of Graphs
The multiset partition dimension of graphs is introduced, with exact values determined for paths, cycles, grids, ladders, and infinite values for complete, wheel, and friendship graphs.
-
Multiset resolvability parameters in graphs: A survey with new results and open problems
Multiset resolvability parameters are surveyed; sharp outer-multiset lower bounds for diameter-two and join graphs are proved, and block graphs with local multiset dimension two are characterized.
-
Local (Outer) Multiset Dimensions of Graphs
Introduces the local outer multiset dimension, but key proofs (notably a wheel lemma and a sharpness construction) are invalid.
-
A Survey on Multiset Dimension and Its Variations
A literature survey consolidates results on multiset dimension and its local/outer/edge variants and proposes new multiset partition and related parameters as open directions.
Discussion (0). Continue with ORCID to comment.