Jump to content

Talk:Vertex separator

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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]