On the status sequences of trees

Aida Abiad Monge (Corresponding author), B. Brimkov, Alexander Grigoriev

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)

Samenvatting

The status of a vertex v in a connected graph is the sum of the distances from v to all other vertices. The status sequence of a connected graph is the list of the statuses of all the vertices of the graph. In this paper we investigate the status sequences of trees. Particularly, we show that it is NP-complete to decide whether there exists a tree that has a given sequence of integers as its status sequence. We also present some new results about trees whose status sequences are comprised of a few distinct numbers or many distinct numbers. In this direction, we show that any status injective tree is unique among trees. Finally, we investigate how orbit partitions and equitable partitions relate to the status sequence.
Originele taal-2Engels
Pagina's (van-tot)110-120
Aantal pagina's11
TijdschriftTheoretical Computer Science
Volume856
Vroegere onlinedatum28 dec. 2020
DOI's
StatusGepubliceerd - 8 feb. 2021

Vingerafdruk

Duik in de onderzoeksthema's van 'On the status sequences of trees'. Samen vormen ze een unieke vingerafdruk.

Citeer dit