### 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

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
  El-ZAHAR M H. On circuits in graphs[J]. Discrete Mathematics, 1984, 50:227-230.  DIRAC G A. Some theorems on abstract graphs[J]. Proc London Math Soc, 1952, 2(3):69-81.  ORE O. Note on hamiltonian circuits[J]. Amer Math Monthly, 1960, 67:55.  WANG Hong. Proof of the Erdös-Faudree conjecture on quadrilaterals[J]. Graphs and Combinatorics, 2010, 26:833-877.  YAN Jin. Disjoint triangles and quadrilaterals in a graph[J]. Discrete Mathematics, 2008, 308:3930-3937.  JOHANSSON R. On the bipartite case of El-ZAHAR conjecture[J]. Discrete Mathematics, 2000, 191:123-134.  颜谨, 刘桂真. 图中相互独立的4-圈和含4个点的路[J]. 数学物理学报, 2003, 23(6):711-718.
  YE Xiao-ming, CHEN Xing-shu, YANG Li, WANG Wen-xian, ZHU Yi, SHAO Guo-lin, LIANG Gang. Anomaly detection model of host group based on graph-evolution events [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(9): 1-11.  . Vertex-distinguishing IE-total coloring and general-total coloring of K1,3,p and K1,4,p [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 53-60.  LIU Xiao-hua, MA Hai-cheng. Order of matching energy and Hosoya index of Q-shape graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 61-65.  CUI Zhao-yang, SUN Jia-qi, XU Song-yan, JIANG Xin. A secure clustering algorithm of Ad Hoc network for colony UAVs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(7): 51-59.  GAO Rui-mei, CHU Ying. Freeness of arrangements between the Weyl arrangements of types An-1 and Bn [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 70-75.  FANG Qi-ming, ZHANG Li. k-frugal list coloring of planar graphs without 4 and 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 35-41.  LI Mei-lian, DENG Qing-ying. Maple calculation of the transition polynomial of plane graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 27-34.  KANG Hai-yan, HUANG Yu-xuan, CHEN Chu-qiao. Enhancing privacy for geographic information based on video analysis [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 19-29.  . Graph model based trustworthy resource scheduling algorithm in cloud environment [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 63-74.  DAI Hong-xiu, WANG Nan, AIMAIER·Aikebaijiang, LIN Meng. Preparation of the GO/PPy/Pb3O4 modified electrode for electrochemical sensing application [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(9): 98-102.  WANG Xiao-li, WANG Hui-juan, LIU Bin. Total coloring of planar graphs with maximum degree seven [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 100-106.  PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing index of a kind of sparse graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 94-99.  ZHANG Cong, PEI Jia-huan, HUANG Kai-yu, HUANG De-gen, YIN Zhang-zhi. Semantic graph optimization algorithm based chinesemicroblog opinion summarization [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(7): 59-65.  SU Yang. Reconfigurable design of Galois field multiplication in symmetric cryptography [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(6): 76-83.  CHEN Xiang-en, MIAO Ting-ting, WANG Zhi-wen. Vertex-distinguishing I-total colorings of the join of two paths [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 30-33.
Viewed
Full text

Abstract

Cited

Shared
Discussed
 No Suggested Reading articles found!