RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2016 Number 2(32), Pages 115–118 (Mi pdm548)

Applied Graph Theory

On the number of Sperner vertices in a tree

V. N. Salii

Saratov State University, Saratov, Russia

Abstract: A vertex $v$ of a tree $T$ is called a Sperner vertex if the in-tree $T(v)$ obtained from $T$ by orientation of all edges towards $v$ has the Sperner property, i.e. there exists a largest subset $A$ of mutually unreachable vertices in it such that all vertices in $A$ are equidistant to $v$. Some explicit methods to count the number of Sperner vertices in certain special trees are presented.

Keywords: graph, Sperner vertex, path, star, palm-tree, rank, caterpillar, train of palm-trees.

UDC: 519.17

DOI: 10.17223/20710410/32/8



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024