Opened 18 months ago
Closed 11 months ago
#28243 closed enhancement (fixed)
Accelerate `is_cactus()`
Reported by:  ghrbarnes  Owned by:  

Priority:  minor  Milestone:  sage9.1 
Component:  graph theory  Keywords:  cactus 
Cc:  Merged in:  
Authors:  João Tavares  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  ac1cf88 (Commits)  Commit:  ac1cf884ade760e719e48a5c44461e7065370c9a 
Dependencies:  Stopgaps: 
Description
This proof could be used to accelerate is_cactus()
by providing a quick O(1) check that can detect a large class of graphs which are not cactuses. This, in turn, would be helpful for situations where is_cactus()
is applied to large graphs.
Change History (11)
comment:1 Changed 18 months ago by
comment:2 Changed 18 months ago by
 Component changed from group theory to graph theory
If you are not able to double check the proof, it's better to find a reference (article, school book, etc.). This looks like a class exercise...
comment:3 Changed 18 months ago by
Actually, fill free to add the test without reference. This result is well known and often used as an exercise. Furthermore, this is a tight bound and we have graphs reaching it.
sage: for n in range(1, 10): ....: G = graphs.FriendshipGraph(n) ....: G.size() == 3 * (G.order()  1) / 2 ....: True True True True True True True True True sage: for _ in range(10): ....: G = graphs.RandomBlockGraph(10, 3) ....: G.size() == 3 * (G.order()  1) / 2 ....: True True True True True True True True True True
comment:4 Changed 13 months ago by
 Milestone changed from sage8.9 to sage9.1
Ticket retargeted after milestone closed
comment:5 Changed 11 months ago by
 Branch set to u/ghtabus/accelerate__is_cactus___
comment:6 Changed 11 months ago by
 Commit set to ac1cf884ade760e719e48a5c44461e7065370c9a
 Status changed from new to needs_review
New commits:
ac1cf88  Added the necessary condition check

comment:7 Changed 11 months ago by
 Reviewers set to David Coudert
Please add your full name in the field Authors
of this page.
comment:8 followup: ↓ 9 Changed 11 months ago by
comment:9 in reply to: ↑ 8 Changed 11 months ago by
Replying to ghtabus: Here it is. Is there anything else that should be done?
comment:10 Changed 11 months ago by
 Status changed from needs_review to positive_review
For this simple test, this is enough.
comment:11 Changed 11 months ago by
 Branch changed from u/ghtabus/accelerate__is_cactus___ to ac1cf884ade760e719e48a5c44461e7065370c9a
 Resolution set to fixed
 Status changed from positive_review to closed
(I have not yet found an academic citation for the theorem.)