Resolving Sets and Metric Dimension of Graphs | Graph Theory

Описание: Support the production of this course by joining Wrath of Math to access all my graph theory videos!
   / @wrathofmath  
🛍 Check out the coolest math clothes in the world: https://mathshion.com/

Graph Theory course:    • Graph Theory  
Graph Theory exercises:    • Graph Theory Exercises  

Get the textbook! https://amzn.to/3HvI535
Business Inquiries: [email protected]

What are resolving sets and the metric dimension of a graph? We'll be going over that with examples and definitions in today's video graph theory lesson! Resolving sets are also sometimes called locating sets.

SOLUTION TO PRACTICE PROBLEM:

What is the metric dimension of a path graph? The answer is that dim(P) = 1 for every path graph P (this excludes the "path" of 0 vertices). This is because every two vertices in a path graph have distinct distances from a single end-vertex of the path graph. So if we let v be an end-vertex of a path graph, then {v} will always be a minimum resolving set of the path graph because no two vertices in the path have equal distances from v and so every pair of vertices in the path is resolved by v.

Here are some papers for further study...

Resolving Sets and Resolving Several Objects in the Finite King Grid: https://www.utupub.fi/bitstream/handl...
Resolvability in graphs and the metric dimension of a graph: https://core.ac.uk/download/pdf/82498...
The resolving number of a graph: https://arxiv.org/pdf/1309.0252.pdf

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu