C4p-frame of complete multipartite multigraphs

被引:0
作者
V. Chitra
A. Shanmuga Vadivu
A. Muthusamy
机构
[1] Periyar University,Department of Mathematics
来源
Aequationes mathematicae | 2013年 / 85卷
关键词
05C70; 05C51; 05B30; Decomposition; factorization; frame;
D O I
暂无
中图分类号
学科分类号
摘要
For two graphs G and H their wreath product\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${G \otimes H}$$\end{document} has the vertex set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${V(G) \times V(H)}$$\end{document} in which two vertices (g1, h1) and (g2, h2) are adjacent whenever \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${g_{1}g_{2} \in E(G)}$$\end{document} or g1 =  g2 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${h_{1}h_{2} \in E(H)}$$\end{document} . Clearly \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${K_{m} \otimes I_{n}}$$\end{document} , where In is an independent set on n vertices, is isomorphic to the complete m-partite graph in which each partite set has exactly n vertices. A subgraph of the complete multipartite graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${K_m \otimes I_n}$$\end{document} containing vertices of all but one partite set is called partial factor. An H-frame of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${K_m \otimes I_n}$$\end{document} is a decomposition of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${K_m \otimes I_n}$$\end{document} into partial factors such that each component of it is isomorphic to H. In this paper, we investigate C2k-frames of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${(K_m \otimes I_n)(\lambda)}$$\end{document} , and give some necessary or sufficient conditions for such a frame to exist. In particular, we give a complete solution for the existence of a C4p-frame of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${(K_m \otimes I_n)(\lambda)}$$\end{document} , where p is a prime, as follows: For an integer m ≥  3 and a prime p, there exists a C4p-frame of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${(K_m \otimes I_n)(\lambda)}$$\end{document} if and only if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${(m-1)n \equiv 0 ({\rm {mod}} {4p})}$$\end{document} and at least one of m, n must be even, when λ is odd.
引用
收藏
页码:563 / 579
页数:16
相关论文
共 39 条
[1]  
Alspach B.R(2001)Cycle decompositions of J. Combin. Theory Ser. B 81 77-99
[2]  
Gavlas H.J.(2010) and Discret. Math. 310 241-254
[3]  
Billington E.J.(2009)− Discret. Math. 309 3061-3073
[4]  
Cavenagh N.J.(1989)Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts Graphs Combin. 5 213-221
[5]  
Smith B.R.(2011)Path and cycle decompositions of complete equipartite graphs: four parts Discret. Math. 311 2220-2232
[6]  
Billington E.J.(1998)Near 2-factorizations of 2 Australas. J. Combin. 18 193-200
[7]  
Cavenagh N.J.(2000): cycles of even length Graphs Combin. 16 49-65
[8]  
Smith B.R.(1988)On the existence of cycle frames and almost resolvable cycle systems Graphs Combin. 4 111-113
[9]  
Burling J.(1988)Decompositions of complete tripartite graphs into J. Combin. Theory Ser. A 49 218-232
[10]  
Heinrich K.(1989)-cycles J. Graph Theory 13 417-426