#17532: Convexity properties on graphs works incorrectly
--------------------------------+------------------------
Reporter: azi | Owner:
Type: defect | Status: new
Priority: critical | Milestone: sage-6.5
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
--------------------------------+------------------------
Comment (by ncohen):
> 1. By implementing a different algorithm and getting 4 as an answer
> 2. By drawing the solution given by sage and seeing that it does not
give the whole graph
> 3. Arguing as follows. In the Petersen graph any pair of vertices is
connected by a UNIQUE shortest path and has diameter 2. Hence 3 vertices
give you a hull of size at most 3+ (3 \choose 2)*1 = 9
> 4. By checking this paper
http://ajc.maths.uq.edu.au/pdf/26/ajc_v26_p011.pdf where it says that the
Petersen graph has hull number 4.
The paper you cite talks about the geodetic number, not the hull number.
The computation that you do in 3 is only correct for the geodetic number.
Thus I tend to think that the same reason explains 1 and 2 as well.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17532#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
