Label-connected graphs and the gossip problem
type: Item
instance of: scholarly article
title: Label-connected graphs and the gossip problem
zbMATH Open document ID: 0728.05040
DOI: 10.1016/0012-365X(91)90068-D
author: N. E. Zubov
published in: Discrete Mathematics
publication date: 1991-01-01T00:00:00Z
review text: A graph G is called label-connected if the edges of G can be labeled by real numbers so that for every pair (u,v) of vertices of G there is an (u,v)-path with ascending labels. It is shown (using the gossip problem) that the minimum number of edges of a label-connected graph on n vertices is 2n-4. A necessary and sufficient condition for a graph to be label-connected is given. It is proved that recognizing label-connected graphs is NP-complete.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4202297
zbMATH Keywords: label-connected graph
reviewed by: Peter Horák
MaRDI profile type: Publication
cites work: Q5422499
cites work: A Problem with Telephones
cites work: Q4198056
cites work: The communication problem on graphs
cites work: Further gossip problems
cites work: Q3048571
cites work: Edge-Disjoint Spanning Trees of Finite Graphs
cites work: On the Problem of Decomposing a Graph into n Connected Factors
description: scientific article; zbMATH DE number 4202297