Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 4 down vote favorite

Is there a special name for the kind of subgraphs you get by taking some sequence of the following operation: Pick two vertices and identify them so all edges going to either vertex get sent to the new vertex.

share|improve this question
Note that if you contract only adjacent vertices of a graph $G$ you obtain a minor of $G$. – Jernej Jul 17 '12 at 6:48
Here is link to Wikipedia article on minors mentioned in Azoo's comment. – Martin Sleziak Jul 17 '12 at 12:28
I'm actually doing the opposite here and only contracting vertices which are not adjacent. My graph is the Hasse graph of a ranked poset and my identifications take place between vertices of the same rank. – user1390 Jul 18 '12 at 3:52

1 Answer

up vote 6 down vote accepted

You don't get a subgraph when you do that, but what you might call a quotient graph instead (the natural map goes the other way). The operation is called vertex contraction.

share|improve this answer
I like the name for this as it goes along with identification similar to the quotient topology. Thank you! (I was aware the output would not necessarily be a subgraph cause it's easy to see the maximal and average degree can increase, but I poorly phrased my question and used subgraph there instead of output.) – user1390 Jul 17 '12 at 13:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.