Premium
Degree sequences of graphs and dominance order
Author(s) -
Triesch Eberhard
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199605)22:1<89::aid-jgt12>3.0.co;2-j
Subject(s) - partition (number theory) , mathematics , combinatorics , frequency partition of a graph , dominance (genetics) , graph , order (exchange) , discrete mathematics , line graph , graph power , chemistry , economics , biochemistry , finance , gene
Suppose that the graphical partition H ( A ) = ( a 2 1 ≥ ··· ≥ a n 1 ) arises from A = ( a 1 ≥ ··· ≥ a n ) by deleting the largest summand a 1 from A and reducing the a 1 largest of the remaining summands by one. Let ( a i +1 ′ ≥ ··· ≥ a n ′) = H ′( A ) denote the partition obtained by applying the operator H i times. We prove that the dominance order of partitions is preserved when we switch from A to ( a 1 ≥ a 2 1 ≥ ··· ≥ a i +1 ′ ≥ ···) =: E (A). This generalizes a recent result by Favaron, Mahéo, and Saclé on the residue of a graph. © 1996 John Wiley & Sons, Inc.