Talk:Vertex separator

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Low	This article has been rated as Low-priority on the project's priority scale.

Computer science Mid‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

What is a “free tree”?[edit]

This article refers to “free tree[s]”, but the link on those words links to the article on trees. Is there any distinction to be made wrt. non-free trees (if they exist)? Theanswertolifetheuniverseandeverything (talk) 15:11, 6 July 2023 (UTC)[reply]

It merely means that the tree is considered as an undirected graph, rather than as having a root. —David Eppstein (talk) 19:06, 6 July 2023 (UTC)[reply]

Balanced vertex separator in a tree[edit]

The tree example and associated figure seems to mistakenly assume that a center and a balanced vertex separator is the same (I know the latter as a "centroid" or a special case of a "median"). They are not; take for example an n-vertex path and add n-1 leaves to one end. The center(s) is/are roughly on the middle of the path, but the unique centroid is on the end where the leaves where added.

The part about there being always exactly one or exactly two centroids is correct, but that has nothing to do with centered/bicentered trees or eccentricity. I can edit that section unless somebody objects. BABerendsohn (talk) 14:10, 13 March 2024 (UTC)[reply]