×

Towards a new framework for domination. (English) Zbl 1228.05223

Summary: Dominating concepts constitute a cornerstone in Graph Theory. Part of the efforts in the field have been focused in finding different mathematical frameworks where domination notions naturally arise, providing new points of view about the matter. In this paper, we introduce one of these frameworks based in convexity. The main idea consists of defining a convexity in a graph, already used in image processing, for which the usual parameters of convexity are closely related to domination parameters. Moreover, the Helly number of this convexity may be viewed as a new domination parameter whose study would be of interest.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
52A35 Helly-type theorems and geometric transversal theory
68R10 Graph theory (including graph drawing) in computer science
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002
[2] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs: Advanced Topics (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0883.00011
[3] Chartrand, G.; Haynes, T. W.; Henning, M. A.; Zhang, P., Stratification and domination in graphs, Discrete Math., 272, 171-185 (2003) · Zbl 1028.05074
[4] Diestel, R., Graph Theory (2005), Springer-Verlag: Springer-Verlag Heidelberg · Zbl 1074.05001
[5] Bollobás, B.; Cockayne, E. J., Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory, 3, 241-249 (1979) · Zbl 0418.05049
[6] Cockayne, E. J.; Hedetniemi, S. T., Towards a theory of domination in graphs, Networks, 7, 247-261 (1977) · Zbl 0384.05051
[7] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039
[8] Cockayne, E. J.; Goodman, S.; Hedetniemi, S. T., A linear algorithm for the domination number of a tree, Inform. Process. Lett., 4, 41-44 (1975) · Zbl 0311.68024
[9] Chang, G. J., Algorithmic aspects of domination in graphs, (Du, D. Z.; Pardalos, P. M., Handbook of Combinatorial Optimization, vol. 3 (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA), 339-405 · Zbl 1058.90524
[10] Cockayne, E. J.; Hedetniemi, S. T.; Miller, D. J., Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull., 21, 461-468 (1978) · Zbl 0393.05044
[11] Favaron, O., Two relations between the parameters of independence and irredundance, Discrete Math., 70, 17-20 (1988) · Zbl 0639.05029
[12] Van de Vel, M. L.J., Theory of Convex Structures (1993), North-Holland: North-Holland Amsterdam · Zbl 0785.52001
[13] Critescu, G.; Lupsa, L., Classes of discrete convexity properties, Discrete Comput. Geom., 31, 461-490 (2004) · Zbl 1069.52013
[14] Rosenfeld, A.; Pfaltz, J. L., Sequential operations in digital picture processing, J. ACM, 13, 4, 471-494 (1966) · Zbl 0143.41803
[15] Pfaltz, J. L.; Jamison, R. E., Closure systems and their structure, Inform. Sci., 139, 275-286 (2001) · Zbl 0993.06004
[16] Chartrand, G.; Erwin, D.; Johns, G. L.; Zhang, P., Boundary vertices in graphs, Discrete Math., 263, 25-34 (2003) · Zbl 1020.05024
[17] Cáceres, J.; Márquez, A.; Oellermann, O.; Puertas, M. L., Rebuilding convex sets in graphs, Discrete Math., 297, 1, 26-37 (2005) · Zbl 1070.05035
[18] Dourado, M. C.; Gimbel, J.; Kratochvíl, J.; Protti, F.; Szwarcfiter, J. L., On the computation of the hull number of a graph, Discrete Math., 309, 5668-5674 (2009) · Zbl 1215.05184
[19] Dourado, M. C.; Protti, F.; Rautenbach, D.; Szwarcfiter, J. L., Some remarks on the geodetic number of a graph, Discrete Math., 310, 832-837 (2010) · Zbl 1209.05129
[20] Ore, O., Theory of Graphs, vol. 38 (1962), American Mathematical Society Colloquium Publications: American Mathematical Society Colloquium Publications Providence, RI
[21] Berge, C., Theory of Graphs and its Applications (2003), Textbook Publishers: Textbook Publishers East Lansing, MI
[22] Cockayne, E. J.; Mynhardt, C. M., The sequence of upper and lower domination, independence and irredundance numbers of a graph, Discrete Math., 122, 89-102 (1993) · Zbl 0788.05055
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.