On the status sequences of trees

DOI10.1016/J.TCS.2020.12.030zbMATH Open1476.68189arXiv1812.03765OpenAlexW3115004624MaRDI 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 $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 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

• Weakly status injective trees are status unique in trees.
• Pairs of a tree and a nontree graph with the same status sequence
• Spiders are status unique in trees
• On constructing graphs with the same status sequence.
• Minimum status of trees with given parameters

zbMATH Keywords

treegraph partitioncomplexitystatus sequencestatus injective

Mathematics Subject Classification ID

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (9)

• 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
• The Serial Transitive Closure Problem for Trees
• Arbres et suites majeures. (Trees and major sequences)
• Trees, taxonomy, and strongly compatible multi-state characters

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)