Trees with depression three

DOI10.1016/J.DISC.2007.07.039MaRDI QIDQ2470454zbMATH OpenOpenAlexFDO

Authors Christina M. Mynhardt

Publication date 14 February 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.07.039

zbMATH Keywords

depressionedge orderingincreasing pathmonotone pathtree

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

An edge ordering of a graph is an injection \(f\) from the edge set into the set of natural numbers. A simple path for which \(f\) increases along its edge sequence is an \(f\)-ascent, and an \(f\)-ascent is called maximal if it is not contained by a longer \(f\)-ascent. The depression of a graph is the smallest integer \(k\) such that every edge ordering of the graph has a maximal ascent of length at most \(k\). Earlier Cockayne at al. characterized trees with depression 2. This paper characterizes trees with depression 3. The trees with depression 3 are produced by a recursive procedure.

Recommendations

• A lower bound for the depression of trees
• A class of graphs with depression three
• A construction of a class of graphs with depression three
• The depression of a graph
• Edge colourings and the depression of a graph

Cites work

• A lower bound for the depression of trees
• A monotone path in an edge-ordered graph
• Altitude of regular graphs with girth at least five
• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• scientific article; zbMATH DE number 2147937 (Why is no real title available?)
• Increasing paths in edge ordered graphs
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• Large monotone paths in graphs with bounded degree
• Monotone paths in edge-ordered sparse graphs
• Some Combinatorial Theorems on Monotonicity
• The depression of a graph

Cited in

(8)

• The depression of a graph and \(k\)-kernels
• A construction of a class of graphs with depression three
• Three tree-paths
• A class of graphs with depression three
• Edge colourings and the depression of a graph
• A lower bound for the depression of trees
• The depression of a graph
• Finding monotone paths in edge-ordered graphs

This page was built for publication: Trees with depression three

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2470454)