Abstract
If S is a set of vertices of a graph G, then the convex hull of S in the P 3-convexity of G is the smallest set H G (S) of vertices of G that contains S such that no vertex in V (G) H G (S) has at least two neighbors in S. The Carathéodory number of the P 3 convexity of G is the smallest integer c such that for every set S of vertices of G and every vertex u in H G (S), there is a set F ⊆ S with ¦F¦ ≤ c and u ∈ H G (F). We describe a polynomial time algorithm to determine the Carathéodory number of the P 3 convexity of a chordal graph.
We gratefully acknowledge financial support by the CAPES/DAAD Probral project “Cycles, Convexity, and Searching in Graphs” (PPP Project ID 56102978).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
R. M. Barbosa, E. M. M. Coelho, M. C. Dourado, D. Rautenbach and J. L. Szwarcfiter, On the Carathéodory number for the convexity of paths of order three, SIAM J. Discrete Math. 26 (2012), 929–939.
J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas and C. Seara, On geodetic sets formed by boundary vertices, Discrete Math. 306 (2006), 188–198.
C. Carathéodory, Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo 32 (1911), 193–217.
C. C. Centeno, S. Dantas, M. C. Dourado, D. Rautenbach and J. L. Szwarcfiter, Convex Partitions of Graphs induced by Paths of Order Three, Discrete Mathematics and Theoretical Computer Science 12 (2010), 175–184.
C. C. Centeno, M. C. Dourado, L. D. Penso, D. Rautenbach and J. L. Szwarcfiter, Irreversible conversion of graphs, Theoretical Computer Science 412 (2011), 3693–3700.
M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Math. 206 (1999), 91–95.
M. Changat, S. Klav~zar and H. M. Mulder, The all-paths transit function of a graph, Czech. Math. J. 51(126) (2001), 439–448.
M. C. Dourado, F. Protti, D. Rautenbach and J. L. Szwarcfiter, On the hull number of triangle-free graphs, SIAM J. Discrete Math. 23 (2010), 2163–2172.
M. C. Dourado, F. Protti and J. L. Szwarcfiter, Complexity results related to monophonic convexity, Discrete Appl. Math. 158 (2010), 1269–1274.
P. Duchet, Convex sets in graphs II: Minimal path convexity, J. Combin. Theory, Ser. B 44 (1988), 307–316.
P. Erdős, E. Fried, A. Hajnal and E.C. Milner, Some remarks on simple tournaments, Algebra Univers. 2 (1972), 238–245.
M. G. Everett and S. B. Seidman, The hull number of a graph, Discrete Math. 57 (1985), 217–223.
M. Farber and R. E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods 7 (1986), 433–444.
M. Farber and R. E. Jamison, On local convexity in graphs, Discrete Math. 66 (1987), 231–247.
J. W. Moon, Embedding tournaments in simple tournaments, Discrete Math. 2 (1972), 389–395.
D. B. Parker, R. F. Westhoff and M. J. Wolf, On two-path convexity in multipartite tournaments, European J. Combin. 29 (2008), 641–651.
J. C. Varlet, Convexity in tournaments, Bull. Soc. R. Sci. Liége 45 (1976), 570–586.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2013 Scuola Normale Superiore Pisa
About this paper
Cite this paper
Coelho, E.M.M., Dourado, M.C., Rautenbach, D., Szwarcfiter, J.L. (2013). The Carathéodory number of the P 3 convexity of chordal graphs. In: Nešetřil, J., Pellegrini, M. (eds) The Seventh European Conference on Combinatorics, Graph Theory and Applications. CRM Series, vol 16. Edizioni della Normale, Pisa. https://doi.org/10.1007/978-88-7642-475-5_34
Download citation
DOI: https://doi.org/10.1007/978-88-7642-475-5_34
Publisher Name: Edizioni della Normale, Pisa
Print ISBN: 978-88-7642-474-8
Online ISBN: 978-88-7642-475-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)