Determination of the star valency of a graph
type: Item
instance of: scholarly article
title: Determination of the star valency of a graph
zbMATH Open document ID: 1012.05095
DOI: 10.1016/S0166-218X(02)00202-0
author: Jin Quan Dong
author: Yanpei Liu
author: Cun-Quan Zhang
published in: Discrete Applied Mathematics
publication date: 2003-03-09T00:00:00Z
review text: A star decomposition \(P\) of a graph \(G\) is a decomposition of the edge set of \(G\) into stars. Let \(M(P)\) be a maximum number of stars in \(P\) containing a vertex. The star valency of \(G\) is the minimum of \(M(P)\) taken over all star decompositions of \(G.\) In the paper, a polynomial time algorithm for determining the star valency of a graph is given.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1878539
zbMATH Keywords: star valency
zbMATH Keywords: polynomial algorithm
reviewed by: Peter Horák
MaRDI profile type: Publication
cites work: Q5422499
cites work: Covering a graph by complete bipartite graphs
cites work: Bipartite dimensions and bipartite degrees of graphs
description: scientific article; zbMATH DE number 1878539