This summer, Professor of Mathematics Sally Cockburn and Sean McAvoy ’23 worked on a research project exploring what happens when graph automorphisms that are usually applied to vertices are instead applied to edges.
The project resulted in a paper, “Edge Determining Sets and Determining Index,” which has been submitted to Involve, a mathematics journal that publishes collaborative faculty-student work. In addition, McAvoy recently presented a talk about the research at the Young Mathematicians Conference at Ohio State University.
In discussing her work with McAvoy, Cockburn described graphs as mathematical objects consisting of dots (vertices) joined by lines (edges) that can be random and irregular, or more orderly and symmetric, in the sense that all the nodes are interchangeable. She said that a graph automorphism is a way of altering the vertices (for example, by rotating them all by 90 degrees) without changing the overall structure of the graph.
One way mathematicians determine how symmetric a graph is, Cockburn said, “is to identify what steps would need to be taken in order to shut down all graph automorphisms.
“If one vertex is fixed in its position, can the other vertices be moved around without changing the overall structure? What if two vertices are fixed in position? More generally, how many vertices must be fixed before all vertices would have to stay fixed in their position to maintain the structure of the graph?”
Cockburn and McAvoy extended this idea to edges, asking how many edges must be fixed in order to shut down all automorphisms of a graph?
“What can make this question tricky is that fixing an edge in position doesn’t necessarily fix the vertices at either end; they could switch positions without moving the edge” Cockburn said.
They found that sometimes the number of edges that must be fixed is the same as the number of vertices, but sometimes, it is substantially less. “And, just to make things interesting,” she noted, “in one case, twice as many edges as vertices are required!”