11
$\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 ?

$\endgroup$
  • 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 Sep 18 '13 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 Sep 18 '13 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 Sep 18 '13 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 Sep 18 '13 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 Sep 19 '13 at 8:51
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.

$\endgroup$
3
$\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.

$\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.

$\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.

$\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.

$\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.

$\endgroup$
  • $\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 Sep 18 '13 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 Sep 18 '13 at 9:59
  • $\begingroup$ Yes it is always good to know it :) $\endgroup$ – Aline Parreau Sep 18 '13 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.

$\endgroup$
  • $\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 Sep 18 '13 at 15:36
  • $\begingroup$ I don't know anything about this. $\endgroup$ – Ira Gessel Sep 18 '13 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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