Order-Degree Sequences

Bold, Christoph (1989) Order-Degree Sequences.
Published in: Ars Combinatoria : a Canadian journal of combinatorics Vol. 27. pp. 113-116.


Let G be a graph with vertices x1,...,xn. The order-degree sequence of G is the maximal n-tuple (a1,...,an)=(a(x1),...,a(xn)) of nonnegative integers such that, for i=1(1)n, vertex xi is joined to distinct vertices y1,...,y{asb i} with a(yj) >= j for j=1(1)asb i. We present an algorithm for computing order-degree sequences and study their impact on independence numbers and connectivities. For instance, if n>=3, then the connectivity of G is at least (smax+smin-n+3), where smax and smin are the largest and the smallest component of the order-degree sequence of G.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Content information:
Deposit Information:
ZAIK Number: zpr86-038
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 24 Oct 2011 12:47
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/38