d5d5d5;padding:1px 3px;height:17px; line-height:17px; display:inline-block;' >Full-Text HTML Download Download as PDF (Size:145KB) PP. 1719-1722
DOI: 10.4236/am.2012.311237    3,435 Downloads   5,133 Views Citations
Author(s)
Teresa Sousa

Affiliation(s)

Departamento de Matemática and Centro de Matemática e Aplica??es, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, Quinta da Torre, Caparica, Portugal.

ABSTRACT

The concept of H-decompositions of graphs was first introduced by Erd?s, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decom- positions of graphs.

KEYWORDS

Graph Decompositions; Weighted Graph Decompositions; Monochromatic Graph Decompositions; Turán Graph; Ramsey Numbers

Cite this paper

T. Sousa, "The H-Decomposition Problem for Graphs," Applied Mathematics, Vol. 3 No. 11, 2012, pp. 1719-1722. doi: 10.4236/am.2012.311237.
AM Subscription
E-Mail Alert
AM Most popular papers
Publication Ethics & OA Statement
AM News
Frequently Asked Questions
Recommend to Peers
Recommend to Library
Contact Us

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.