Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

The depression of a graph and k-kernels

100%

Schurch M., Mynhardt C.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 2

233-247

An edge ordering of a graph G is an injection f : E(G) → R, the set of real numbers. A path in G for which the edge ordering f increases along its edge sequence is called an f-ascent ; an f-ascent is maximal if it is not contained in a longer f-ascent. The depression of G is the smallest integer k such that any edge ordering f has a maximal f-ascent of length at most k. A k-kernel of a graph G is a set of vertices U ⊆ V (G) such that for any edge ordering f of G there exists a maximal f-ascent of length at most k which neither starts nor ends in U. Identifying a k-kernel of a graph G enables one to construct an infinite family of graphs from G which have depression at most k. We discuss various results related to the concept of k-kernels, including an improved upper bound for the depression of trees.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Mynhardt C.

1 Schurch M.

1 2014

Wyniki wyszukiwania

The depression of a graph and k-kernels