Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory and Bipartite graphs

  1. Mar 14, 2010 #1
    I have a problem involving graph theory. This is not a graph theory course though so I do not know much about it.

    If we have complete bipartite graphs consider whethere or not they are graceful.

    A graph is graceful provided the vertices of the graph can be assigned v distinct integers from 0 to e in such a way that each integer from 1 to e arises as the absolute value of the difference of the numbers assigned to adjacent vertices.

    I think I have read somewhere that a bipartite graph has an odd graceful labeling. I am not sure what this means or if this is even correct.
    But i need a make some kind of conjecture about complete bipartite graphs and whether or not they are graceful.

    Also another question would be given a graceful, bipartite graph it is sometimes possible to modify the grapg so as to produce a graceful, nonbipartite graph with the same number of edges and one fewer vertices, when and how?

    Does anoyone have ideas about this questions?
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted