|
The Depression of a Graph |
|---|
EJ Cockayne1, G Geldenhuys2, PJP Grobler3, CM Mynhardt4 & Jan H van Vuuren5
Abstract
The notions of the flatness of an edge-ordering and of the depression of a simple graph are introduced. Some general properties of these parameters are established, after which a characterisation of graphs with depression two is given and exact values for the depression parameter of a number of simple graph classes are found and contrasted with those of a previously established parameter, called the altitude of a graph (which is in a sense the dual to the depression parameter).
An electronic version of the complete paper may be obtained here: [ps] [pdf].
Affiliations
1Department of Mathematics and Statistics, University of Victoria, Box 3045, Victoria, BC, Canada,
V8W 3P4, email: e_cockayne@hotmail.com.
2 Department of Applied Mathematics, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa.
3 Department of Applied Mathematics, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa,
email: pgrobler@sun.ac.za.
4 Department of Mathematics and Statistics, University of Victoria, Box 3045, Victoria, BC, Canada,
V8W 3P4, email: mynhardt@math.uvic.ca.
5 Department of Applied Mathematics, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa,
email: vuuren@sun.ac.za.