Advertisement
Published in:
2020 | OriginalPaper | Chapter
\(\varDelta \)-Convexity Number and \(\varDelta \)-Number of Graphs and Graph Products
Authors : Bijo S. Anand, Prasanth G. Narasimha-Shenoi, Sabeer Sain Ramla
Published in: Algorithms and Discrete Applied Mathematics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The \(\varDelta \)-interval of \(u,v \in V (G)\), \(I_{\varDelta }(u,v)\), is the set formed by u, v and every w in V(G) such that \(\{u, v, w\}\) is a triangle \((K_3)\) of G. A set S of vertices such that \(I_{\varDelta } (S)=V(G)\) is called a \(\varDelta \)-set. \(\varDelta \)-number is the minimum cardinality of a \(\varDelta \)-set. \(\varDelta \)-graph is a graph with all the vertices lie on some triangles. If a block graph is a \(\varDelta \)-graph, then we say that it is a block \(\varDelta \)-graph. A set \(S\subseteq V (G)\) is \(\varDelta \)-convex if there is no vertex \(u \in V(G)\setminus S\) forming a triangle with two vertices of S. The convexity number of a graph G with respect to the \(\varDelta \)-convexity is the maximum cardinality of a proper convex subset of G. We have given an exact value for the convexity number of block \(\varDelta \)-graphs with diameter \({\le }3\), block \(\varDelta \)-graphs with diameter \({>}3\) and the two standard graph products (Strong, Lexicographic products), a bound for Cartesian product. Also discussed some bounds for \(\varDelta \)-number and a realization is done for the \(\varDelta \)-number and the hull number.