Abstract.
Given a subgraph H in a graph G, we say H is convex if given any two vertices u and v in H, then H contains each shortest u–v path in G. As defined in [5], [8] and other places the convexity number of G, denoted con(G), is the order of a largest convex proper subgraph of G. We note that if G is not a complete graph, then the clique number of G forms a lower bound on con(G). As we shall see, in many graphs the clique number and convexity number are equal. We exploit this equality to show that computation of con is NP-complete, provide a Nordhaus-Gaddum type bound for con and produce a Ramsey type theorem for con. We shall see the latter two problems are closely related to classical Ramsey theory. In doing so, we answer a problem posed by Chartrand and Zhang in [5].
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding author
Additional information
Acknowledgments. Respectfully dedicated to Professor Edgar M. Palmer, on the happy occasion of his retirement from Michigan State University. Professor Palmer's kind generosity to his students, colleagues and family is deeply appreciated by many. Salmon beware!!!
Rights and permissions
About this article
Cite this article
Gimbel, J. Some Remarks on the Convexity Number of a Graph. Graphs and Combinatorics 19, 357–361 (2003). https://doi.org/10.1007/s00373-002-0518-4
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00373-002-0518-4