您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2015, Vol. 50 ›› Issue (02): 1-4.doi: 10.6040/j.issn.1671-9352.0.2014.282

• 论文 •    下一篇

图中相互独立的4-圈和8-圈

张绍华1, 颜谨1, 李硕2   

  1. 1. 山东大学数学学院, 山东 济南 250100;
    2. 昌吉学院数学系, 新疆 昌吉 831100
  • 收稿日期:2014-06-20 修回日期:2014-11-11 出版日期:2015-02-20 发布日期:2015-01-27
  • 作者简介:张绍华(1991-),女,硕士研究生,研究方向为图中点不交的圈问题. E-mail:zhangsh0629@163.com;颜谨(1967-),女,博士,教授,研究方向为图论与组合优化近似算法. E-mail:yanj@sdu.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(11271230);山东省自然科学基金资助项目(ZR2012AM023)

Disjoint 4-cycles and 8-cycles in graphs

ZHANG Shao-hua1, YAN Jin1, LI Shuo2   

  1. 1. School of Mathematics, Shandong University, Jinan 250100, Shandong, China;
    2. Department of Mathematics, Changji University, Changji 831100, Xinjiang, China
  • Received:2014-06-20 Revised:2014-11-11 Online:2015-02-20 Published:2015-01-27

PDF (PC)

886

摘要： 设G是一个含有4k个顶点的简单图,若δ(G)≥2k,则G包含k-2个4-圈和1个8-圈,使得这k-1个圈是相互独立的.在此基础上证明了:若G是一个含有4k(k≥4)个顶点的图,δ(G)≥2k,则下列两种情况中至少有一种成立:(1) G包含k-3个4-圈和1个12-圈; (2) G包含k-4个4-圈和2个8-圈.且不论哪一种情况成立,这k-2个圈点不交.

关键词: 图, 点不交, 4-圈, 8-圈

Abstract: Let G be a graph of order 4k(k≥4) and δ (G)≥2k. Then G contains k-2 cycles of length 4 and a cycle of length 8 such that these k-1 cycles are disjoint. As an application, we prove that if G is a graph of order 4k and δ(G)≥2k, then at least one of the following two results is true: (1) G contains k-3 cycles of length 4 and a cycle of length 12; (2) G contains k-4 cycles of length 4 and two cycles of length 8, where the cycles are disjoint.

Key words: graph, vertex disjoint, 4-cycle, 8-cycle

中图分类号: 

  • O157
[1] El-ZAHAR M H. On circuits in graphs[J]. Discrete Mathematics, 1984, 50:227-230.
[2] DIRAC G A. Some theorems on abstract graphs[J]. Proc London Math Soc, 1952, 2(3):69-81.
[3] ORE O. Note on hamiltonian circuits[J]. Amer Math Monthly, 1960, 67:55.
[4] WANG Hong. Proof of the Erdös-Faudree conjecture on quadrilaterals[J]. Graphs and Combinatorics, 2010, 26:833-877.
[5] YAN Jin. Disjoint triangles and quadrilaterals in a graph[J]. Discrete Mathematics, 2008, 308:3930-3937.
[6] JOHANSSON R. On the bipartite case of El-ZAHAR conjecture[J]. Discrete Mathematics, 2000, 191:123-134.
[7] 颜谨, 刘桂真. 图中相互独立的4-圈和含4个点的路[J]. 数学物理学报, 2003, 23(6):711-718.
[1] 叶晓鸣,陈兴蜀,杨力,王文贤,朱毅,邵国林,梁刚. 基于图演化事件的主机群异常检测模型[J]. 山东大学学报（理学版）, 2018, 53(9): 1-11.
[2] 寇艳芳,陈祥恩,王治文. K1,3,p和 K1,4,p的点可区别的IE-全染色及一般全染色[J]. 山东大学学报（理学版）, 2018, 53(8): 53-60.
[3] 刘小花,马海成. Q形图的匹配能序及Hosoya指标排序[J]. 山东大学学报（理学版）, 2018, 53(8): 61-65.
[4] 刘华,叶勇,魏玉梅,杨鹏,马明,冶建华,马娅磊. 一类离散宿主-寄生物模型动态研究[J]. 山东大学学报（理学版）, 2018, 53(7): 30-38.
[5] 高瑞梅,初颖. Weyl构形An-1和Bn之间的构形的自由性[J]. 山东大学学报（理学版）, 2018, 53(6): 70-75.
[6] 朱林. A4型箭图的可分单态射表示和RSS等价[J]. 山东大学学报（理学版）, 2018, 53(2): 1-8.
[7] 李美莲,邓青英. 平图的transition多项式的Maple计算[J]. 山东大学学报（理学版）, 2018, 53(10): 27-34.
[8] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报（理学版）, 2018, 53(10): 35-41.
[9] 孙泽锐,王继军,李国祥,夏国恩. 基于插值图像的可逆信息隐藏算法[J]. 山东大学学报（理学版）, 2018, 53(1): 46-52.
[10] 齐平, 王福成, 王必晴. 一种基于图模型的可信云资源调度算法[J]. 山东大学学报（理学版）, 2018, 53(1): 63-74.
[11] 王凯,洪宇,邱盈盈,王剑,姚建民,周国栋. 一种查询意图边界检测方法研究[J]. 山东大学学报（理学版）, 2017, 52(9): 13-18.
[12] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[13] 潘文华,徐常青. 一类稀疏图的邻和可区别边色数[J]. 山东大学学报（理学版）, 2017, 52(8): 94-99.
[14] 王霞,张茜,李俊余,刘庆凤. 基于粗糙集的三元概念分析[J]. 山东大学学报（理学版）, 2017, 52(7): 37-43.
[15] 张聪,裴家欢,黄锴宇,黄德根,殷章志. 基于语义图优化算法的中文微博观点摘要研究[J]. 山东大学学报（理学版）, 2017, 52(7): 59-65.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发