|
|
几类重图的阶为4的图对分解
|
Abstract:
对于某个整数t ≥ 4，如果G和H是Kt的两个边不交的、非同构的、无孤立点的生成子图且满足E(G)∪E(H)=E(Kt)，那么称(G,H)是阶为t的图对。Abueida和Daven得到了Pm,Pn，Pm,Cn，Pm,Kn，Cm,Cn，Cm,Kn，Km,Kn的阶为4的图对分解存在的充要条件。作为其结果的推广，本文给出λ(Pm,Pn)，λ(Pm,Cn)，λ(Pm,Kn)，λ(Cm,Cn)，λ(Cm,Kn)，λ(Km,Kn)，λL(Kn)的阶为4的图对分解存在的充要条件。
For some integer t ≥ 4, if G and H are edge disjoint, non-isomorphic and non-isolated vertices span-ning subgraphs of Kt such that E(G)∪E(H)=E(Kt) , then we say that is a graph-pair of order t. Abueida and Daven have introduced the necessary and sufficient conditions of the exist-ence of multidecompositions of Pm,Pn，Pm,Cn，Pm,Kn，Cm,Cn，Cm,Kn，Km,Kn for graph- pair of order 4. As a generalization, we obtain the necessary and sufficient conditions of the exist-ence of multidecompositions of λ(Pm,Pn)，λ(Pm,Cn)，λ(Pm,Kn)，λ(Cm,Cn)，λ(Cm,Kn)，λ(Km,Kn)，λL(Kn) for graph-pair of order 4.
| [1] | Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. The Macmillan Press Ltd., London.
https://doi.org/10.1007/978-1-349-03521-2 |
| [2] | 邦迪, 默蒂. 图论及其应用[M]. 北京: 科学出版社, 1984. |
| [3] | Cox, B.A. (1995) The Complete Spectrum of 6-Cycle Systems of L(Kn). Journal of Combinatorial Designs, 3, 353-362.
https://doi.org/10.1002/jcd.3180030506 |
| [4] | Cox, B.A. and Rodger, C.A. (1996) Cycle Systems of the Line Graph of the Complete Graph. Journal of Graph Theory, 21, 173-182. https://doi.org/10.1002/(SICI)1097-0118(199602)21:2<173::AID-JGT6>3.0.CO;2-O |
| [5] | Ganesamurthy, S. and Paulraja, P.A. (2019) C5-Decomposition of the λ-Fold Line Graph of the Complete Graph. Discrete Mathematics, 342, 2726-2732. https://doi.org/10.1016/j.disc.2019.06.004 |
| [6] | Shyu, T.W. (2010) Decomposition of Complete Graphs into Paths and Stars. Discrete Mathematics, 310, 2164-2169.
https://doi.org/10.1016/j.disc.2010.04.009 |
| [7] | Jeevadoss, S. and Muthusamy, A. (2014) Decomposition of Com-plete Bipartite Graphs into Paths and Cycles. Discrete Mathematics, 331, 98-108. https://doi.org/10.1016/j.disc.2014.05.009 |
| [8] | Shyu, T.W. (2013) Decomposition of Complete Bipartite Graphs into Paths and Stars with Same Number of Edges. Discrete Mathematics, 313, 865-871. https://doi.org/10.1016/j.disc.2012.12.020 |
| [9] | Abueida, A.A. and Daven, M. (2003) Multidesigns for Graph-Pairs of Order 4 and 5. Graphs and Combinatorics, 19, 433-447. https://doi.org/10.1007/s00373-003-0530-3 |
| [10] | 刘萍. 4和5阶Kn(t)的图对分解[J]. 徐州师范大学学报: 自然科学版, 2004, 22(4): 10-14. |
| [11] | Abueida, A.A., Daven, M. and Roblee, K.J. (2005) Multidesigns of the λ-Fold Complete Graph for Graph-Pairs of Orders 4 and 5. Australasian Journal of Combinatorics, 32, 125-136. |
| [12] | Gao, Y. and Roberts, D. (2016) Multidecomposition and Multipacking of Complete Graph into Graph Pair of Order 6. |
| [13] | Abueida, A.A. and Daven, M. (2013) Multidecompositions of Several Graph Products. Graphs and Combinatorics, 29, 315-326. https://doi.org/10.1007/s00373-011-1127-x |
| [14] | Bryant, D., Horsley, D., Maenhaut, B. and Smith, B.R. (2011) Cycle Decompositions of Complete Multigraphs. Journal of Combinatorial Designs, 19, 42-69. https://doi.org/10.1002/jcd.20263 |
| [15] | Colby, M. and Rodger, C.A. (1993) Cycle Decompositions of the Line Graph of Kn. Journal of Combinatorial Theory, Series A, 62, 158-161. https://doi.org/10.1016/0097-3165(93)90078-M |
