# Does the notion of graphs with vertex multiplicity exist?

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:

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 ?

-
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
show 1 more comment

## 7 Answers

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.

-
add comment

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.

-
add comment

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.

-
add comment

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.

-
add comment
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.

-
add comment

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.

-
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
add comment

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.

-
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
add comment