几类重图的阶为4的图对分解
Multidecompositions of Several Multigraphs for Graph-Pair of Order 4
DOI: 10.12677/AAM.2023.124201, PDF,   
作者: 赵依凡*, 杨卫华：太原理工大学数学学院，山西 太原
关键词: 分解；图对；重图；Multidecompositon； Graph-Pair； Multigraph
摘要: 对于某个整数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的图对分解存在的充要条件。
Abstract: 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.
文章引用：赵依凡, 杨卫华. 几类重图的阶为4的图对分解[J]. 应用数学进展, 2023, 12(4): 1964-1970. https://doi.org/10.12677/AAM.2023.124201

参考文献

[1] Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. The Macmillan Press Ltd., London. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[5] Ganesamurthy, S. and Paulraja, P.A. (2019) C5-Decomposition of the λ-Fold Line Graph of the Complete Graph. Discrete Mathematics, 342, 2726-2732. [Google Scholar] [CrossRef] 
[6] Shyu, T.W. (2010) Decomposition of Complete Graphs into Paths and Stars. Discrete Mathematics, 310, 2164-2169. [Google Scholar] [CrossRef] 
[7] Jeevadoss, S. and Muthusamy, A. (2014) Decomposition of Com-plete Bipartite Graphs into Paths and Cycles. Discrete Mathematics, 331, 98-108. [Google Scholar] [CrossRef] 
[8] Shyu, T.W. (2013) Decomposition of Complete Bipartite Graphs into Paths and Stars with Same Number of Edges. Discrete Mathematics, 313, 865-871. [Google Scholar] [CrossRef] 
[9] Abueida, A.A. and Daven, M. (2003) Multidesigns for Graph-Pairs of Order 4 and 5. Graphs and Combinatorics, 19, 433-447. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[14] Bryant, D., Horsley, D., Maenhaut, B. and Smith, B.R. (2011) Cycle Decompositions of Complete Multigraphs. Journal of Combinatorial Designs, 19, 42-69. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 

为你推荐