Groups and Graphs: Proving Transitive Action on Vertices

In summary, a group in graph theory is a collection of elements connected by edges, and transitive action on vertices means that there exists a path between any two vertices in the group. This can be proven by providing an example or using mathematical induction, and it has applications in computer science, social networks, and transportation systems. A group can have transitive action on vertices without being a complete graph, as long as there exists a path between any two vertices.
  • #1
Mess10
1
0
Hi.

Need help with following problem:

Let R=(V,E) a regular graph with degree at least 1 and odd number of vertices.
Let C=Aut(R) the transitive action on the set E of R.

Prove C also transitive action on the set V of R.


Anyone got any idea/tips?

Thanks!
 
Physics news on Phys.org
  • #2
Try assuming the contrary: that the action is not transitive on V. Deduce that R is bipartite. Contradiction. Am I missing something?
 

FAQ: Groups and Graphs: Proving Transitive Action on Vertices

What is a group in the context of graph theory?

A group in graph theory refers to a collection of elements that are connected by edges. These elements can be vertices, nodes, or objects, and the edges represent the relationships between them.

What does it mean for a group to have transitive action on vertices?

Transitive action on vertices means that for any two vertices in a group, there exists a path or sequence of edges that connects them. This path can be traversed by following the edges in the correct order, and it allows for the group to have a sense of symmetry and connectivity.

How do you prove transitive action on vertices in a group?

To prove transitive action on vertices in a group, you need to show that for any two vertices A and B, there exists a path or sequence of edges that connects them. This can be done by providing a specific example of such a path, or by using mathematical induction to show that the property holds for all pairs of vertices in the group.

What are some real-life applications of transitive action on vertices in groups?

Transitive action on vertices in groups has many applications in various fields such as computer science, social networks, and transportation systems. For example, in computer science, it can be used to determine the shortest path between two nodes in a network, while in social networks, it can be used to analyze the spread of information or influence between individuals. In transportation systems, it can be used to optimize routes and schedules for efficient travel.

Can a group have transitive action on vertices without being a complete graph?

Yes, a group can have transitive action on vertices without being a complete graph. A complete graph is one in which every pair of vertices is connected by an edge, but transitive action on vertices only requires that there exists a path between any two vertices, not necessarily a direct edge. This means that a group can have transitive action on vertices even if it is not fully connected.

Similar threads

Vladimir I. Arnold ODE'S book, about action group
Replies
4
Views
2K
MHB Number of Orbits: Showing Equality of Group G and G_a
Replies
34
Views
5K
Transitive subgroup of the symmetric group
Replies
1
Views
1K
MHB Prove the statements : Vectors/Matrices
Replies
5
Views
1K
Does Cayley's Theorem imply all groups are countable?
Replies
8
Views
2K
MHB Decomposition formulas for rotational symmetries of a cube
Replies
1
Views
2K
MHB Exponent of Group Hey! :o - Answers to Questions
Replies
16
Views
4K
I The number of intersection graphs of ##n## convex sets in the plane
Replies
2
Views
891
C* algebras, states, finite graphs
Replies
1
Views
2K
MHB Proving $(G,*)$ is a Group: Hints and Tips for a Simple Group Theory Problem
Replies
2
Views
1K

Hot Threads

Recent Insights

Back
Top