NoteDetermination of the star valency of a graph
Review articleOpen access

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

References (0)

Cited By (0)

No reference data.
No citation data.
Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.
Join for free!