In this chapter, we focus on the ten most studied graph convexity parameters, listed in Sect. 2.2 . There is a subsection to each of them where we recall their definition, list results from the literature, and show examples for simple graphs, determining their values in the most known convexities: geodesic, monophonic, and \(P_3\) . Remember that the geodesic, monophonic, and \(P_3\) convexities are associated with minimum paths, induced paths, and \(P_3\) paths within the graph, respectively. As in Lemma 2.3 , they can coincide in certain graph classes, such as the geodesic and monophonic convexities in distance–hereditary graphs, in trees, and in the graph of Fig. 3.2.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Graph Convexity Parameters

  • Júlio Araújo,
  • Mitre C. Dourado,
  • Fábio Protti,
  • Rudini M. Sampaio

摘要

In this chapter, we focus on the ten most studied graph convexity parameters, listed in Sect. 2.2 . There is a subsection to each of them where we recall their definition, list results from the literature, and show examples for simple graphs, determining their values in the most known convexities: geodesic, monophonic, and \(P_3\) . Remember that the geodesic, monophonic, and \(P_3\) convexities are associated with minimum paths, induced paths, and \(P_3\) paths within the graph, respectively. As in Lemma 2.3 , they can coincide in certain graph classes, such as the geodesic and monophonic convexities in distance–hereditary graphs, in trees, and in the graph of Fig. 3.2.