Time-stamped graphs and their associated influence digraphs (Q1811116): Difference between revisions

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.