zbMATH — the first resource for mathematics

Covering, packing and generalized perfection. (English) Zbl 0556.05055
For simple graph \(G=(V,E)\) let T be a family of subsets of V. A T- covering of G is a subset F(T) of T with the property that each vertex \(v\in V\) is in at least one member of F(T); let \(\theta\) (G:T) denote the minimum cardinality of a T-covering of G. A T-packing is a vertex subset P(T) of B with the property that each vertex subset S in T contains at most one vertex in P(T); let \(\alpha\) (G;T) denote the maximum cardinality of a T-packing. Clearly \(\alpha (G:T)\leq \theta (G:T)\) for all G and T.
This paper studies covering and packing problems for \(T_ k\), the family of subtrees of diameter at most k. In particular, classes of chordal graphs for which \(\theta (H:T_ k)=\alpha (H:T_ k)\) for all induced subgraphs H of G are studied.
Reviewer: P.Slater

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C99 Graph theory
PDF BibTeX Cite
Full Text: DOI
[1] Berge, Claude, LES problèmes de coloration en théorie des graphes, Publ. Inst. Statist. Univ. Paris, 9, 123, (1960) · Zbl 0103.16201
[2] Berge, C., Balanced matrices, Math. Programming, 2, 19, (1972) · Zbl 0247.05126
[3] Berge, Claude, Graphs and hypergraphs, (1973) · Zbl 0254.05101
[4] 1982Personal communication
[5] Polynomial algorithm to recognize a meyniel graphResearch Report303Lab. Inform. Math. Appl. de GrenobleFrance1982
[6] Ph.D. ThesisK-domination and graph covering problemsSchool of Operations Research and Industrial Engneering, Cornell Univ.Ithaca, NY1982
[7] Chang, GerardJ.; Nemhauser, GeorgeL., The k-domination and k-stability problems on Sun-free chordal graphs, SIAM J. Algebraic Discrete Methods, 5, 332, (1984) · Zbl 0576.05054
[8] Christofides, Nicos, Graph theory, (1975) · Zbl 0321.94011
[9] Perfectly ordered graphsTech. ReportSOCS-81.28McGill Univ.Montreal1981
[10] Cockayne, E. J.; Goodman, S.; Hedetniemi, S. T., A linear algorithm for the domination number of a tree, Inform. Proc. Letters, 4, 41, (1975) · Zbl 0311.68024
[11] Fulkerson, D. R.; Hoffman, A. J.; Oppenheim, Rosa, On balanced matrices, Math. Programming Stud., 120, (1974) · Zbl 0357.90038
[12] Golumbic, MartinCharles, Algorithmic graph theory and perfect graphs, (1980) · Zbl 0541.05054
[13] Polynomial algorithms for perfect graphsReport81176-0RInstitut für Ökonometrie and Operations Research, Universität BonnBonn, W. Germany1981
[14] Hajnal, András; Surányi, János, Über die auflösung von graphen in vollständige teilgraphen, Ann. Univ. Sci. Budapest. Eötvös. Sect. Math., 1, 113, (1958) · Zbl 0093.37801
[15] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 253, (1972) · Zbl 0239.05111
[16] Meir, A.; Moon, J. W., Relations between packing and covering numbers of a tree, Pacific J. Math., 61, 225, (1975) · Zbl 0315.05102
[17] Meyniel, H., On the perfect graph conjecture, Discrete Math., 16, 339, (1976) · Zbl 0383.05018
[18] Rose, DonaldJ.; Tarjan, R. Endre; Lueker, GeorgeS., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266, (1976) · Zbl 0353.65019
[19] Slater, PeterJ., R-domination in graphs, J. Assoc. Comput. Mach., 23, 446, (1976) · Zbl 0349.05120
[20] Tansel, BarbarosC.; Francis, RichardL.; Lowe, TimothyJ.; Tansel, BarbarosC.; Francis, RichardL.; Lowe, TimothyJ., Location on networks: a survey. II. exploiting tree network structure, Management Sci., 29, 498, (1983) · Zbl 0513.90023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.