Subscribe to Syndicate

Marc Hellmuth

S-prime graphs are graphs that cannot be represented as nontrivial subgraphs of nontrivial Cartesian products of graphs, i.e., whenever it is a subgraph of a nontrivial Cartesian product graph it is a subgraph of one the factors. A graph is S-composite if it is not S-prime.
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.
A graph is said to be View the MathML source-prime if, whenever it is a subgraph of a nontrivial Cartesianproductgraph, it is a subgraph of one of the factors. A diagonalizedCartesianproduct is obtained from a Cartesianproductgraph by connecting two vertices of maximal distance by an additional edge. We show there that a diagonalizedproduct of View the MathML source-primegraphs is again View the MathML source-prime. Klavžar et al. [S. Klavžar, A. Lipovec, M. Petkovšek, On subgraphs of Cartesianproductgraphs, Discrete Math.

Pages