4-Cycle Decompositions of Graphs

Author(s)
Teresa Sousa

ABSTRACT

In this paper we consider the problem of finding the smallest number such that any graph G of order n admits a decomposition into edge disjoint copies of C_{4} and single edges with at most elements. We solve this problem for *n* sufficiently large.

In this paper we consider the problem of finding the smallest number such that any graph G of order n admits a decomposition into edge disjoint copies of C

Cite this paper

T. Sousa, "4-Cycle Decompositions of Graphs,"*Open Journal of Discrete Mathematics*, Vol. 2 No. 4, 2012, pp. 125-130. doi: 10.4236/ojdm.2012.24024.

T. Sousa, "4-Cycle Decompositions of Graphs,"

References

[1] B. Bollobás, “Modern Graph Theory,” Springer-Verlag, New York, 1998. doi:10.1007/978-1-4612-0619-4

[2] P. Erd?s, A. W. Goodman and L. Pósa, “The Representation of a Graph by Set Intersections,” Canadian Journal of Mathematics, Vol. 18, No. 1, 1966, pp. 106-112. doi:10.4153/CJM-1966-014-3

[3] B. Bollobás, “On Complete Subgraphs of Different Orders,” Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 79, No. 1, 1976, pp. 19-24. doi:10.1017/S0305004100052063

[4] O. Pikhurko and T. Sousa, “Minimum H-Decompositions of Graphs,” Journal of Combinatorial Theory Series B, Vol. 97, No. 6, 2007, pp. 1041-1055. doi:10.1016/j.jctb.2007.03.002

[5] T. Sousa, “Decompositions of Graphs into a Given Clique-Extension,” ARS. Combinatoria, Vol. 100, 2011, pp. 465-472.

[6] T. Sousa, “Decompositions of Graphs into 5-Cycles and Other Small Graphs,” Electronic Journal of Combinatorics, Vol. 12, 2005, 7pp.

[7] T. Sousa, “Decompositions of Graphs into Cycles of Length Seven and Single Edges,” ARS. Combinatoria, to appear.

[8] L. ?zkahya and Y. Person, “Minimum H-Decompositions of Graphs: Edge-Critical Case,” Journal of Combinatorial Theory Series B, Vol. 102, No. 102, 2012, pp. 715-725. doi:10.1016/j.jctb.2011.10.004

[9] P. Allen, J. B?ttcher and Y. Person, “An Improved Error Term for Minimum H-Decompositions of Graphs,” arXiv: 1109.2571v1, 2011.

[10] P. Erd?s and T. Gallai, “Graphs with Prescribed Degree of Vertices,” Matematikai Lapok, Vol. 11, 1960, pp. 264-274.

[11] N. Alon, Y. Caro and R. Yuster, “Packing and Covering Dense Graphs,” Journal of Combinatorial Designs, Vol. 6, No. 6, 1998, pp. 451-472. doi:10.1002/(SICI)1520-6610(1998)6:6<451::AID-JCD6>3.0.CO;2-E

[12] T. Gustavsson, “Decompositions of Large Graphs and Digraphs with High Minimum Degree,” Ph.D. Thesis, University of Stockholm, Stockholm, 1991.

[1] B. Bollobás, “Modern Graph Theory,” Springer-Verlag, New York, 1998. doi:10.1007/978-1-4612-0619-4

[2] P. Erd?s, A. W. Goodman and L. Pósa, “The Representation of a Graph by Set Intersections,” Canadian Journal of Mathematics, Vol. 18, No. 1, 1966, pp. 106-112. doi:10.4153/CJM-1966-014-3

[3] B. Bollobás, “On Complete Subgraphs of Different Orders,” Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 79, No. 1, 1976, pp. 19-24. doi:10.1017/S0305004100052063

[4] O. Pikhurko and T. Sousa, “Minimum H-Decompositions of Graphs,” Journal of Combinatorial Theory Series B, Vol. 97, No. 6, 2007, pp. 1041-1055. doi:10.1016/j.jctb.2007.03.002

[5] T. Sousa, “Decompositions of Graphs into a Given Clique-Extension,” ARS. Combinatoria, Vol. 100, 2011, pp. 465-472.

[6] T. Sousa, “Decompositions of Graphs into 5-Cycles and Other Small Graphs,” Electronic Journal of Combinatorics, Vol. 12, 2005, 7pp.

[7] T. Sousa, “Decompositions of Graphs into Cycles of Length Seven and Single Edges,” ARS. Combinatoria, to appear.

[8] L. ?zkahya and Y. Person, “Minimum H-Decompositions of Graphs: Edge-Critical Case,” Journal of Combinatorial Theory Series B, Vol. 102, No. 102, 2012, pp. 715-725. doi:10.1016/j.jctb.2011.10.004

[9] P. Allen, J. B?ttcher and Y. Person, “An Improved Error Term for Minimum H-Decompositions of Graphs,” arXiv: 1109.2571v1, 2011.

[10] P. Erd?s and T. Gallai, “Graphs with Prescribed Degree of Vertices,” Matematikai Lapok, Vol. 11, 1960, pp. 264-274.

[11] N. Alon, Y. Caro and R. Yuster, “Packing and Covering Dense Graphs,” Journal of Combinatorial Designs, Vol. 6, No. 6, 1998, pp. 451-472. doi:10.1002/(SICI)1520-6610(1998)6:6<451::AID-JCD6>3.0.CO;2-E

[12] T. Gustavsson, “Decompositions of Large Graphs and Digraphs with High Minimum Degree,” Ph.D. Thesis, University of Stockholm, Stockholm, 1991.