Cycle stochastic graphs: Structural and forbidden graph characterizations

Abstract

A vertex (respectively, edge) cycle stochastic function of a graph G is a labeling of vertices (respectively, edges) by a non-negative real valued function (respectively, ) such that for every cycle of G, the sum of labels of its vertices (respectively, edges) is 1. The graphs where we can define such a function are called vertex cycle stochastic graphs (respectively, edge cycle stochastic graphs). In this paper, we provide a structure theorem for biconnected cycle stochastic graphs, which is extended to characterize edge cycle stochastic graphs. We also find a minimal forbidden graph characterization for biconnected vertex cycle stochastic graphs and its description for vertex cycle stochastic graphs.

Keywords

• cycle stochastic graphs
• structural characterization
• minimal forbidden graph characterization