Convex cycle bases

Marc Hellmuth, Josef Leydold, Peter F. Stadler

Abstract


Convex cycles play a role e.g. in the context of product graphs. We introduce convex cycle bases and describe a polynomial-time algorithm that recognizes whether a given graph has a convex cycle basis and provides an explicit construction in the positive case. Relations between convex cycles bases and other types of cycles bases are discussed. In particular we show that if G has a unique minimal cycle bases, this basis is convex. Furthermore, we characterize a class of graphs with convex cycles bases that includes partial cubes and hence median graphs.

Keywords


cycle basis; convex subgraph; isometric subgraph; Cartesian product; partial cubes

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.226.0a2

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications