Graph Theory and Bipartite graphs

[greg.spellman]

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?

 

[lippyka]

My conjecture is that complete bipartite graphs are graceful. This is because all vertices in a bipartite graph have an even degree, and according to the definition of a graceful graph, each absolute difference between adjacent vertices must be an integer between 1 and e (where e is the number of edges). Since the degree of each vertex in a complete bipartite graph is even, it is possible to assign labels to the vertices such that each absolute difference between adjacent vertices is an integer from 1 to e, thus fulfilling the criteria for a graceful graph. Regarding the second question, it is not always possible to modify a graceful, bipartite graph so as to produce a graceful, non-bipartite graph with the same number of edges and one fewer vertices. This is because certain combinations of labels may not be possible when attempting to reduce the number of vertices. For example, if there is a vertex with label 3 adjacent to a vertex with label 5, it may not be possible to reduce the number of vertices while still fulfilling the criteria for a graceful graph, as the absolute difference between the adjacent vertices must still be 2.