Cycle stochastic graphs: Structural and forbidden graph characterizations. Issue 3 (1st September 2020)

• Record Type: Journal Article
• Authors: Rao, S. B.; Sahoo, U. K.; Parameswaran, V.
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 3(2020)
• Page Start: 1076
• Page End: 1080
• Publication Date: 2020-09-01
• Subjects: Cycle stochastic graphs -- structural characterization -- minimal forbidden graph characterization
• DOI: 10.1016/j.akcej.2020.01.004
• Languages: English
• ISSNs: 0972-8600

Abstract

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 f V : V ( G ) → R + ∪ { 0 } (respectively, f E : E ( G ) → R + ∪ { 0 } ) 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.