Star number and star arboricity of a complete multigraph期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Star number and star arboricity of a complete multigraph

Authors:

Institution:

(1) Department of Mathematics, National Central University, Chung-Li, Taiwan;(2) College of International Studies and Education for Overseas Chinese, National Taiwan Normal University, Linkou, Taipei Hsien, Taiwan

Abstract:

Let G be a multigraph. The star number s(G) of G is the minimum number of stars needed to decompose the edges of G. The star arboricity sa(G) of G is the minimum number of star forests needed to decompose the edges of G. As usual λK _n denote the λ-fold complete graph on n vertices (i.e., the multigraph on n vertices such that there are λ edges between every pair of vertices). In this paper, we prove that for n ⩾ 2

$s(\lambda K_n ) = \left\{ {_{\frac{1}{2}(\lambda + 1)n - 1 if \lambda is odd,}^{\frac{1}{2}\lambda n if \lambda is even,} } \right.$

((1))

$sa(\lambda K_n ) = \left\{ {_{\left\lceil {\frac{1}{2}\lambda n} \right\rceil + 1 if \lambda is odd, n \geqslant 4.}^{\left\lceil {\frac{1}{2}\lambda n} \right\rceil if \lambda is odd, n = 2,3 or \lambda is even,} } \right.$

((2))

Keywords:

decomposition star arboricity star forest complete multigraph

本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏