A service provided by the WU Library and the WU IT-Services

Convex Cycle Bases

Hellmuth, Marc and Leydold, Josef and Stadler, Peter F. (2013) Convex Cycle Bases. Research Report Series / Department of Statistics and Mathematics, 124. WU Vienna University of Economics and Business, Vienna.

[img]
Preview
PDF
Download (297Kb) | Preview

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. (authors' abstract)

Item Type: Paper
Additional Information: This paper has been accepted for publication in Ars Mathematica Contemporanea.
Keywords: cycle basis / convex subgraph / isometric subgraph / Cartesian product / partial cubes / Graphentheorie / Kreis / Isometrischer Teilgraph / Algorithmen
Classification Codes: RVK QM 451, SK 890
Divisions: Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Depositing User: Josef Leydold
Date Deposited: 19 Feb 2013 09:31
Last Modified: 18 Nov 2014 12:37
URI: http://epub.wu.ac.at/id/eprint/3785

Actions

View Item