Star number and star arboricity of a complete multigraph

Chiang Lin; Tay-Woei Shyu

Czechoslovak Mathematical Journal (2006)

  • Volume: 56, Issue: 3, page 961-967
  • ISSN: 0011-4642

Abstract

top
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 s a ( 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 ( λ K n ) = 1 2 λ n if λ is even , 1 2 ( λ + 1 ) n - 1 if λ is odd, s a ( λ K n ) = ⌈ 1 2 λ n ⌉ if λ is odd , n = 2 , 3 or λ is even , ⌈ 1 2 λ n ⌉ + 1 if λ is odd , n ≥ 4 . ( 1 , 2 )

How to cite

top

Lin, Chiang, and Shyu, Tay-Woei. "Star number and star arboricity of a complete multigraph." Czechoslovak Mathematical Journal 56.3 (2006): 961-967. <http://eudml.org/doc/31082>.

@article{Lin2006,
abstract = {Let $G$ be a multigraph. The star number $\{\mathrm \{s\}\}(G)$ of $G$ is the minimum number of stars needed to decompose the edges of $G$. The star arboricity $\{\mathrm \{s\}a\}(G)$ 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\{aligned\} \{\mathrm \{s\}\}(\lambda K\_n)&= \left\rbrace \begin\{array\}\{ll\}\frac\{1\}\{2\}\lambda n&\text\{if\}\ \lambda \ \text\{is even\}, \frac\{1\}\{2\}(\lambda +1)n-1&\text\{if\}\ \lambda \ \text\{is odd,\} \end\{array\}\right. \{\vspace\{2.0pt\}\} \{\mathrm \{s\}a\}(\lambda K\_n)&= \left\rbrace \begin\{array\}\{ll\}\lceil \frac\{1\}\{2\}\lambda n \rceil &\text\{if\}\ \lambda \ \text\{is odd\},\ n = 2, 3 \ \text\{or\}\ \lambda \ \text\{is even\}, \lceil \frac\{1\}\{2\}\lambda n \rceil +1 &\text\{if\}\ \lambda \ \text\{is odd\},\ n\ge 4. \end\{array\}\right. \end\{aligned\} \qquad \mathrm \{(1,2)\}\]},
author = {Lin, Chiang, Shyu, Tay-Woei},
journal = {Czechoslovak Mathematical Journal},
keywords = {decomposition; star arboricity; star forest; complete multigraph; decomposition; star arboricity; star forest; complete multigraph},
language = {eng},
number = {3},
pages = {961-967},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Star number and star arboricity of a complete multigraph},
url = {http://eudml.org/doc/31082},
volume = {56},
year = {2006},
}

TY - JOUR
AU - Lin, Chiang
AU - Shyu, Tay-Woei
TI - Star number and star arboricity of a complete multigraph
JO - Czechoslovak Mathematical Journal
PY - 2006
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 56
IS - 3
SP - 961
EP - 967
AB - Let $G$ be a multigraph. The star number ${\mathrm {s}}(G)$ of $G$ is the minimum number of stars needed to decompose the edges of $G$. The star arboricity ${\mathrm {s}a}(G)$ 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{aligned} {\mathrm {s}}(\lambda K_n)&= \left\rbrace \begin{array}{ll}\frac{1}{2}\lambda n&\text{if}\ \lambda \ \text{is even}, \frac{1}{2}(\lambda +1)n-1&\text{if}\ \lambda \ \text{is odd,} \end{array}\right. {\vspace{2.0pt}} {\mathrm {s}a}(\lambda K_n)&= \left\rbrace \begin{array}{ll}\lceil \frac{1}{2}\lambda n \rceil &\text{if}\ \lambda \ \text{is odd},\ n = 2, 3 \ \text{or}\ \lambda \ \text{is even}, \lceil \frac{1}{2}\lambda n \rceil +1 &\text{if}\ \lambda \ \text{is odd},\ n\ge 4. \end{array}\right. \end{aligned} \qquad \mathrm {(1,2)}\]
LA - eng
KW - decomposition; star arboricity; star forest; complete multigraph; decomposition; star arboricity; star forest; complete multigraph
UR - http://eudml.org/doc/31082
ER -

References

top
  1. Path factors of a graph, In: Graphs and Applications. Proceedings of the first Cororado Symposium on Graph Theory, F. Harary, J.  Maybee (eds.), , , 1982, pp. 1–21. (1982) MR0778395
  2. 10.1016/0012-365X(89)90073-3, Discrete Math. 75 (1989), 11–22. (1989) MR1001381DOI10.1016/0012-365X(89)90073-3
  3. 10.1016/0012-365X(90)90142-5, Discrete Math. 81 (1990), 115–122. (1990) Zbl0737.05038MR1054968DOI10.1016/0012-365X(90)90142-5
  4. Extremal Graph Theory, Academic Press, New York, 1978. (1978) MR0506522
  5. Graph Theory with Applications, North Holland, New York, 1976. (1976) MR0411988
  6. 10.1016/0012-365X(86)90190-1, Discrete Math. 58 (1986), 93–95. (1986) MR0820842DOI10.1016/0012-365X(86)90190-1
  7. The star arboricity of complete bipartite graphs, Graph Theory, Combinatorics and Applications 1 (1988), 389–396. (1988) MR1170792
  8. On independence numbers of the Cartesian product of graphs, ARS Combin. 43 (1996), 149–157. (1996) MR1415983
  9. 10.1016/0012-365X(94)00313-8, Discrete Math. 149 (1996), 93–98. (1996) MR1375101DOI10.1016/0012-365X(94)00313-8
  10. Independence in direct-product graphs, ARS Combin. 50 (1998), 53–63. (1998) MR1670588
  11. Some decomposition invariants of crowns, ARS Combin. 66 (2003), 33–48. (2003) MR1961473
  12. Isomorphic star decomposition of multicrowns and the power of cycles, ARS Combin. 53 (1999), 249–256. (1999) MR1724509
  13. 10.1137/S0895480198342838, SIAM J.  Discrete Math. 12 (1999), 491–499. (1999) MR1720404DOI10.1137/S0895480198342838
  14. Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964), 12. (1964) Zbl0119.38805MR0161333
  15. Decomposing graphs into forests of stars, Congr. Numer. 54 (1986), 73–86. (1986) Zbl0646.05022MR0885263

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.