JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (02): 1-4.doi: 10.6040/j.issn.1671-9352.0.2014.282

    Next Articles

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

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

CLC Number: 

  • 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] TANG Buzhou, HU Han. Construction of technology and application of knowledge graph in power safety [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(5): 18-26.
[2] ZHANG Luning, WANG Jingsheng. Traffic speed prediction study based on adaptive residual dynamic fusion graph attention network [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(5): 90-101.
[3] BAI Yuerong, WEI Zongtian, WANG Deli. Analysis of network invulnerability based on the multi-fire source burning connectivity [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(4): 102-108.
[4] WANG Zhixuan, PANG Jifang, WANG Zhiqiang, SONG Peng, LI Ru. Attribute enhanced temporary group recommendation algorithm fusing long-and short-term interests [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(3): 54-65.
[5] WANG Hui, LIU Mengmeng. Lower bound of Mostar index with respect to tricyclic graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(8): 68-77.
[6] WANG Jiang, LI Jingwen, GAO Xin, SUN Liangjing. Adjacent vertex reducible total labeling of some joint graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(8): 57-67.
[7] WU Xiaojun, CHEN Yidan, HAO Yaojun, SONG Changwei, HE Deqing. Multi-label feature selection with label manifold and dynamic graph constraints [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(7): 69-83.
[8] WU Xinyao, XU Ji. Hierarchical graph representation learning based on graphical mutual information pooling [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(7): 84-93.
[9] QIAN Wenbin, PENG Jiahao, CAI Xingxing. Knowledge graph representation learning based on neighborhood granularity and three-way decision [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(7): 94-103.
[10] REN Yanlan, XIE Yunli. The non-leaving-face property of exchange graphs of cluster algebras via G -systems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(5): 79-86.
[11] GUO Yaqin, CHEN Xiangen. E-total colorings of complete bipartite graphs K1,n, K2,n and K3,n which are vertex-distinguished by multiple sets [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(2): 24-33.
[12] LIU Zhaozhi, Metrose Metsidik. Linear arboricity of product graphs of 1-degenerate graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(2): 51-62.
[13] LYU Zhen, WEI Zongtian. S-T reconstruction of graph based on connectivity optimization [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(12): 156-160.
[14] BAI Yu, QIANG Huiying, HE Jing. Neighbor sum distinguishing edge coloring of join graphs Cm∨Cn [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(12): 161-166.
[15] Liang GUI,Yao XU,Shizhu HE,Yuanzhe ZHANG,Kang LIU,Jun ZHAO. Factual error detection in knowledge graphs based on dynamic neighbor selection [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(7): 76-84.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd