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

山东大学学报（理学版） ›› 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)

1404

被引次数

7

摘要： 设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]. 《山东大学学报(理学版)》, 2026, 61(5): 18-26.
[2] 张鲁宁,王景升. 基于自适应残差动态融合图注意力网络的交通速度预测[J]. 《山东大学学报(理学版)》, 2026, 61(5): 90-101.
[3] 白月蓉,魏宗田,王德莉. 基于多火源燃烧连通度的网络抗毁性分析[J]. 《山东大学学报(理学版)》, 2026, 61(4): 102-108.
[4] 王智玄,庞继芳,王智强,宋鹏,李茹. 融合长短期兴趣的属性增强临时群组推荐算法[J]. 《山东大学学报(理学版)》, 2026, 61(3): 54-65.
[5] 杨滨,孙建楠,曹恩国,李子川,周志立. 基于显著性特征的海报设计侵权检测分析[J]. 《山东大学学报(理学版)》, 2026, 61(3): 11-19.
[6] 姚勋祥,刘培培,徐英城,范清兰,包芳勋,张云峰. 基于多重分形优化的图像超分辨率重建[J]. 《山东大学学报(理学版)》, 2026, 61(3): 96-110.
[7] 王军涛,黄强. 基于一般重叠函数的模糊数学形态学边缘检测方法[J]. 《山东大学学报(理学版)》, 2026, 61(1): 36-48.
[8] 仲尚,马丽,刘文哲,李雨豪. 融合多尺度注意力机制和改进特征融合的轻量化水面小目标检测模型[J]. 《山东大学学报(理学版)》, 2026, 61(1): 15-25.
[9] 王江,李敬文,高鑫,孙亮晶. 若干联图的邻点可约全标号[J]. 《山东大学学报(理学版)》, 2025, 60(8): 57-67.
[10] 王辉,刘蒙蒙. 三圈图的Mostar指标的下界[J]. 《山东大学学报(理学版)》, 2025, 60(8): 68-77.
[11] 武晓军,陈怡丹,郝耀军,宋长伟,何德清. 具有标签流形和动态图约束的多标签特征选择[J]. 《山东大学学报(理学版)》, 2025, 60(7): 69-83.
[12] 吴辛尧,徐计. 基于图互信息池化的分层图表示学习[J]. 《山东大学学报(理学版)》, 2025, 60(7): 84-93.
[13] 钱文彬,彭嘉豪,蔡星星. 基于邻域粒度与三支决策的知识表示学习方法[J]. 《山东大学学报(理学版)》, 2025, 60(7): 94-103.
[14] 任艳栏,谢云丽. 丛代数换位图具有非离开面性的G -系统证明[J]. 《山东大学学报(理学版)》, 2025, 60(5): 79-86.
[15] 梁娟,张晋珠,崔亮. 具有交叉扩散的植被模型的稀疏最优控制[J]. 《山东大学学报(理学版)》, 2025, 60(4): 29-39.
Viewed
Full text


Abstract

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