Ask Your Question
0

twin free graphs

asked 2022-09-16 14:44:19 +0200

salam gravatar image

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 flag offensive close merge delete

Comments

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.

John Palmieri gravatar imageJohn Palmieri ( 2022-09-16 23:52:28 +0200 )edit

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

Max Alekseyev gravatar imageMax Alekseyev ( 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.

John Palmieri gravatar imageJohn Palmieri ( 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'
salam gravatar imagesalam ( 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?

John Palmieri gravatar imageJohn Palmieri ( 2022-09-17 20:13:24 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted
0

answered 2022-09-17 22:19:56 +0200

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.

edit flag offensive delete link more

Comments

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])])
David Coudert gravatar imageDavid Coudert ( 2022-09-18 10:25:06 +0200 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

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

Seen: 62 times

Last updated: Sep 17