Please wait a minute...
北京大学期刊网 | 作者  审稿人  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 2018, Vol. 47(3): 348-362
研究论文
标准多重图中点不交的重边四边形
Vertex-disjoint Multiquadrilaterals in Multigraphs

石慧苓, 高云澍*
SHI Huiling, GAO Yunshu

宁夏大学数学统计学院, 银川, 宁夏, 750021
School of Mathematics and Statistics, Ningxia University, Yinchuan, Ningxia, 750021, P. R. China

收稿日期: 2016-08-30
出版日期: 2018-06-01
2018, Vol. 47(3): 348-362
DOI: 10.11845/sxjz.2016106b


PDF
[418 KB]
10
下载
55
浏览

引用导出
E-mail这篇文章
E-mail提醒
RSS订阅

摘要 圈长为 $4$ 的图叫做四边形,任意两个顶点之间边数至多为 $2$ 的多重图叫做标准多重图,圈上的四条边都是重边的四边形叫重边四边形. 本文证明了:如果 $M$ 是阶数为 $4k$ 的标准多重图, $k$ 是正整数,且 $M$ 的最小度至少为 $6k-2$, 则除了三个特例之外, $M$ 包含 $k-1$个重边四边形和一个有三条重边的四边形, 使得这$k$个四边形彼此点不交.
关键词 重边四边形标准多重图最小度    
Abstract:A cycle of length 4 is called a quadrilateral and a multigraph is called standard if every edge in it has multiplicity at most 2. A quadrilateral with four multiedges is called heavy-quadrilateral. We prove that if the minimum degree of $M$ is at least $6k-2$, then $M$ contains $k$ vertex-disjoint quadrilaterals, such that $k-1$ of them are heavy-quadrilaterals and the remaining one is a quadrilateral with three multiedges, with only three exceptions.
Key wordsmultiquadrilateral    standard multigraph    mininum degree
PACS:  O157.5  
基金资助:国家自然科学基金(No. 11561054).
通讯作者: E-mail: $*$ gysh2004@163.com   
[1] Bang-Jensen, J. and Gutin, G.Z., Digraphs: Theory, Algorithms and Applications, London: Springer-Verlag, 2008.
[2] Czygrinow, A., Kierstead, H.A. and Molla, T., On directed versions of the Corrádi-Hajnal corollary, European J. Combin., 2014, 42: 1-14.
[3] Erdos, P., Some recent combinatorial problems, Technical Report, Bielefeld: University of Bielefeld, 1990.
[4] Gao, Y.S., Zou, Q.S. and Ma, L.Y., Vertex-disjoint quadrilaterals in
multigraphs, Graphs Combin., 2017, 33(4): 901-912.
[5] Randerath, B., Schiermeyer, I. and Wang, H., On quadriaterals in a graph, Discrete Math., 1999, 203(1/2/3): 229-237.
[6] Wang, H., Proof of the Erdos-Faudree conjecture on quadrilaterals, Graphs Combin., 2010, 26(6): 833-877.
[7] Zhang, D.H. and Wang, H., Disjoint directed quadrilaterals in a directed graph, J. Graph Theory, 2005, 50(2): 91-104.
[1] 宋慧敏,刘桂真. 边覆盖临界图的一些性质[J]. 数学进展, 2004, 33(1): 96-102.
Viewed
Full text


Abstract

Cited

  Discussed   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .