A lower bound for the convexity number of some graphs
type: Item
instance of: scholarly article
title: A lower bound for the convexity number of some graphs
zbMATH Open document ID: 1035.05036
DOI: 10.1007/BF02936107
author: Byung Kee Kim
published in: Journal of Applied Mathematics and Computing
publication date: 2004-03-29T00:00:00Z
review text: A set \(C\) of vertices in a connected graph \(G\) is called convex if for all \(x,y\in C\) all vertices of each shortest \(x\)-\(y\)-path are in \(C\). The convexity number of \(G\) is defined to be the cardinality of a maximal proper convex set in \(G\). The main result of the paper reads: for all integers \(k\) and \(n\) satisfying \(2\leq k\leq n-1\) there is a connected triangle-free graph with \(n\) vertices whose convexity number is \(k\).
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 2063145
zbMATH Keywords: distance
reviewed by: Mikhail Ostrovskii
MaRDI profile type: Publication
cites work: Q4692391
cites work: The convexity number of a graph
cites work: Q4949868
cites work: Q5572939
cites work: Convexity in graphs
cites work: Convex sets under some graph operations
full work available at URL: https://doi.org/10.1007/bf02936107
OpenAlex ID: W2118371044
description: scientific article; zbMATH DE number 2063145