| 摘要(英) |
Let G be a graph. The unrestricted path number of G, denoted by
ho(G), is the minimum number of paths needed to cover the edges of G. The arboricity of G, denoted by a(G), is the minimum number of forests needed to decompose the edges of G. A linear forest is a forest in which each component is a path. The linear arboricity of G, denoted by la(G), is the minimum number of linear forests needed to decompose the edges of G. In Chapter 2, we study the linear arboricity and unrestricted path number of regular complete r-partite graphs. Let K_{r imes n} denote the complete r-partite graph such that each part has n$vertices, For rge 2, we obtain
a(K_{r imes n})= la(K_{r imes n})=
ho (K_{r imes n})=lceil frac{(r-1)n+1}{2}
ceil.
In Chapter 3, we study the linear arboricity of complete tripartite graphs. Suppose n_1ge n_2ge n_3, we obtain
la(K_{n_1, n_2, n_3})=n_1+1 if n_1=n_2=n_3, and
la(K_{n_1, n_2, n_3})=lceilfrac{n_1+n_2}{2}
ceil otherwise.
For a graph G and a positive integer k, let G^k denote the graph with V(G^k)=V(G) and E(G^k)={uv : u, vin V(G), u
e v, d_G(u, v)le k} where d_G(u, v) denotes the distance between u and v in G. We call G^k the k-th power of G.
A star forest is a forest in which each component is a star. The star arboricity of a graph G, denoted by sa(G), is the minimum number of star forests needed to decompose the edges of G. In Chapter 4, we study the star arboricity of power of cycles. Suppose that k, n are integers such that 2le kle lfloorfrac{n}{2}
floor-1, we obtain
sa(C_n^k)=k+1 if n=0(mod k+1), and
sa(C_n^k)=k+2 otherwise
In Chapter 5, some problems are proposed for further investigations. |
| 參考文獻 |
[1] H. Ait-Djafter, Linear arboricity for graphs with maximum degree six or seven and edge multiplicity two, Ars. Combinatoria 20 (1985), 5-16.
[2] J. Akiyama, A status on the linear arboricity, Lecture Notes in Computer Science 108 (1981), 38-44.
[3] J. Akiyama and V. Chvatal, A short proof of the linear arboricity for cubic graphs, Bull. Liber. Arts and Sci., NMS 2 (1981), 1-3.
[4] J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs III: cyclic and acyclic invariants, Math. Slovaca 30 (1980), 405-417.
[5] J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs IV: linear arboricity, Networks 11 (1981), 69-72.
[6] J. Akiyama, T. Hamada, The decompositions of line graphs, middle graphs and total graphs of complete graphs into forests, Discrete Math. 26 (1979), 203-208.
[7] J. Akiyama and M. Kano, Path factors of a graph, in Graph Theory and its Applications, Proc. First Colorado Sympo. on Graph Theory (Wiley, New York 1985), 1-21.
[8] I. Algor and N. Alon, The star arboricity of graphs, Discrete Math. 75 (1989), 11-22.
[9] N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988), 311-325.
[10] N. Alon, C. McDiarmid and B. Reed, Star arboricity, Combinatorica 12 (1992), 375-380.
[11] Y. Aoki, The star-arboricity of the complete regular multipartite graphs,
Discrete Math. 81 (1990), 115-122.
[12] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs, Wadsworth, Belmont, CA, (1979).
[13] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, New York (1976).
[14] J. Bosak, Decompositions of Graphs, Kluwer, Dordrecht, Netherlands, 1990.
[15] G. Chartrand, L. Lesniak, Graphs and Digraphs, 2nd Edition, Wadsworth, Belmont, CA, (1986).
[16] Y. Egawa, M. Urabe, T. Fukuda and S. Nagoya, A decomposition of complete bipartite graphs into edge-disjoint subgraphs with star components,
Discrete Math. 58 (1986), 93-95.
[17] H. Enomoto, The linear arboricity of 5-regular graphs, Technical Report,
Dept. of Information Sci., Univ. of Tokyo, 1981.
[18] H. Enomoto and B. Peroche, The linear arboricity of some regular graphs,
J. Graph Theory 8 (1984), 309-324.
[19] H. Enomoto and Y. Usami, The star arboricity of complete bipartite graphs,
Graph Theory, Combinatorics, and Applications 1 (1988), 389-396.
[20] B. Guiduli, Note on incidence coloring and star arboricity of graphs,
Discrete Math. 163 (1997), 275-278.
[21] F. Guldan, The linear arboricity of 10-regular graphs, Math. Slovaca 36 (1986), 225-228.
[22] F. Guldan, Some results on linear arboricity, J. Graph Theory 10 (1986), 505-509.
[23] M. Habib and B. Peroche, Some problems about linear arboricity, Discrete Math. 41 (1982), 219-220.
[24] S. L. Hakimi, J. Mitchem and E. Schmeichel, Star arboricity of graphs, Discrete Math. 149 (1996), 93-98.
[25] F. Harary, Covering and packing in graphs I, Ann. New York Acad. Sci. 175 (1970), 198-215.
[26] F. Harary and A. J. Schwenk, Evolution of the path number of a graph: Covering and packing in graphs II, Graph Theory and Computing, edited by R. C. Read, Acad. Press, NY, (1972), 39-45.
[27] P. Hell, A. Rosa, Graph decompositions, handcuffed prisoners and balanced P-designs, Discrete Math. 2 (1972), 229-252.
[28] A. Kurek, Arboricity and star arboricity of graphs, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (1992), 171-173.
[29] C. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964), 12.
[30] B. Peroche, The path-numbers of some multipartite graphs, Ann. of Discrete Math. 9 (1980), 195-197.
[31] B. Peroche, On partition of graphs into linear forests and dissections.
[32] R. Stanton, D. Cowan and L. James, Some results on path numbers, Proc. Louisiana Conf. Combinatorics, Graph theory and Computing, Baton Rouge (1970), 112-135.
[33] R. Stanton, L. James and D. Cowan, Tripartite path numbers, Graph Theory and Computing (1972), 285-294.
[34] P. Tomasta, Note on linear arboricity, Math. Slovaca 32 (1982), 239-242.
[35] M. Truszczynski, Decomposing graphs into forests of stars, Congr. Numer. 54 (1986), 73-86.
[36] D. B. West, Introduction to Graph Theory, Prentice-Hall (1996).
[37] T. W. Yeh, Linear Arboricities of Complete r-Partite Graphs, Master Thesis, Dept. Applied Math., National Chiao Tung Univ., Hsinchu, Taiwan, June 1997. |
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit