Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.

Related Articles:

• Prediction of Nucleotide Binding Peptides Using Star Graph Topological Indices.

• A Novel Protein Characterization Based on Pseudo Amino Acids Composition and Star-Like Graph Topolog Read more...

• A Survey of Graph Cuts/Graph Search Based Medical Image Segmentation.

• Graph mining for next generation sequencing: leveraging the assembly graph for biological insights.

• RNA graph partitioning for the discovery of RNA modularity: a novel application of graph partition a Read more...

NoteDetermination of the star valency of a graph

Jinquan Dong - No affiliation found

2003/03/15 Short communication DOI: 10.1016/S0166-218X(02)00202-0 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.