Fwd: [sage-trac-account] Corrections about the function "is_prime" for graphs

[Harald Schilly]

This came in via the trac account request. I don't know the sender's
email address ...

-- h


---------- Forwarded message ----------
From: 'Jamel Dammak' via sage-trac-account <sage-tra...@googlegroups.com>
Date: Sun, Dec 11, 2016 at 10:01 PM
Subject: [sage-trac-account] Corrections about the function "is_prime"
for graphs
To: "sage-tra...@googlegroups.com" <sage-tra...@googlegroups.com>


Dear sir,

there is an error concerning the function "is_prime" for graphs in
Sagemath, section Graph Theory.

Here is a conter-example.

g1=Graph({0:[1,4],1:[0,2,4],2:[1,3,4],3:[2],4:[0,1,2]});g2=Graph({0:[1],1:[0,2,4],2:[1,3,4],3:[2,4],4:[1,2,3]})
#g1.show();g2.show();
#[1,4] is a module of g1 so g1 is not prime
g2.is_isomorphic(g1), g1.is_prime(),g2.is_prime()

This is a conter-example with two isomorphic graphs g1 and g2 on 5
vertices giving two different results
with the function "is prime".

I have an algorithm giving the list of all prime graphs on at most 8 vertices.

Best regards.

--
--
You received this message because you are subscribed to the Google
Groups "sage-trac-account" group.
To post to this group, send email to sage-tra...@googlegroups.com
To unsubscribe from this group, send email to
sage-trac-acco...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-trac-account

---
You received this message because you are subscribed to the Google
Groups "sage-trac-account" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to sage-trac-acco...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Dima Pasechnik]

Sooner or later it was bound to happen; this function relies on modular_decomposition optional package,

which is very iffy, and ought to be removed or redone, see  https://trac.sagemath.org/ticket/17950

Should we do something about it?

@Harald - you can see the sender email by doing show source on the message; I put it into cc to this message.

[Dima Pasechnik]

in fact, the output quite telling:

sage: g1=Graph({0:[1,4],1:[0,2,4],2:[1,3,4],3:[2],4:[0,1,2]});g2=Graph({0:[1],1:[0,2,4],2:[1,3,4],3:[2,4],4:[1,2,3]})

sage: g1.is_prime()

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/graphs/graph.py:6842:

********************************************************************************

Graph.modular_decomposition is known to return wrong results

This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/13744.

********************************************************************************

True

sage: g2.is_prime()

False

[Mohamed Khemakhem]

Hi, the sender is Jamel Dammak his email adress is jda...@yahoo.fr