Digraph Automorphisms: Counting Edge Colorings

  • Thread starter Thread starter Monte_Carlo
  • Start date Start date
Click For Summary
SUMMARY

The discussion focuses on counting edge colorings for a directed graph (digraph) G with vertices V(G) = {x, y, z, w} and edges E(G) = { (x, y), (x, z), (x, w) }. The user Monte presents four specific coloring scenarios: using only white, using both white and blue, using green, red, and blue, and using red and blue. Monte concludes that the first scenario has one solution, while the second scenario's solution of two differs from the book's answer, indicating a need for clarification on the correct approach to these problems.

PREREQUISITES
  • Understanding of digraphs and their properties
  • Familiarity with edge coloring concepts in graph theory
  • Knowledge of automorphisms in abstract algebra
  • Basic combinatorial techniques for counting distinct configurations
NEXT STEPS
  • Study the principles of digraph automorphisms in detail
  • Learn about edge coloring techniques in graph theory
  • Explore combinatorial counting methods for distinct arrangements
  • Review textbook solutions for edge coloring problems to identify discrepancies
USEFUL FOR

Students and researchers in abstract algebra and graph theory, particularly those interested in combinatorial problems and edge coloring techniques.

Monte_Carlo
Messages
70
Reaction score
0
Hello,

I have the following abstract algebra problem. It has to do with digraph automorphisms.

You're given a digraph G with vertices V(G) = {x, y, z, w} and edges E(G) = { (x, y), (x, z), (x, w) }. How many essentially different ways are there to color the edges of G using the following colors:

1) only white
2) both white and blue, each at least once
3) green, red and blue, each at least once
4) all red, all blue or some red and some blue

For 1), I think the answer is 1
For 2), I think the answer is 2 but it disagrees with the answer in the book.

Please give me some direction and opinion, I don't think just answers will be useful.

Thanks,

Monte
 
Physics news on Phys.org
Since it's the first time I've posted a request for homework assistance, I realize I might have made several mistakes which would explain why nobody has proffered an attempt at solution. For one, I'm not sure if this section of the forum is the right one. I've seen descriptions of other sections, for example one for abstract algebra. However, there is an instruction not to post homework problems there. The problem I'm asking about is not, strictly speaking, a homework problem, but it is one at the end of a textbook chapter.

I'd be happy to hear if there is any other additional information that would be expected from me to elicit an attempt at solution from anybody at this forum.

Thanks,

Monte
 

Similar threads

  • · Replies 40 ·
2
Replies
40
Views
6K
  • · Replies 8 ·
Replies
8
Views
3K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 21 ·
Replies
21
Views
4K
  • · Replies 5 ·
Replies
5
Views
3K
  • · Replies 146 ·
5
Replies
146
Views
12K
  • · Replies 2 ·
Replies
2
Views
3K
  • · Replies 14 ·
Replies
14
Views
5K
  • · Replies 3 ·
Replies
3
Views
2K