应用数学进展  >> Vol. 6 No. 2 (March 2017)

图中具有指定性质的不交子图
Disjoint Subgraphs with Specified Properties in Graphs

DOI: 10.12677/AAM.2017.62016, PDF, HTML, XML, 下载: 892  浏览: 4,719  国家自然科学基金支持

作者: 王怡华, 衣晓宁:山东大学数学学院,山东 济南;李硕:昌吉学院数学系,新疆 昌吉

关键词: 点不交4-团弦圈Vertex-Disjoint 4-Cliques Chordal Cycle

摘要: G是一个顶点数为n的简单图,满足n≥4kk是任意正整数。假设,则图G可划分成k-1个点不交的4-团和一个弦圈,使得弦圈上点的度大于等于3或4。
Abstract: Let G be a graph of order n with n≥4k, where k is a positive integer. Suppose that , then the partition of G can be k-1 vertex disjoint 4-cliques and a chordal cycle, where the degree of vertexes in this chordal cycle is equal or greater than 3 or 4.

文章引用: 王怡华, 李硕, 衣晓宁. 图中具有指定性质的不交子图[J]. 应用数学进展, 2017, 6(2): 139-145. https://doi.org/10.12677/AAM.2017.62016

参考文献

[1] Erdös, P. (1967) Extremal Problems in Graph Theory. In: Harary, F., Ed., A Seminar in Graph Theory, Holt, Rinehart and Winston, 54-56.
[2] Bollobás, B. (2004) Extremal Graph Theory. Courier Corporation.
[3] Corradi, K. and Hajnal, A. (1963) On the Maximal Number of Independent Circuits in a Graph. Acta Mathematica Hungarica, 14, 423-439.
https://doi.org/10.1007/BF01895727
[4] Wang, H. Covering a Graph with Cycles of Lengths at Least 4.
[5] Ore, O. (1960) Note on Hamilton Circuits. The American Mathematical Monthly, 67, 55.
https://doi.org/10.2307/2308928
[6] Chartrand, G., Lesniak, L. and Zhang, P. (2010) Graphs & Digraphs. CRC Press.