Label-connected graphs and the gossip problem

DOI10.1016/0012-365X(91)90068-DMaRDI QIDQ804593zbMATH OpenFDO

Authors N. E. Zubov

Publication date 1991

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(91)90068-D

zbMATH Keywords

label-connected graph

Mathematics Subject Classification ID

Connectivity (05C40) Graph theory (05C99)

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.

Recommendations

• Some minimum gossip graphs
• The e-mail gossip number and the connected domination number
• Note on optimal gossiping in some weak-connected graphs
• Broadcast and gossip in line-communication mode
• scientific article; zbMATH DE number 3910097

Cites work

• A Problem with Telephones
• Edge-Disjoint Spanning Trees of Finite Graphs
• Further gossip problems
• Graph theory
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the Problem of Decomposing a Graph into n Connected Factors
• The communication problem on graphs

Cited in

(15)

• The e-mail gossip number and the connected domination number
• Kernels of minimum size gossip schemes
• Reordered gossip schemes
• Connectivity and inference problems for temporal networks
• Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks
• Temporally connected components
• The complexity of computing optimum labelings for temporal connectivity
• Temporalizing digraphs via linear-size balanced bi-trees
• Parameterized algorithms for multi-label periodic temporal graph realization
• Temporal graph realization with bounded stretch
• Temporal graph realization with bounded stretch
• Recognizing and realizing temporal reachability graphs
• The shortest temporal exploration problem
• Realization of temporally connected graphs based on degree sequences
• Simple, strict, proper, and directed: comparing reachability in directed and undirected temporal graphs

This page was built for publication: Label-connected graphs and the gossip problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804593)