Graph Theory - Connectivity of r-regular graphs

Thread starter Gh0stZA
Start date Apr 2, 2012
Tags

Graph Graph theory Graphs Theory

In summary, a regular graph is a type of graph where each vertex has the same number of edges connected to it. The connectivity of an r-regular graph is the minimum number of edges that need to be removed in order to disconnect the graph, which can be calculated using the formula k = r - 1. For an r-regular graph with n vertices, the maximum connectivity that can be attained is n/2, but if the graph is also a complete graph, then the connectivity will be equal to n-1. The connectivity of an r-regular graph is directly proportional to its robustness, meaning that a higher connectivity results in a more robust graph.

Apr 2, 2012

Gh0stZA

Hello everyone.

Find the minimum positive integer r for which there exists an r-regular graph G such that λ(G) ≥ κ(G) + 2

All help appreciated.

Physics news on Phys.org

Apr 7, 2012

Gh0stZA

Sorry for the bump, any ideas on this?

Related to Graph Theory - Connectivity of r-regular graphs

1. What is a regular graph?

A regular graph is a type of graph where each vertex has the same number of edges connected to it. This number is known as the degree of the graph and is denoted by 'r'. Therefore, an r-regular graph is a graph where each vertex has exactly 'r' edges connected to it.

2. What is the connectivity of an r-regular graph?

The connectivity of an r-regular graph is the minimum number of edges that need to be removed in order to disconnect the graph. In other words, it is the minimum number of edges that need to be cut in order to separate the graph into two or more disconnected components.

3. How is the connectivity of an r-regular graph calculated?

The connectivity of an r-regular graph can be calculated using the formula k = r - 1, where k is the connectivity and r is the degree of the graph. This means that the connectivity of an r-regular graph is always one less than its degree.

4. What is the relationship between the connectivity and the number of vertices in an r-regular graph?

For an r-regular graph with n vertices, the maximum connectivity that can be attained is n/2. This means that the maximum number of edges that need to be removed to disconnect the graph is n/2. However, if the graph is also a complete graph, then the connectivity will be equal to n-1, which is the maximum number of edges in a complete graph.

5. How does the connectivity of an r-regular graph affect its robustness?

The connectivity of an r-regular graph is directly proportional to its robustness. This means that the higher the connectivity of the graph, the more robust it is. This is because a higher connectivity means that the graph has more edges that need to be removed in order to disconnect it, making it more difficult to break apart.