Advanced Search

Let $G$ be a multigraph. The star number $\mathrm{s}\left(G\right)$ of $G$ is the minimum number of stars needed to decompose the edges of $G$. The star arboricity $\mathrm{s}a\left(G\right)$ of $G$ is the minimum number of star forests needed to decompose the edges of $G$. As usual $\lambda K_n$ denote the $\lambda$-fold complete graph on $n$ vertices (i.e., the multigraph on $n$ vertices such that there are $\lambda$ edges between every pair of vertices). In this paper, we prove that for $n\ge 2$ $$\begin{array}{ccc}\hfill \mathrm{s}\left(\lambda K_n\right)& =\left\}\begin{array}{ccc}\frac{1}{2}\lambda n\hfill & \text{if}\lambda \text{is}\text{even},\frac{1}{2}(\lambda +1)n-1\hfill & \text{if}\lambda \text{is}\text{odd,}\end{array}\right.\mathrm{s}a\left(\lambda K_n\right)\hfill & \hfill =\left\}\begin{array}{ccc}\lceil \frac{1}{2}\lambda n\rceil \hfill & \text{if}\lambda \text{is}\text{odd},n=2,3\text{or}\lambda \text{is}\text{even},\lceil \frac{1}{2}\lambda n\rceil +1\hfill & \text{if}\lambda \text{is}\text{odd},n\ge 4.\end{array}\right.\end{array}(1,2)$$

The minimum orders of degree-continuous graphs with prescribed degree sets were investigated by Gimbel and Zhang, Czechoslovak Math. J. 51 (126) (2001), 163–171. The minimum orders were not completely determined in some cases. In this note, the exact values of the minimum orders for these cases are obtained by giving improved upper bounds.

Let $P_k$ denote a path with $k$ edges and $łK_{n,n}$ denote the $ł$-fold complete bipartite graph with both parts of size $n$. In this paper, we obtain the necessary and sufficient conditions for $łK_{n,n}$ to have a balanced $P_k$-decomposition. We also obtain the directed version of this result.

In this paper we show that in a tree with vertex weights the vertices with the second smallest status and those with the second smallest branch-weight are the same.