On the status sequences of trees
From MaRDI portal
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
- 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
- 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?)
- 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 constructing graphs with the same status sequence.
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- On the distance Laplacian spectra of graphs
- On the distance spectra of some graphs
- On the metric dimension of some families of graphs
- On the Wiener index, distance cospectrality and transmission-regular 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
(16)- Trees, taxonomy, and strongly compatible multi-state characters
- Constructing status injective graphs
- Minimum status of series-reduced trees with given parameters
- Which numbers are status differences?
- Pairs of a tree and a nontree graph with the same status sequence
- Minimum status of trees with a given degree sequence
- On constructing graphs with the same status sequence.
- Statuses and branch-weights of weighted trees
- scientific article; zbMATH DE number 1185606 (Why is no real title available?)
- The Serial Transitive Closure Problem for Trees
- Weakly status injective trees are status unique in trees.
- scientific article; zbMATH DE number 7267318 (Why is no real title available?)
- Spiders are status unique in trees
- New transmission irregular chemical graphs
- An efficient algorithm for generating transmission irregular trees
- Arbres et suites majeures. (Trees and major sequences)
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)
