All-path convexity: two characterizations, general position number, and one algorithm

Vladyslav Haponenko; Sergiy Kozerenko

doi:10.47443/dml.2024.014

No Detail Found!

All-path convexity: two characterizations, general position number, and one algorithm

Author(s)

Vladyslav Haponenko National University of Kyiv-Mohyla Academy,Skovorody str. 2, 04070 Kyiv,Ukraine

Sergiy Kozerenko National University of Kyiv-Mohyla Academy, Skovorody str. 2, 04070 Kyiv, Ukraine; Institute of Mathematics of NAS of Ukraine, Tereshchenkivska str. 3, 01024 Kyiv, Ukraine; Kyiv School of Economics, Mykoly Shpaka str. 3, 03113 Kyiv, Ukraine

Abstract

We present two characterizations for the all-path convex sets in graphs. Using the first criterion, we obtain a new characterization of connected block graphs and compute the general position number in a graph with respect to the all-path convexity. The second criterion allows us to provide a new algorithm for testing a set on all-path convexity.

Publication Details

Page(s) 58-65

DOI 10.47443/dml.2024.014

Published Journal: Discrete Mathematics Letters, Volume: 13, Issue: 0, Year: 2024

Request the full text from PASTIC

Keywords

all-path convexity, graph convexity, interval space, block graph, gated set, general position number

References

Bandelt H. J.,Mulder H. M.,Chandran S. V. U.,Parthasarathy G. J.,Changat M.,Klavzar S.,Mulder H. M.,Harary F. .2001 .A characterization of block graphs. Canad. Math. Bull. 6, 51(1963) : 1-6.

Harary F. .1969 .. , : .

Manuel P.,Klavzar S.,Patkos B.,Protti F.,Thompson J. V. C.,Sampathkumar E. .1984 .Convex sets in a graph. Indian J. Pure Appl, 15 : 1065-1071.

Sreedharan S.,Changat M.,Tarjan R. .1972 .Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 21 : 146-160.

Thomas E. J.,Chandran S. V. U.,Thomas E. J.,Chandran S. V. U.,Tuite J.,Stefano G. Di,M. L. J. van de Vel .1993 .On monophonic position sets in graphs. Discrete Appl, 02 : 935-939.

Yao Y.,He M.,Ji S. .2022 .On the general position number of two classes of graphs. , 20 : 1021-1029.