On the status sequences of trees
From MaRDI portal
Publication:2219062
Abstract: The status of a vertex in a connected graph is the sum of the distances from 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 results about trees whose status sequences are comprised of a few distinct numbers or many distinct numbers. In this direction, we provide a partial answer to a conjecture of Shang and Lin from 2011, showing that any status injective tree is unique among trees. Finally, we investigate how orbit partitions and equitable partitions relate to the status sequence.
Recommendations
Cites work
- scientific article; zbMATH DE number 3169205 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 194437 (Why is no real title available?)
- scientific article; zbMATH DE number 2230268 (Why is no real title available?)
- A linear time algorithm for metric dimension of cactus block graphs
- Alternative parameterizations of \textsc{Metric Dimension}
- Compact graphs and equitable partitions
- Constructing status injective graphs
- Distance in graphs
- Distance mean-regular graphs
- Distance spectrum of graph compositions
- Graphs that are cospectral for the distance Laplacian
- Integer Programming with a Fixed Number of Variables
- Landmarks in graphs
- Locating a robber on a graph
- Locating a robber on a graph via distance queries
- Minimum statuses of connected graphs with fixed maximum degree and order
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- On constructing graphs with the same status sequence.
- On the Wiener index, distance cospectrality and transmission-regular graphs
- On the distance Laplacian spectra of graphs
- On the distance spectra of some graphs
- On the metric dimension of some families of graphs
- Pairs of a tree and a nontree graph with the same status sequence
- Problems in algebraic combinatorics
- Spiders are status unique in trees
- Two Laplacians for the distance matrix of a graph
- Weakly status injective trees are status unique in trees.
- Wiener dimension: fundamental properties and \((5,0)\)-nanotubical fullerenes
Cited in
(14)- Weakly status injective trees are status unique in trees.
- Spiders are status unique in trees
- scientific article; zbMATH DE number 1185606 (Why is no real title available?)
- Pairs of a tree and a nontree graph with the same status sequence
- scientific article; zbMATH DE number 7267318 (Why is no real title available?)
- New transmission irregular chemical graphs
- Statuses and branch-weights of weighted trees
- Minimum status of trees with a given degree sequence
- Minimum status of series-reduced trees with given parameters
- The Serial Transitive Closure Problem for Trees
- Arbres et suites majeures. (Trees and major sequences)
- Which numbers are status differences?
- Trees, taxonomy, and strongly compatible multi-state characters
- On constructing graphs with the same status sequence.
This page was built for publication: On the status sequences of trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2219062)
