Determine the diameter of the graph

In summary, we can calculate the diameter of a graph by counting the number of edges in the graph and finding the maximum distance between two vertices.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

We have the matrix $$A=\begin{pmatrix}0&1&0&0&0&0&0&1\\1&0&1&0&0&0&0&0\\0&1&0&1&0&0&0&0\\0&0&1&0&1&0&0&0\\0&0&0&1&0&1&0&0\\0&0&0&0&1&0&1&0\\0&0&0&0&0&1&0&1\\1&0&0&0&0&0&1&0\end{pmatrix}$$
and we want to determine the diameter of the graph.

For that do we have to calculate the eigenvalues? Or isn't the diameter related to the number of eigenvalues? (Wondering)
 
Physics news on Phys.org
  • #2
mathmari said:
Hey! :eek:

We have the matrix $$A=\begin{pmatrix}0&1&0&0&0&0&0&1\\1&0&1&0&0&0&0&0\\0&1&0&1&0&0&0&0\\0&0&1&0&1&0&0&0\\0&0&0&1&0&1&0&0\\0&0&0&0&1&0&1&0\\0&0&0&0&0&1&0&1\\1&0&0&0&0&0&1&0\end{pmatrix}$$
and we want to determine the diameter of the graph.

For that do we have to calculate the eigenvalues? Or isn't the diameter related to the number of eigenvalues?

Hey mathmari!

I'm not aware (yet) of a relationship between eigenvalues and diameter.
But to find the diameter, we can draw the graph, and figure out its diameter from the graph can't we? (Wondering)
 
  • #3
I like Serena said:
I'm not aware (yet) of a relationship between eigenvalues and diameter.
But to find the diameter, we can draw the graph, and figure out its diameter from the graph can't we? (Wondering)

Do we have the following graph?

View attachment 8334

(Wondering)
 

Attachments

  • graph_matrix.png
    graph_matrix.png
    6 KB · Views: 67
  • #4
mathmari said:
Do we have the following graph?

Yep. (Nod)
 
  • #5
I like Serena said:
Yep. (Nod)

Graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another, right? Is the largest number of vertices equal to 8? (Wondering)
 
  • #6
mathmari said:
Graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another, right?

Not vertices but edges.
It's the largest possible 'distance' between 2 vertices. (Nerd)

mathmari said:
Is the largest number of vertices equal to 8?

I don't think so.
We have 8 vertices in total that are effectively arranged in a circle.
If we pick 2 of them, what is the distance (the minimum number of edges) between them? (Wondering)
 
  • #7
I like Serena said:
We have 8 vertices in total that are effectively arranged in a circle.
If we pick 2 of them, what is the distance (the minimum number of edges) between them? (Wondering)

The minimum numbers of edges between two vertices is 2, right? Is this the diameter? (Wondering)
 
  • #8
mathmari said:
The minimum numbers of edges between two vertices is 2, right? Is this the diameter?

Nope.
The distance between 2 vertices is the minimum number of edges between those vertices.
And the diameter is the maximum distance that we can find.

If we pick 2 neighboring edges (one edge between them), the distance is 1.
But we can also pick vertices that are further apart can't we? (Thinking)
 
  • #9
I like Serena said:
Nope.
The distance between 2 vertices is the minimum number of edges between those vertices.
And the diameter is the maximum distance that we can find.

If we pick 2 neighboring edges (one edge between them), the distance is 1.
But we can also pick vertices that are further apart can't we? (Thinking)

The maximum distance between two vertices is 4, or not? (Wondering)
 
  • #10
mathmari said:
The maximum distance between two vertices is 4, or not?

Yes it is. (Nod)
 
  • #11
I like Serena said:
Yes it is. (Nod)

Ok! Thank you! (Smile)
 

FAQ: Determine the diameter of the graph

What is the meaning of determining the diameter of a graph?

The diameter of a graph is the longest distance between any two vertices in the graph. It is a measure of the graph's size and can help determine its complexity.

How is the diameter of a graph calculated?

The diameter of a graph can be calculated by finding the shortest path between all pairs of vertices and then selecting the longest path out of those. This can be done using algorithms such as Dijkstra's or Floyd-Warshall.

What is the significance of determining the diameter of a graph?

Determining the diameter of a graph can provide valuable information about the structure and connectivity of the graph. It can also help in solving problems related to network design, routing, and optimization.

Does the diameter of a graph change if edges are added or removed?

Yes, the diameter of a graph can change if edges are added or removed. Adding edges can decrease the diameter by providing shorter paths between vertices, while removing edges can increase the diameter by breaking previously existing paths.

Can the diameter of a graph be greater than the number of vertices in the graph?

No, the diameter of a graph cannot be greater than the number of vertices in the graph. This is because at most, the longest path between two vertices can include all the vertices in the graph, making the diameter equal to the number of vertices.

Similar threads

Replies
1
Views
1K
Replies
1
Views
368
Replies
4
Views
1K
Replies
2
Views
1K
Replies
17
Views
1K
Replies
1
Views
969
Replies
17
Views
2K
Replies
15
Views
2K
Back
Top