ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

The l1 - Convexity number of a graph

Journal: International Journal of Mathematics and Soft Computing (Vol.5, No. 2)

Publication Date:

Authors : ; ;

Page : 9-14

Keywords : Convex set; local convexity number; local clique number;

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

Let $G$ be a simple connected graph. A subset $S$ of vertices of $G$ is said to be a convex set if for any two vertices $u$, $v$ of $S$, $S$ contains all the vertices of every $u - v$ shortest path in $G$. The convexity number $con(G)$ of $G$ is the maximum cardinality of a proper convex set of $G$. The local convexity number of a graph denoted by $l_{1}con(G)$ is defined as the maximum of ${con(< N[x]>) / x in V(G) $ and $ con(< N[x]>) $ set is a proper convex set of $G }$. For a connected graph $G$ of order $n geq 3$, we have $2 leq l_{1}con(G) leq n-1$. Local convex set for which its cardinality is same as $l_{1}con(G)$ is called a maximum local convex set. Local clique number denoted by $omega_{1}(G)$ is the cardinality of a maximum clique in the set of all maximum local convex sets of $G$. Here we present characterisation of graphs for which $l_{1}con (G) = con (G)$, equivalent condition in graphs for which $N[S]$ is convex for any connected subgraph $< S >$ of $G$ is presented. Interesting results and construction of graphs with prescribed $l_{1}con(G)$, $omega_{1}(G)$ are also presented.

Last modified: 2017-08-29 19:58:53