Opened 4 years ago

Closed 4 years ago

#25613 closed defect (fixed)

Graph.is_gallai_tree() method has an error in the code

Reported by: gh-math1um Owned by:
Priority: minor Milestone: sage-8.3
Component: graph theory Keywords:
Cc: dcoudert Merged in:
Authors: Frédéric Chapoton Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: f8a9c73 (Commits, GitHub, GitLab) Commit: f8a9c73afdb06dfe3b92d80cb47d57b2b56fe342
Dependencies: Stopgaps:

Status badges

Description (last modified by nvcleemp)

The Graph.is_gallai_tree() method checks for whether a block's vertices induce a cycle tests if the number of edges is one more than the number of vertices. These should be the same.

The third-to-last-line currently has the test: gg.size() == len(c)+1

It *should* have the test: gg.size() == len(c)

A graph which is a 5-cycle with an appended edge to an external vertex is a gallai tree. But the existing method returns False. Call this graph "gg":


should return: True.

Change History (5)

comment:1 Changed 4 years ago by nvcleemp

  • Type changed from PLEASE CHANGE to defect

comment:2 Changed 4 years ago by nvcleemp

  • Description modified (diff)

comment:3 Changed 4 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to public/25613
  • Cc dcoudert added
  • Commit set to f8a9c73afdb06dfe3b92d80cb47d57b2b56fe342
  • Status changed from new to needs_review

New commits:

f8a9c73fixing is_gallai_tree

comment:4 Changed 4 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review


comment:5 Changed 4 years ago by vbraun

  • Branch changed from public/25613 to f8a9c73afdb06dfe3b92d80cb47d57b2b56fe342
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.