Geodesic
Convex cycle bases
Ars Mathematica Contemporanea, Tome 7 (2014) no. 1, pp. 123-140.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.226.0a2
Keywords: cycle basis, convex subgraph, isometric subgraph, Cartesian product, partial cubes 
@article{10_26493_1855_3974_226_0a2,
     author = {Marc Hellmuth and Josef Leydold and Peter F. Stadler},
     title = {Convex cycle bases},
     journal = {Ars Mathematica Contemporanea},
     pages = {123--140},
     publisher = {mathdoc},
     volume = {7},
     number = {1},
     year = {2014},
     doi = {10.26493/1855-3974.226.0a2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.226.0a2/}
}
TY  - JOUR
AU  - Marc Hellmuth
AU  - Josef Leydold
AU  - Peter F. Stadler
TI  - Convex cycle bases
JO  - Ars Mathematica Contemporanea
PY  - 2014
SP  - 123
EP  - 140
VL  - 7
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.226.0a2/
DO  - 10.26493/1855-3974.226.0a2
LA  - en
ID  - 10_26493_1855_3974_226_0a2
ER  - 
%0 Journal Article
%A Marc Hellmuth
%A Josef Leydold
%A Peter F. Stadler
%T Convex cycle bases
%J Ars Mathematica Contemporanea
%D 2014
%P 123-140
%V 7
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.226.0a2/
%R 10.26493/1855-3974.226.0a2
%G en
%F 10_26493_1855_3974_226_0a2
Marc Hellmuth; Josef Leydold; Peter F. Stadler. Convex cycle bases. Ars Mathematica Contemporanea, Tome 7 (2014) no. 1, pp. 123-140. doi : 10.26493/1855-3974.226.0a2. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.226.0a2/

Cité par Sources :