12
$\begingroup$

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 ?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – HJRW
    Commented Sep 18, 2013 at 8:57
  • $\begingroup$ 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 ? $\endgroup$
    – Aline Parreau
    Commented Sep 18, 2013 at 9:16
  • $\begingroup$ 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. $\endgroup$
    – HJRW
    Commented Sep 18, 2013 at 9:49
  • $\begingroup$ A similar construction has been called binary relation orbifold (Borchmann, Daniel: Context Orbifolds, Diploma Thesis, TU Dresden, 2009, link). $\endgroup$
    – Tobias Schlemmer
    Commented Sep 18, 2013 at 22:22
  • $\begingroup$ This is also a special case of the "generalized lexicographic product of graphs", also known as "local join" or "composition" $G[H_1,H_2,\dots,H_n]$ where the $H_i$ consist of isolated vertices only. See eg. Sabidussi, "Graph derivatives" or item 16 of Section 2.7 in Cvetkovic, Doob, Sachs, "Spectra of Graphs". $\endgroup$
    – Martin Rubey
    Commented Sep 19, 2013 at 8:51

7 Answers 7

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

  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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 ! $\endgroup$
    – Aline Parreau
    Commented Sep 18, 2013 at 9:53
  • $\begingroup$ 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. =) $\endgroup$
    – Tony Huynh
    Commented Sep 18, 2013 at 9:59
  • $\begingroup$ Yes it is always good to know it :) $\endgroup$
    – Aline Parreau
    Commented Sep 18, 2013 at 18:15
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – Aline Parreau
    Commented Sep 18, 2013 at 15:36
  • $\begingroup$ I don't know anything about this. $\endgroup$
    – Ira Gessel
    Commented Sep 18, 2013 at 16:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .