MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have.

It is actually a way to write in a compact way a graph which has a lot of twin vertices: two vertices $u$ and $v$ are twin if $N(u)=N(v)$ (they are not adjacent).

Since the twin relation is an equivalence relation, there is a unique way to write any graph in a reduced form as a graph with vertex multiplicities.

Here is an example: Here is an example of the reduction

This representation is particularly useful when vertices represent some items with large quantity.

Does someone know if such a concept already exists ? What's the usual name ? Do you have some references ?

share|cite|improve this question
A similar but not identical equivalence relation was defined by Servatius in his study of graph groups (aka right-angled Artin groups). Write $u\geq v$ if $N(v)\subseteq N(u)\cup\{u\}$ and $u\sim v$ if $u\geq v$ and $v\geq u$. In other words, $u$ and $v$ are also allowed to be adjacent. – HJRW Sep 18 '13 at 8:57
Indeed, the equivalence classes with this relation will be either clique or stable sets. Do you know if anyone else use this relation and the reduced graph behind ? – Aline Parreau Sep 18 '13 at 9:16
It's heavily used in subsequent work on outer automorphisms of graph groups. Look at the citations of Servatius' paper. The reference is: H. Servatius, Automorphisms of graph groups, J. Algebra 126 (1989), no. 1, 34–60. – HJRW Sep 18 '13 at 9:49
I will look at it, thanks ! – Aline Parreau Sep 18 '13 at 9:52
A similar construction has been called binary relation orbifold (Borchmann, Daniel: Context Orbifolds, Diploma Thesis, TU Dresden, 2009, link). – Tobias Schlemmer Sep 18 '13 at 22:22
up vote 7 down vote accepted

In this paper, they call these objects "blow-up graphs", since the operation of adding twins to a vertex is commonly called a blow-up. Putting integer weights on the vertices of a graph to signify by how much to blow up a vertex like you do above is fairly common.

share|cite|improve this answer

This notion is complementary to the notion of vertex multiplication, in which every vertex is replaced with a homogeneous clique. This goes back to Lovasz' proof of the Weak Perfect Graph Theorem, and probably even earlier.

share|cite|improve this answer

I have heard this concept called, logically enough, "vertex multiplication." The first hit I got when I searched was Small Survey on Perfect Graphs by Michele Alberti. Be aware, though, that I've also heard the term "vertex multiplication" used when the multiple copies of a vertex form a clique rather than an independent set.

share|cite|improve this answer

As well as the use of this by Lovász for perfect graphs (mentioned by earlier answers), this has been used by Häggkvist to find high-degree four-chromatic triangle-free graphs. See

Häggkvist, R. (1981), "Odd cycles of specified length in nonbipartite graphs", Graph Theory (Cambridge, 1981), pp. 89–99, MR0671908.

share|cite|improve this answer
  1. You might want to look up this paper where reduced graphs are studied, in the sense of Servatius (or very similar to it), from the viewpoint of spectral graph theory.

  2. People have studied twin-free graphs quite a lot. One possible pointer is this.

share|cite|improve this answer

The equivalence relation that HJRW defines in the comments (that is twin vertices may be adjacent) is related to the cochromatic number $z(G)$ of a graph $G$. The cochromatic number of $G$ is the minimum number of colours needed to colour $V(G)$ such that each colour class induces a clique or stable set. Thus, the number of such equivalence classes gives an upper bound on the cochromatic number.

share|cite|improve this answer
I agree but it does not really help with my question : with my relation it already gives an upperbound on the chromatic number, but it could be very bad ! – Aline Parreau Sep 18 '13 at 9:53
I agree. In general, I try to be pretty liberal with my answers to reference requests, since usually it is unclear what the OP is exactly looking for. Ergo, it is possible that some semi-related concept may be helpful. Sorry if it was not in this case. =) – Tony Huynh Sep 18 '13 at 9:59
Yes it is always good to know it :) – Aline Parreau Sep 18 '13 at 18:15

A graph in which no two vertices have the same neighborhood is called a point-determining graph or mating graph or mating-type graph. See A006024 for references.

share|cite|improve this answer
Thanks for the name and the reference. I can indeed assume that my graph is point-determining. But what about adding multiplicities on the vertices ? Do you know if something similar exists ? – Aline Parreau Sep 18 '13 at 15:36
I don't know anything about this. – Ira Gessel Sep 18 '13 at 16:44

Your Answer


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.