![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Last year, my students in the seminar studied graph theory. In the second semester we did a research project on total difference labeling of a graph. They had some really good ideas and a preprint for it is now available here .
Recall that by a graph, we mean a collection of points, called vertices or nodes, where pairs of nodes can be connected by edges. This is useful for representing data. For example, one can imagine four people, Alice, Bob, Carol and Diego. Maybe Alice is friends with Carol, and Bob, and Bob is friends with Diego, and no one else is a friend with anyone else. Then we can represent this data with a graph of four nodes, labeled Alice, Bob, Carol and Diego, with edges between the pairs (Alice, Bob), (Alice, Carol) and (Bob, Diego). One can imagine other contexts where this would be important. For example, one very relevant one right now is to think of graphs which model possibility for disease transmission.
One classic problem in graph theory is the problem of graph coloring. Given each node in a graph, we want to label it with a given color, and we want that no two adjacent nodes (that is nodes connected by an edge) have the same color. We are interested in how few colors we can do this with. For example, you can check that you can color the above graph with Alice, Bob, Carol and Diego with just two colors. A practical variant of this problem shows up in scheduling. Suppose for example, that you have a whole bunch of classes with students in them, and you want to schedule each class so no student has to be in two classes as the same time. Then you can make a graph where each node is a class, and two classes share an edge if at least one student is in both classes. Then, the minimum number of colors needed is the minimum number of distinct time slots you need for all the classes.
A total labeling of a graph is a little different. In a total labeling of a graph, we label each node with a color, but we also label each edge. And we insist that no two nodes which share an edge may be the same color, but we also insist that no two edges which share a node may be the same color. Finally, we require that no edge is the same color of either of its two nodes. (Exercise: What is the minimum number of colors needed to put a total labeling on the graph of Alice, Bob, Carol and Diego above?) Now, so far we've done this with colors. But there's no need to do this with actual colors. We can label our nodes, or our edges instead with numbers, where each number represent a specific color. We'll write say 1 for blue, 2 for red, and so on. Now, one thing we can do with this is we can now restrict our total labelings in terms of properties the numbers must have. We define a total difference labeling then as a total labeling satisfying that the number on any edge must be the absolute value of the difference of the numbers on its two nodes. For example, if we had nodes labeled 3 and 5, and they had an edge connecting them, that edge must then be labeled 2. We can then ask the same sort of question as before: Given a graph G, what is the minimum k such that we can put a total difference labeling on G using just 1, 2, 3... k. We'll call this the total difference labeling number of the graph. (Exercise: What is this number for our Alice, Bob, Carol, Diego graph?)
The idea of a total difference labeling was earlier introduced by a paper by Ranjan Rohatgi and Yufei Zhang where they calculated this for a whole host of graph families. The work with my students extends their work in two major ways. First, Rohatgi and Zhang gave an upper estimate on the total difference labeling number of a complete graph on n nodes. (A complete graph is a graph where every node is connected to every other node.) Their estimate grows exponentially in n, and we were able to reduce this to only polynomial growth. Second, we extended their results to some nice infinite graphs, such as calculating the total difference labeling number of an infinite square lattice. The paper does not assume much background, and should be probably somewhat readable to non-experts.
Recall that by a graph, we mean a collection of points, called vertices or nodes, where pairs of nodes can be connected by edges. This is useful for representing data. For example, one can imagine four people, Alice, Bob, Carol and Diego. Maybe Alice is friends with Carol, and Bob, and Bob is friends with Diego, and no one else is a friend with anyone else. Then we can represent this data with a graph of four nodes, labeled Alice, Bob, Carol and Diego, with edges between the pairs (Alice, Bob), (Alice, Carol) and (Bob, Diego). One can imagine other contexts where this would be important. For example, one very relevant one right now is to think of graphs which model possibility for disease transmission.
One classic problem in graph theory is the problem of graph coloring. Given each node in a graph, we want to label it with a given color, and we want that no two adjacent nodes (that is nodes connected by an edge) have the same color. We are interested in how few colors we can do this with. For example, you can check that you can color the above graph with Alice, Bob, Carol and Diego with just two colors. A practical variant of this problem shows up in scheduling. Suppose for example, that you have a whole bunch of classes with students in them, and you want to schedule each class so no student has to be in two classes as the same time. Then you can make a graph where each node is a class, and two classes share an edge if at least one student is in both classes. Then, the minimum number of colors needed is the minimum number of distinct time slots you need for all the classes.
A total labeling of a graph is a little different. In a total labeling of a graph, we label each node with a color, but we also label each edge. And we insist that no two nodes which share an edge may be the same color, but we also insist that no two edges which share a node may be the same color. Finally, we require that no edge is the same color of either of its two nodes. (Exercise: What is the minimum number of colors needed to put a total labeling on the graph of Alice, Bob, Carol and Diego above?) Now, so far we've done this with colors. But there's no need to do this with actual colors. We can label our nodes, or our edges instead with numbers, where each number represent a specific color. We'll write say 1 for blue, 2 for red, and so on. Now, one thing we can do with this is we can now restrict our total labelings in terms of properties the numbers must have. We define a total difference labeling then as a total labeling satisfying that the number on any edge must be the absolute value of the difference of the numbers on its two nodes. For example, if we had nodes labeled 3 and 5, and they had an edge connecting them, that edge must then be labeled 2. We can then ask the same sort of question as before: Given a graph G, what is the minimum k such that we can put a total difference labeling on G using just 1, 2, 3... k. We'll call this the total difference labeling number of the graph. (Exercise: What is this number for our Alice, Bob, Carol, Diego graph?)
The idea of a total difference labeling was earlier introduced by a paper by Ranjan Rohatgi and Yufei Zhang where they calculated this for a whole host of graph families. The work with my students extends their work in two major ways. First, Rohatgi and Zhang gave an upper estimate on the total difference labeling number of a complete graph on n nodes. (A complete graph is a graph where every node is connected to every other node.) Their estimate grows exponentially in n, and we were able to reduce this to only polynomial growth. Second, we extended their results to some nice infinite graphs, such as calculating the total difference labeling number of an infinite square lattice. The paper does not assume much background, and should be probably somewhat readable to non-experts.
