×

Convexity in graphs and hypergraphs. (English) Zbl 0591.05056

The notion of convexity in graphs is extended to hypergraphs and analogues are obtained of several classical results including the Milman- Klein-Minkowski theorem, Caratheodory’s theorem and Tietze’s convexity theorem. New results on chordal graphs and hypergraphs are obtained.
Reviewer: H.N.V.Temperley

MSC:

05C65 Hypergraphs
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anstee, R. P.; Farber, Martin, Characterizations of totally balanced matrices, J. Algorithms, 5, 215, (1984) · Zbl 0551.05026
[2] Beeri, Catriel; Fagin, Ronald; Maier, David; Yannakakis, Mihalis, On the desirability of acyclic database schemes, J. Assoc. Comput. Mach., 30, 479, (1983) · Zbl 0624.68087 · doi:10.1145/2402.322389
[3] Berge, C., Graphs and Hypergraphs, (1983) · Zbl 0523.05040
[4] Berge, C., Balanced matrices, Math. Programming, 2, 19, (1972) · Zbl 0247.05126
[5] Bondy, J. A.; Murty, U. S. R., Graph theory with applications, (1976) · Zbl 1226.05083
[6] Brouwer, A. E.; Kolen, A., A super-balanced hypergraph has a nest point, (1980) · Zbl 0438.05051
[7] Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71, (1961) · Zbl 0098.14703
[8] Duchet, P.; Meyniel, H., Ensemble convexes dans LES graphes. I. théorèmes de Helly et de Radon pour graphes et surfaces, European J. Combin., 4, 127, (1983) · Zbl 0523.05031
[9] Edelman, P., Meet-distributive lattices and the anti-exchange closure, Algebra Universalis, 10, 290, (1980) · Zbl 0442.06004
[10] Farber, Martin, Independent domination in chordal graphs, Oper. Res. Lett., 1, 134, (198182) · Zbl 0495.05053 · doi:10.1016/0167-6377(82)90015-3
[11] Farber, Martin, Characterizations of strongly chordal graphs, Discrete Math., 43, 173, (1983) · Zbl 0514.05048 · doi:10.1016/0012-365X(83)90154-1
[12] Farber, Martin, Domination, independent domination, and duality in strongly chordal graphs, Discrete Appl. Math., 7, 115, (1984) · Zbl 0531.05045 · doi:10.1016/0166-218X(84)90061-1
[13] Some polynomial algorithms for certain graphs and hypergraphsProceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975)Utilitas Math.Winnipeg, Man.1976211-226. Congressus Numerantium, No. XV
[14] Gavril, Fănică, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput., 1, 180, (1972) · Zbl 0227.05116 · doi:10.1137/0201013
[15] Hoffman, A. J.; Kolen, A. W. J.; Sakarovitch, M., Totally-balanced and greedy matrices, SIAM J. Algebraic Discrete Methods, 6, 721, (1985) · Zbl 0573.05041
[16] Howorka, Edward, A characterization of ptolemaic graphs, J. Graph Theory, 5, 323, (1981) · Zbl 0437.05046
[17] A development of axiomatic convexityTech. Report#481Clemson UniversityClemson, SC1970
[18] Jamison, RobertE., Tietze’s convexity theorem for semilattices and lattices, Semigroup Forum, 15, 357, (197778) · Zbl 0381.06004
[19] Jamison, R. E., Copoints in antimatroids, Congr. Numer., 29, 535, (1980) · Zbl 0463.05005
[20] Jamison, R. E., Convexity and block graphs, Congr. Numer., 33, 129, (1981) · Zbl 0495.05056
[21] Jamison, R. E.; Kay, D. C.; Breen, M., A perspective on abstract convexity: classifying alignments by varieties, Convexity and related combinatorial geometry (Norman, Okla., 1980), 76, 113, (1982), Dekker, New York · Zbl 0482.52001
[22] A Helly theorem for convexity in graphsTech. Report# 419Clemson Univ.Clemson, SC1983
[23] Kelley, J. L.; Namioka, I., Linear topological spaces, (1976) · Zbl 0318.46001
[24] Kolen, Antoon, Solving covering problems and the uncapacitated plant location problem on trees, European J. Oper. Res., 12, 266, (1983) · Zbl 0508.90035 · doi:10.1016/0377-2217(83)90197-2
[25] Shelling structures, convexity and a happy endReport#83274—ORInstitute of Operations Research, Univ. Bonn1983
[26] Masters Thesis&ggr;-free matricesMasters thesisUniv. WaterlooWaterloo, Ontario1982October
[27] Rose, D. J., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597, (1970) · Zbl 0216.02602
[28] Ryser, H. J., Combinatorial configurations, SIAM J. Appl. Math., 17, 593, (1969) · Zbl 0186.01901 · doi:10.1137/0117056
[29] Soltan, V. P., {\it d}-convexity in graphs, Soviet Math. Dokl., 28, 419, (1983) · Zbl 0553.05060
[30] Valentine, FrederickA., Convex sets, (1964) · Zbl 0129.37203
[31] White, Kevin; Farber, Martin; Pulleyblank, William, Steiner trees, connected domination and strongly chordal graphs, Networks, 15, 109, (1985) · Zbl 0579.05050
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.