Determination of the star valency of a graph
The star valency of a graph G is the minimum, over all star decompositions ?, of the maximum number of elements in ? incident with a vertex. The maximum average degree of G, denoted by dmax-ave(G), is the maximum average degree of all subgraphs of G. In this paper, we prove that the star valency of G is either ?dmax-ave(G)/2? or ?dmax-ave(G)/2?+1, and provide a polynomial time algorithm for determining the star valency of a graph.
star valency graph average degree algorithm orientation