# twin free graphs

A graph is called twin-free if distinct vertices have different neighborhoods. I have no idea how to obtain twin-free graphs in Sagemath. Would please you help me?

twin free graphs

0

You could list all of the neighborhoods and see if there are any duplicates:

```
sage: g = graphs.DiamondGraph()
sage: [g.neighbors(v) for v in g.vertex_iterator()]
[[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
```

`g[v]`

is equivalent to `g.neighbors(v)`

, so we could do this instead:

```
sage: g = graphs.DiamondGraph()
sage: [g[v] for v in g.vertex_iterator()]
[[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
```

There are indeed duplicates; how to detect them? You can search the internet for "Python does list contain duplicates" to find lots of options, but one choice is to convert this list to a set, since sets do not contain duplicates. Sets cannot contain lists as elements, though, so convert each neighborhood to a tuple first:

```
sage: nbhds = [tuple(g[v]) for v in g.vertex_iterator()]
sage: nbhds
[(1, 2), (0, 2, 3), (0, 1, 3), (1, 2)]
sage: set(nbhds)
{(0, 1, 3), (0, 2, 3), (1, 2)}
sage: len(nbhds)
4
sage: len(set(nbhds))
3
```

So you can test whether `len(nbhds) == len(set(nbhds))`

.

Alternatively, the adjacency matrix records the neighbors of each vertex: there is a 1 in the `(i,j)`

entry of the matrix if there is an edge between vertices `i`

and `j`

, or equivalently, row `i`

of the matrix has 1's in the columns where its neighbors are. So if two rows of the matrix are the same, then two vertices have the same neighborhoods. You can write a similar test to detect this.

1

You can certainly use the modular decomposition of the graph to identify twins.

```
sage: G = graphs.DiamondGraph()
sage: G.modular_decomposition()
(SERIES, [(PARALLEL, [0, 3]), 1, 2])
sage: G = graphs.CompleteBipartiteGraph(2, 3)
sage: G.modular_decomposition()
(SERIES, [(PARALLEL, [2, 3, 4]), (PARALLEL, [0, 1])])
```

Please start posting anonymously - your entry will be published after you log in or create a new account.

Asked: ** 2022-09-16 14:44:19 +0200 **

Seen: **144 times**

Last updated: **Sep 17 '22**

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.

Is this homework? Try to find a way to determine whether a graph is twin-free and write a function

`is_twin_free`

that implements your algorithm. Then`L = [G for G in graphs(10) if is_twin_free(G)]`

will create a list of all graphs on 10 vertices which satisfy your condition.Or in the form of generator:

`graphs(10, property=is_twin_free)`

@MaxAlekseyev: I tried that first and it returns no graphs:

`list(graphs(10, property=is_twin_free))`

is empty, and`for g in graphs(10, property=is_twin_free): print(g)`

prints nothing.@John Palmieri, thank you. I know that function but let

I would like to know if this graph is twin-free. Using the code

`is_twin_free(G)`

I got the following error:or for

`G.is_twin_free()`

I got this one:As I said, "try to find a way to determine whether a graph is twin-free and write a function

`is_twin_free`

that implements your algorithm." You have to implement it, it does not already exist. Do you have any ideas?