hello, I have a question about graph theory. I want to change a graph ,such that there are at least k vertices with the same degree in it. it means that there is no vertex with unique degree in the graph. it is possible by deleting, adding or switching the edges in the graph. is there any algorithm or technique in the theory graph that can help me decide which edge should be selected to remove from or add to the graph?
Hi, you'll need to be more specific about what you're hoping to accomplish. Graphs with all vertices having the same degree are called regular. There are several techniques like "edge-swap" or more generally using a notion of alternating cycles but these are designed to maintain the regular condition.
Are you trying to make the graph:
- not regular?
- smaller / larger while preserving regularity?
hi Colton Magnant , thanks to your answer. i want to make a non-regular graph and the vertices of the graph should not change, but just the edges of the graph should change by removing, adding or switching between vertices. i mean, it is no need all the vertices have the same degree, but if we consider the number k=4, all the vertices of the graph should have at least 4-1=3 vertices with the same degree. and there should not be any vertex that the number of the vertices in the graph with the same degree of it be less than k-1(i.e. 4-1=3). I don't know I could clarified the question or not.
I want something like what Yair Caro introduced, but I do not want to change the number of vertices in the graph. only the edges should be added or removed or switched. thanks
I see, so you don’t need all vertices to have the same degree, just many to have each degree that appears. Probably Yair’s paper would be a great place to start since they are forcing repetitions in the degree sequence. Even if it is not doing what you need, there should be strategies that are applicable. You May also need to look for Edit Distance, the number of edits (edge addition / removal) needed to make the graph do something you want. In my experience, this concept is not very well understood, but to be fair, I was looking for something specific related to Hamiltonicity.
If we have no restrictions on the process of removing, adding or switching edges, then we can add all missed edges and get what you need (the complete graph). The restrictions may be: 1) the number of operations have to be the minimal one; 2) the vertex degree can not increase (decrease) during the operation; etc.
I think you can convert this problem in matrix theory. if A be adjacency matrix of graph you can easily add edges.
Maryam - you need to give a more precise definition what you want to get and what are the operations allowed.
The reference I gave is to the case where the operation allowed is to delete vertices so that you get an induced subgraph with at least k equal degrees. And see in Arxiv recent progress related to this problem.
If you don't want to delete vertices then as far as I remember we looked at this question to equate k degrees by edge- deletion/addition and the answer was an easy ck^2 ( upper bound ) such "manipulations " suffices . And we decided not to deal with this edge-version problem.
Starting with the adjacency matrix of the graph in question, interchange the rows and columns of the graph in such a way that in the left hand corner of the mtrix become kxk mtrix which is J-I where J is a matrix of all 1s and I is a unit matrix of order k.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs