×
Dourado, Mitre C.; Penso, Lucia D.; Rautenbach, Dieter

Geodetic convexity parameters for \((q, q - 4)\)-graphs. (English) Zbl 1464.05333

Discrete Appl. Math. 223, 64-71 (2017).
Summary: Following a suggestion of V. Campos et al. [ibid. 192, 28–39 (2015; Zbl 1319.05077)] we show that, within the geodetic convexity, the interval number, the convexity number, the Carathéodory number, and the Radon number can be computed in polynomial time for \((q, q - 4)\)-graphs.

Cited in 1 Document

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C12 Distance in graphs
05C38 Paths and cycles
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity

Keywords:

geodetic convexity; hull number; geodetic number; interval number; convexity number; Carathéodory number; Radon number; \((q, q - 4)\)-graphs

Citations:

Zbl 1319.05077
Cite Review PDF
Full Text: DOI

References:

[1] Albenque, M.; Knauer, K., Convexity in partial cubes: The hull number, Lecture Notes in Comput. Sci., 8392, 421-432 (2014) · Zbl 1405.68233
[2] Araujo, J.; Campos, V.; Giroire, F.; Nisse, N.; Sampaio, L.; Soares, R., On the hull number of some graph classes, Theoret. Comput. Sci., 475, 1-12 (2013) · Zbl 1419.05049
[3] Araujo, J.; Morel, G.; Sampaio, L.; Soares, R.; Weber, V., Hull number: \(P_5\)-free graphs and reduction rules, Discrete Appl. Math., 210, 171-175 (2016) · Zbl 1339.05064
[5] Babel, L.; Olariu, S., On the structure of graphs with few \(P_4\)’s, Discrete Appl. Math., 84, 1-13 (1998) · Zbl 0908.05065
[6] Buckley, F.; Harary, F.; Quintas, L. V., Extremal results on the geodetic number of a graph, Scientia, 2, 17-26 (1988) · Zbl 0744.05021
[7] Campos, V.; Sampaio, R. M.; Silva, A.; Szwarcfiter, J. L., Graphs with few \(P_4\)’s under the convexity of paths of order three, Discrete Appl. Math., 192, 28-39 (2015) · Zbl 1319.05077
[8] Carathéodory, C., Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo (2), 32, 193-217 (1911) · JFM 42.0429.01
[9] Changat, M.; Klavžar, S.; Mulder, H. M., The all-paths transit function of a graph, Czechoslovak Math. J., 51, 439-448 (2001) · Zbl 0977.05135
[10] Changat, M.; Mathew, J., On triangle path convexity in graphs, Discrete Math., 206, 91-95 (1999) · Zbl 0929.05046
[11] Changat, M.; Prasanth, G. N.; Mathews, J., Triangle path transit functions, betweenness and pseudo-modular graphs, Discrete Math., 309, 1575-1583 (2009) · Zbl 1228.05190
[12] Chartrand, G.; Wall, C. E.; Zhang, P., The convexity number of a graph, Graphs Combin., 18, 209-217 (2002) · Zbl 1002.05018
[13] Dourado, M. C.; Gimbel, J. G.; 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
[14] Dourado, M. C.; Sá, V. G. Pereira de; Rautenbach, D.; Szwarcfiter, J. L., On the geodetic Radon number of grids, Discrete Math., 313, 111-121 (2013) · Zbl 1254.05193
[15] Dourado, M. C.; Sá, V. G. Pereira de; Rautenbach, D.; Szwarcfiter, J. L., Near-linear-time algorithm for the geodetic Radon number of grids, Discrete Appl. Math., 210, 277-283 (2016) · Zbl 1339.05304
[16] Dourado, M. C.; Protti, F.; Rautenbach, D.; Szwarcfiter, J. L., On the hull number of triangle-free graphs, SIAM J. Discrete Math., 23, 2163-2172 (2010) · Zbl 1207.05044
[17] 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
[18] Dourado, M. C.; Protti, F.; Rautenbach, D.; Szwarcfiter, J. L., On the convexity number of graphs, Graphs Combin., 28, 333-345 (2012) · Zbl 1256.05123
[19] Dourado, M. C.; Protti, F.; Szwarcfiter, J. L., Complexity results related to monophonic convexity, Discrete Appl. Math., 158, 1269-1274 (2010) · Zbl 1209.05130
[20] Dourado, M. C.; Rautenbach, D.; dos Santos, V.; Schäfer, P. M.; Szwarcfiter, J. L., On the Carathéodory number of interval and graph convexities, Theoret. Comput. Sci., 510, 127-135 (2013) · Zbl 1419.05143
[21] Dragan, F.; Nicolai, F.; Brandstädt, A., Convexity and HHD-free graphs, SIAM J. Discrete Math., 12, 119-135 (1999) · Zbl 0916.05060
[22] Duchet, P., Convex sets in graphs II: Minimal path convexity, J. Combin. Theory Ser. B, 44, 307-316 (1988) · Zbl 0672.52001
[23] Ekim, T.; Erey, A., Block decomposition approach to compute a minimum geodetic set, RAIRO Rech. Oper., 48, 497-507 (2014) · Zbl 1301.05100
[24] Ekim, T.; Erey, A.; Heggernes, P.; van’t Hof, P.; Meister, D., Computing minimum geodetic sets of proper interval graphs, Lecture Notes in Comput. Sci., 7256, 279-290 (2012) · Zbl 1353.68119
[25] Everett, M. G.; Seidman, S. B., The hull number of a graph, Discrete Math., 57, 217-223 (1985) · Zbl 0584.05044
[26] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebr. Discrete Methods, 7, 433-444 (1986) · Zbl 0591.05056
[27] Gimbel, J., Some remarks on the convexity number of a graph, Graphs Combin., 19, 357-361 (2003) · Zbl 1023.05079
[28] Kanté, M. M.; Nourine, L., Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs, Lecture Notes in Comput. Sci., 7741, 268-279 (2013) · Zbl 1303.05195
[29] Radon, J., Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten, Math. Ann., 83, 113-115 (1921) · JFM 48.0834.04
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.