ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 18 Sep 2022 10:25:06 +0200twin free graphshttps://ask.sagemath.org/question/64033/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?Fri, 16 Sep 2022 14:44:19 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/Comment by John Palmieri for <p>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?</p>
https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64069#post-id-64069https://lmgtfy.app/?q=adjacency+matrixSun, 18 Sep 2022 02:21:09 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64069#post-id-64069Comment by salam for <p>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?</p>
https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64065#post-id-64065@John Palmieri, Yes, the natural way is to obtain the neighborhoods of any two vertices and compare them. To find an optimized solution, I asked this question. I have no idea about the adjacency matrix. Please tell me more.Sat, 17 Sep 2022 21:22:15 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64065#post-id-64065Comment by John Palmieri for <p>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?</p>
https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64064#post-id-64064The adjacency matrix is one option, for example.Sat, 17 Sep 2022 20:34:48 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64064#post-id-64064Comment by John Palmieri for <p>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?</p>
https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64063#post-id-64063As 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?Sat, 17 Sep 2022 20:13:24 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64063#post-id-64063Comment by salam for <p>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?</p>
https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64060#post-id-64060@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'Sat, 17 Sep 2022 18:25:52 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64060#post-id-64060Comment by John Palmieri for <p>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?</p>
https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64059#post-id-64059@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.Sat, 17 Sep 2022 17:36:25 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64059#post-id-64059Comment by Max Alekseyev for <p>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?</p>
https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64058#post-id-64058Or in the form of generator: `graphs(10, property=is_twin_free)`Sat, 17 Sep 2022 15:23:36 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64058#post-id-64058Comment by John Palmieri for <p>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?</p>
https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64044#post-id-64044Is 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.Fri, 16 Sep 2022 23:52:28 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64044#post-id-64044Answer by John Palmieri for <p>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?</p>
https://ask.sagemath.org/question/64033/twin-free-graphs/?answer=64067#post-id-64067You 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.
Sat, 17 Sep 2022 22:19:56 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/?answer=64067#post-id-64067Comment by David Coudert for <p>You could list all of the neighborhoods and see if there are any duplicates:</p>
<pre><code>sage: g = graphs.DiamondGraph()
sage: [g.neighbors(v) for v in g.vertex_iterator()]
[[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
</code></pre>
<p><code>g[v]</code> is equivalent to <code>g.neighbors(v)</code>, so we could do this instead:</p>
<pre><code>sage: g = graphs.DiamondGraph()
sage: [g[v] for v in g.vertex_iterator()]
[[1, 2], [0, 2, 3], [0, 1, 3], [1, 2]]
</code></pre>
<p>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:</p>
<pre><code>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
</code></pre>
<p>So you can test whether <code>len(nbhds) == len(set(nbhds))</code>. </p>
<p>Alternatively, the adjacency matrix records the neighbors of each vertex: there is a 1 in the <code>(i,j)</code> entry of the matrix if there is an edge between vertices <code>i</code> and <code>j</code>, or equivalently, row <code>i</code> 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.</p>
https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64072#post-id-64072You 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])])Sun, 18 Sep 2022 10:25:06 +0200https://ask.sagemath.org/question/64033/twin-free-graphs/?comment=64072#post-id-64072