Embedding of the join of P3 and C4

  • Context: Graduate 
  • Thread starter Thread starter Solarmew
  • Start date Start date
Click For Summary
SUMMARY

The discussion focuses on the embedding of the join of graphs P3 and C4, specifically proving that the genus of the join is 1, allowing it to be embedded on a torus. The user initially struggles with rearranging the vertices to minimize edge crossings, aiming for at most two edges to cross at any point. The graphs in question are defined as P3 (4-6-1) and C4 (3-7-2-5), although the specific vertex arrangements are deemed less relevant to the overall proof. Ultimately, the user resolves their issue independently.

PREREQUISITES
  • Understanding of graph theory concepts, particularly genus and embeddings.
  • Familiarity with the properties of graph joins, specifically P3 and C4.
  • Knowledge of edge crossing minimization techniques in graph drawings.
  • Basic comprehension of topological surfaces, particularly tori.
NEXT STEPS
  • Research the properties of graph genus and its implications for embeddings.
  • Study techniques for minimizing edge crossings in graph visualizations.
  • Explore the characteristics of toroidal embeddings in graph theory.
  • Investigate the join operation in graph theory and its effects on genus.
USEFUL FOR

Graph theorists, mathematicians specializing in topology, and students studying advanced graph theory concepts will benefit from this discussion.

Solarmew
Messages
37
Reaction score
1
Given a join of P3 and C4, "Adjust the picture if necessary so that at most two edges cross in any point (not representing a vertex). Then erect an overpass at every point where two edges of G cross. The genus of G, is the minimum number of overpasses that must be added to the plane so that G can be embedded in the resulting surface."
The objective is to prove that the graph of the join has genus=1, so it can be embedded on a torus. But I can't figure out how to rearrange the vertices in such a way :( I'm assuming there supposed to be only one point of intersection, but the best I can do is three...
Here P3 is 4-6-1, and C4 is 3-7-2-5, but I don't think that's even relevant.
Any help is appreciated.

attachment.php?attachmentid=54139&stc=1&d=1356066965.png
 

Attachments

  • image.png
    image.png
    11.5 KB · Views: 578
Physics news on Phys.org
nm, i got it...
 

Similar threads

How Do You Calculate Car Speed When Dodging a Water Balloon?
  • · Replies 9 ·
Replies
9
Views
4K
Lagrange multipliers understanding
  • · Replies 8 ·
Replies
8
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 Real life engineering problem I or guidance
  • · Replies 3 ·
Replies
3
Views
3K
MHB Another tree-related graph theory proof
  • · Replies 1 ·
Replies
1
Views
2K
MHB Sentences about the Template algorithm
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Main Theorem of Renormalization, but in physicist-speak
  • · Replies 10 ·
Replies
10
Views
2K
Strong Induction, Tangled Graph
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Gamma - A Minkowski Spacetime Diagram Generator
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Did I figure-out z-translation of 2D-coordinates correctly?
  • · Replies 4 ·
Replies
4
Views
3K