A class of graphs with depression three

作者：Mynhardt C M; Schurch M^*

来源：Discrete Mathematics, 2013, 313(11): 1224-1232.

DOI：10.1016/j.disc.2012.05.011

• Edge ordering of a graph
• Increasing path
• Monotone path
• Depression

An edge ordering of a graph G is an injection f : E -%26gt; 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. We characterize the class of graphs with depression three and without adjacent vertices of degree three or higher.

• 出版日期2013-6-6