Time-stamped graphs and their associated influence digraphs
type: Item
instance of: scholarly article
title: Time-stamped graphs and their associated influence digraphs
zbMATH Open document ID: 1019.05037
DOI: 10.1016/S0166-218X(02)00497-3
author: Eddie Cheng
author: Jerrold W. Grossman
author: Marc J. Lipman
published in: Discrete Applied Mathematics
publication date: 2003-06-10T00:00:00Z
review text: A time-stamped graph is a graph \(G=(V,E)\) with a real-valued function \(c\) defined on its edges. If \(u\) and \(v\) are vertices in such a graph, \(u\) influences \(v\) if there is a path from \(u\) to \(v\), whose sequence of real number labels is nondecreasing. The associated influence digraph of \(G\), denoted \(G^1_c\) is the digraph with vertex set \(V\), where \((u,v)\) is an arc if \(u\) influences \(v\). The authors show that certain classes of graphs are ``realizable'' as associated influence digraphs. In particular, for the class of trees, given positive integers \(t\) and \(m\), there is a tree with \(m+1\) vertices and a function \(c\) such that the associated influence digraph has \(t\) arcs. They obtain results for the minimum number of vertices a digraph \(D\) can have so that \(D\) will be an induced subgraph of its associated influence digraph.
reviewed by: Norman F. Quimpo
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 91D30
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 1925291
zbMATH Keywords: time-stamped graph
zbMATH Keywords: influence digraph
zbMATH Keywords: Erdős number
MaRDI profile type: Publication
cites work: Famous trails to Paul Erdős. With a sidebar by Paul M. B. Vitanyi.
cites work: A survey of gossiping and broadcasting in communication networks
description: scientific article; zbMATH DE number 1925291