##### NoteDetermination of the star valency of a graph

Review articleOpen access###### Jinquan Dong - No affiliation found

**2003/03/15**DOI: 10.1016/S0166-218X(02)00202-0

*Short communication***Journal:**Discrete Applied Mathematics

##### Abstract:

AbstractThe 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.

Request full text