General Information

Amanda Olsen
CoRE 734
LaGrange College
Faculty Advisor:
Dr. E. Boros, RUTCOR
Graph Realizations

Project Description

For a graph, G, to be realizable, there must exist some hypergraph, H, that is a subset of some set X, where X is a set of elements. Now to label the vertices of G, V(G), we must assign a number of elements from X, where this number is l. Now this labeling is known as H_v for the vertex v or H_w for the vertex w, where v and w belong to V(G). Now given two vertices in V(G), u and w, (u,w) belongs to the edge set of G, E(G), iff p{|H_u \ H_w|,|H_w \ H_u|} is greater than or equal to some k, where p belongs to the set {min, max, avg} and k is some positive integer. Otherwise, (u,v) is not an edge in G. If there exists such a labeling that matches this criteria where p, k, and l are set to a certain value and G can be drawn, then G is realizable.

So, an example would be that if G is the simple graph with V(G) = {u, v, w} and E(G) = {(u,v), (u,w)} and l = 2, k = 2, and p = min, then we could have H_u = {a,b}, H_v = {c,d}, and H_w = {d,e}. Now we can see that min{|H_u \ H_v|,|H_v \ H_u|} is greater than or equal to 2 so (u,v) is an edge and the same is true for min{|H_u \ H_w|,|H_w \ H_u|}, so (u,w) is an edge. However, min{|H_v \ H_w|,|H_w \ H_v|} is not greater than or equal to 2 because it is 1 since they share the element d, implying that (v,w) is not an edge. This satisfies the characteristics of G, so G is realizable under these conditions.

An open question proposed by Dr. Endre Boros, Dr. Vladimir Gurvich, and Dr. Roy Meshulam in their paper "Difference Graphs" is whether it is possible to show that, given any set size l, where we evaluate the min{|H_u \ H_w|,|H_w \ H_u|} and set k = 2, all graphs can be realized. This is the basis for my research. To start our research we are setting l = 2 to determine which graphs are realizable with a small, uniform set size. Later, we will move to larger values for l where the set size need not be uniform and work on a proof for the question proposed.

For more information on my project and graph realizations, see my presentation below.


Weekly Log

Week 1: Became associated with the problems proposed by my mentor.

Week 2: Familiarized myself with graph realizations.

Week 3: Started working on my problem.

Week 4: Started working on an algorithm.


Boros, Endre, Vladimir Gurvich, and Roy Meshulam. "Difference Graphs." Discrete Mathematics. 276 (2004): 59-64.


To be posted at a later date.