|
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.
Citation:
V. N. Salii, “On the number of Sperner vertices in a tree”, Prikl. Diskr. Mat., 2016, no. 2(32), 115–118
Linking options:
https://www.mathnet.ru/eng/pdm548 https://www.mathnet.ru/eng/pdm/y2016/i2/p115
|
Statistics & downloads: |
Abstract page: | 126 | Full-text PDF : | 63 | References: | 40 |
|