Diameter of graph-usual chessboard

  • Context: MHB 
  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Diameter
Click For Summary

Discussion Overview

The discussion revolves around determining the diameter of a graph representing a chessboard, where vertices correspond to the 64 squares and edges connect squares that share a side. Participants explore the definition of graph diameter and seek to understand how to calculate it.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant suggests that the diameter of the graph is 64 but expresses uncertainty.
  • Another participant questions this claim and seeks clarification on the definition of diameter, stating it is the largest distance between two vertices.
  • A participant reiterates the definition of diameter and asks how to find it, emphasizing the concept of the longest shortest path.
  • There is a suggestion that if the diameter were 64, a shortest path with 64 edges should be identifiable, prompting further inquiry into the longest shortest path.
  • Another participant argues that moving from one end of the board to the other requires at least 8 steps, indicating that the diameter must be at least 8.
  • This participant also posits that if a path takes 64 steps, a shorter path must exist, suggesting the diameter is less than 64.
  • They challenge others to find two squares that require more than 8 steps to traverse, indicating ongoing exploration of the problem.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the diameter of the graph. There are competing views regarding the minimum and maximum possible values for the diameter, with some suggesting it is at least 8 and others proposing it could be as high as 64.

Contextual Notes

Participants have not resolved the assumptions about the paths on the chessboard or the implications of the graph's structure on the diameter calculation.

evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! ;)

I am given this exercise:
A graph has as vertices the $64$ squares of an usual chessboard and two squares are connected with an edge if and only if they have a common side.Which is the diameter of the graph?

I thought that the diameter is equal to $64$,but I am not sure..Could you tell me if it is right?? (Blush)(Blush)
 
Physics news on Phys.org
evinda said:
Hello! ;)

I am given this exercise:
A graph has as vertices the $64$ squares of an usual chessboard and two squares are connected with an edge if and only if they have a common side.Which is the diameter of the graph?

I thought that the diameter is equal to $64$,but I am not sure..Could you tell me if it is right?? (Blush)(Blush)

Hi! :)

I don't think so... (Worried)
What is the definition of the diameter?
 
I like Serena said:
Hi! :)

I don't think so... (Worried)
What is the definition of the diameter?

Diameter of a graph $G$ is defined to be tha largest distance between two vertices of $G$:
$$diam G= \max_{u,v \in V} d(u,v)$$
$d(u,v)$: distance of $u$ and $v$

How can I find it then?? (Thinking)
 
evinda said:
Diameter of a graph $G$ is defined to be tha largest distance between two vertices of $G$:
$$diam G= \max_{u,v \in V} d(u,v)$$
$d(u,v)$: distance of $u$ and $v$

How can I find it then?? (Thinking)

Good! :)

I like to say that the diameter is the longest shortest path.

Well, if you think it is 64, can you find a (shortest) path between 2 nodes that contains 64 edges?
What is the longest shortest path that you can find? (Wondering)
 
I like Serena said:
Good! :)

I like to say that the diameter is the longest shortest path.

Well, if you think it is 64, can you find a (shortest) path between 2 nodes that contains 64 edges?
What is the longest shortest path that you can find? (Wondering)

I don't really know (Worried) Could you give me a hint?? (Blush)
 
evinda said:
I don't really know (Worried) Could you give me a hint?? (Blush)

Well... we can only go from one square to another if those squares are next to each other.
So if we start from 1 end of the board and step to the other side, we're making 8 steps. We can't do it any faster.
That means that the diameter is at least 8.

If we start from one square and take 64 steps to get to some other square, then I think we can also find a shorter path (the distance of 2 squares is the length of the shortest path).
That means that the diameter is less than 64.

Can you find 2 squares for which it will have to take more than 8 steps to cross from the one to the other? (Wondering)
 

Similar threads

MHB Graph: showing that diameter is greater than average pairwise distance
  • · Replies 4 ·
Replies
4
Views
4K
MHB How many edges does the graph have?
  • · Replies 4 ·
Replies
4
Views
2K
Experimenting whether the diameter of a pot affects boiling time for water
  • · Replies 15 ·
Replies
15
Views
3K
MHB Find total number of republications
  • · Replies 22 ·
Replies
22
Views
2K
MHB Is HSC NP-Complete in Graph Theory?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Optimal Seating Arrangement Algorithm for Friendship Graphs
  • · Replies 2 ·
Replies
2
Views
2K
MHB How many hours are needed for team meetings?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Units of a vector in a velocity vs time graph?
  • · Replies 13 ·
Replies
13
Views
2K
MHB What is the Name for a Graph with Loops That Join a Vertex to Nothing?
  • · Replies 4 ·
Replies
4
Views
3K
Graduate Graph G with n vertices, with connectivity
  • · Replies 4 ·
Replies
4
Views
2K