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)

889

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] 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.
[2] . 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] . Graph model based trustworthy resource scheduling algorithm in cloud environment [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(1): 63-74.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] SU Yang. Reconfigurable design of Galois field multiplication in symmetric cryptography [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(6): 76-83.
[15] 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!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd