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 ?

$\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
    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$ 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
    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$ 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$ Sep 19, 2013 at 8:51

7 Answers 7

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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