# 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?

edit retag close merge delete

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.

( 2022-09-16 23:52:28 +0200 )edit

Or in the form of generator: graphs(10, property=is_twin_free)

( 2022-09-17 15:23:36 +0200 )edit

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

( 2022-09-17 17:36:25 +0200 )edit

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

G=graphs.CompleteBipartiteGraph(2,2);


I would like to know if this graph is twin-free. Using the code is_twin_free(G) I got the following error:

NameError: name 'is_twin_free' is not defined


or for G.is_twin_free() I got this one:

AttributeError: 'Graph' object has no attribute 'is_twin_free'

( 2022-09-17 18:25:52 +0200 )edit

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?

( 2022-09-17 20:13:24 +0200 )edit

Sort by ยป oldest newest most voted

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.

more

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])])

( 2022-09-18 10:25:06 +0200 )edit