Back to Search
Start Over
Generalized vertex-rankings of trees
- Source :
- Information Processing Letters. 56:321-328
- Publication Year :
- 1995
- Publisher :
- Elsevier BV, 1995.
-
Abstract
- We newly define a generalized vertex-ranking of a graph G as follows: for a positive integer c, a c-vertex-ranking of G is a labeling (ranking) of the vertices of C with integers such that, for any label i, every connected component of the graph obtained from G by deleting the vertices with label > i has at most c vertices with label i. Clearly an ordinary vertex-ranking is a l-vertex-ranking and vice-versa. We present an algorithm to find a c-vertex-ranking of a given tree T using the minimum number of ranks in time O(cn) where n is the number of vertices in T.
- Subjects :
- Discrete mathematics
Graph center
InformationSystems_INFORMATIONSTORAGEANDRETRIEVAL
Edge-graceful labeling
Neighbourhood (graph theory)
Computer Science Applications
Theoretical Computer Science
Combinatorics
Computer Science::Discrete Mathematics
Graph power
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
Signal Processing
Wheel graph
Path graph
Bound graph
Distance
MathematicsofComputing_DISCRETEMATHEMATICS
Information Systems
Mathematics
Subjects
Details
- ISSN :
- 00200190
- Volume :
- 56
- Database :
- OpenAIRE
- Journal :
- Information Processing Letters
- Accession number :
- edsair.doi...........04b332d1e760e912eee76a09ce0ad05e
- Full Text :
- https://doi.org/10.1016/0020-0190(95)00172-7