On the status sequences of trees
From MaRDI portal
Publication:2219062
DOI10.1016/J.TCS.2020.12.030zbMATH Open1476.68189OpenAlexW3115004624MaRDI QIDQ2219062FDOQ2219062
Authors: Aida Abiad, Boris Brimkov, Alexander Grigoriev 
Publication date: 19 January 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1812.03765
Recommendations
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Distance spectrum of graph compositions
- Problems in algebraic combinatorics
- Integer Programming with a Fixed Number of Variables
- On the metric dimension of some families of graphs
- Two Laplacians for the distance matrix of a graph
- Wiener dimension: fundamental properties and \((5,0)\)-nanotubical fullerenes
- Title not available (Why is that?)
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Distance in graphs
- Title not available (Why is that?)
- Landmarks in graphs
- A linear time algorithm for metric dimension of cactus block graphs
- Graphs that are cospectral for the distance Laplacian
- Locating a robber on a graph via distance queries
- On the distance spectra of some graphs
- Compact graphs and equitable partitions
- Locating a robber on a graph
- On the distance Laplacian spectra of graphs
- Constructing status injective graphs
- Spiders are status unique in trees
- Title not available (Why is that?)
- Distance mean-regular graphs
- On the Wiener index, distance cospectrality and transmission-regular graphs
- Minimum statuses of connected graphs with fixed maximum degree and order
- Alternative parameterizations of \textsc{Metric Dimension}
- Pairs of a tree and a nontree graph with the same status sequence
- On constructing graphs with the same status sequence.
- Weakly status injective trees are status unique in trees.
Cited In (14)
- Title not available (Why is that?)
- Spiders are status unique in trees
- Pairs of a tree and a nontree graph with the same status sequence
- Title not available (Why is that?)
- 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
- Which numbers are status differences?
- Arbres et suites majeures. (Trees and major sequences)
- Trees, taxonomy, and strongly compatible multi-state characters
- On constructing graphs with the same status sequence.
- Weakly status injective trees are status unique in trees.
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)
