×

Rebuilding convex sets in graphs. (English) Zbl 1070.05035

Summary: The usual distance between pairs of vertices in a graph naturally gives rise to the notion of an interval between a pair of vertices in a graph. This in turn allows us to extend the notions of convex sets, convex hull, and extreme points in Euclidean space to the vertex set of a graph. The extreme vertices of a graph are known to be precisely the simplicial vertices, i.e., the vertices whose neighborhoods are complete graphs. It is known that the class of graphs with the Minkowski-Krein-Milman property, i.e., the property that every convex set is the convex hull of its extreme points, is precisely the class of chordal graphs without induced 3-fans. We define a vertex to be a contour vertex if the eccentricity of every neighbor is at most as large as that of the vertex. In this paper we show that every convex set of vertices in a graph is the convex hull of the collection of its contour vertices. We characterize those graphs for which every convex set has the property that its contour vertices coincide with its extreme points. A set of vertices in a graph is a geodetic set if the union of the intervals between pairs of vertices in the set, taken over all pairs in the set, is the entire vertex set. We show that the contour vertices in distance hereditary graphs form a geodetic set.

MSC:

05C12 Distance in graphs
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bandelt, H.-J.; Mulder, H. M., Distance-hereditary graphs, J. Combin. Theory Ser. B, 41, 182-208 (1986) · Zbl 0605.05024
[2] Bandelt, H.-J.; Mulder, H. M., Three interval conditions for graphs, Twelfth British Combinatorial Conference (Norwich, 1989), Ars Combin., 29B, 213-223 (1990)
[3] Bielak, H.; Syslo, M., Peripherical vertices in graphs, Studia Scientiarum Mathematicarum Hungarica, 18, 269-275 (1983) · Zbl 0569.05030
[4] Bilbao, J. M.; Edelman, P. H., The Shapley value on convex geometries, Discrete Appl. Math., 103, 33-40 (2000) · Zbl 0955.91002
[5] Brandstädt, A.; Dragan, F. F.; Nicolai, F., Homogeneously orderable graphs, Theoret. Comput. Sci., 172, 209-232 (1997) · Zbl 0903.68136
[6] Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graph Classes: A survey (1999), SIAM Monograph on Discrete Mathematics and Applications: SIAM Monograph on Discrete Mathematics and Applications Philadelphia · Zbl 0919.05001
[7] Chartrand, G.; Harary, F.; Zhang, P., Geodetic sets in graphs, Discuss. Math. Graph Theory, 20, 29-138 (2000) · Zbl 0958.05044
[8] D’Atri, A.; Moscarini, M., Distance-hereditary graphs, Steiner trees and connected domination, SIAM J. Comput., 17, 521-538 (1988) · Zbl 0647.05048
[9] Day, D. P.; Oellermann, O. R.; Swart, H. C., Steiner distance-hereditary graphs, SIAM J. Discrete Math., 7, 437-442 (1994) · Zbl 0805.05021
[10] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Math., 7, 433-444 (1986) · Zbl 0591.05056
[11] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[12] Golumbic, M.; Rotics, U., On the clique width of some perfect graph classes, Internat. J. Foundations Comput. Sci., 11, 423-443 (2000) · Zbl 1320.05090
[13] Hammer, P. L.; Maffray, F., Completely separable graphs, Discrete Appl. Math., 27, 85-100 (1990) · Zbl 0694.05060
[14] Harary, F., Graph Theory (1969), Perseus Books: Perseus Books Cambridge, Massachusetts · Zbl 0797.05064
[15] Howorka, E., A characterization of distance hereditary graphs, Quart. J. Math. Oxford, 28, 417-420 (1977) · Zbl 0376.05040
[16] Howorka, E., A characterization of ptolemaic graphs, J. Graph Theory, 5, 323-331 (1981) · Zbl 0437.05046
[17] H.M. Mulder, The interval function of a graph, Mathematical Centre Tracts, vol. 132, Mathematisch Centrum, Amsterdam, 1980.; H.M. Mulder, The interval function of a graph, Mathematical Centre Tracts, vol. 132, Mathematisch Centrum, Amsterdam, 1980. · Zbl 0446.05039
[18] Nebeský, L., Characterizing the interval function of a connected graph, Mathematica Bohemica, 123, 137-144 (1998) · Zbl 0937.05036
[19] O.R. Oellermann, M.L. Puertas, Steiner intervals and Steiner geodetic numbers in distance hereditary Graphs. Preprint.; O.R. Oellermann, M.L. Puertas, Steiner intervals and Steiner geodetic numbers in distance hereditary Graphs. Preprint. · Zbl 1113.05030
[20] Van de Vel, M. J.L., Theory of Convex Structures (1993), North-Holland: North-Holland Amsterdam · Zbl 0785.52001
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.