Template:Did you know nominations/Halin graph

The following is an archived discussion of the DYK nomination of the article below. Please do not modify this page. Subsequent comments should be made on the appropriate discussion page (such as this nomination's talk page, the article's talk page or Wikipedia talk:Did you know), unless there is consensus to re-open the discussion at this page. No further edits should be made to this page.

The result was: promoted by Desertarun (talk) 15:15, 1 August 2021 (UTC)

DYK toolbox
DYK check Reviewer instructions Earwig's Copyvio Detector QPQ check Character count A Simple Word Counter Reviewers' template Find sources (notability) Hook length

• ... that when a tree is a star, connecting its leaves in a cycle makes a wheel? Source: Cornuéjols et al (1983), Halin graphs and the travelling salesman problem: "If T is a star, i.e., a single node v joined to n other nodes, then H is called a wheel and is the simplest type of Halin graph."
  • ALT1:... that many hard combinatorial optimization problems are easier on Halin graphs because of their low treewidth? Source: Bodlaender (1988), Dynamic programming on graphs with bounded treewidth: "we show for a large number of graph decision problems ... the existence of O(n^C) or polynomial algorithms for these problems, restricted to the graphs with bounded treewidth"

• Reviewed: Sacred Heart of Jesus (Batoni)

Improved to Good Article status by David Eppstein (talk). Self-nominated at 00:39, 21 July 2021 (UTC).

General: Article is new enough and long enough
New enough: Long enough:

Policy: Article is sourced, neutral, and free of copyright problems
Adequate sourcing: Neutral: Free of copyright violations, plagiarism, and close paraphrasing:

Hook: Hook has been verified by provided inline citation
Cited: Interesting:

QPQ: Done.

Overall: Long enough, new enough, well sourced, neutral, no copyvio. Both the hook and the article itself are really interesting. Ready to go! Zin Win Hlaing (talk) 04:09, 24 July 2021 (UTC)