✦ LIBER ✦

Degree sequences of graphs and dominance order

✍ Scribed by Triesch, Eberhard

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 271 KB
Volume: 22
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199605)22:1<89::aid-jgt12>3.0.co;2-j

No coin nor oath required. For personal study only.

✦ Synopsis

Suppose that the graphical partition H(A) = (a: 2 . . . 2 a:) arises from A = (al 2 . . . 2 a,) by deleting the largest summand a1 from A and reducing the a1 largest of the remaining summands by one. Let (a;+l 2 . . 2 ah) = H ( A ) denote the partition obtained by applying the operator H i times. We prove that the dominance order of partitions is preserved when w e switch from A to (a1 2 a: 2 . 2 2 ' .) =: €(A). This generalizes a recent result by Favaron, Maheo, and Sacle on the residue of a graph.

📜 SIMILAR VOLUMES

Signed degree sequences of signed graphs

✍ Yan, Jing-Ho; Lih, Ko-Wei; Kuo, David; Chang, Gerard J. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 1 views

sequence to be the signed degree sequence of a signed graph or a signed tree, answering a question raised by

Degree sequence conditions for maximally

Degree sequence conditions for maximally edge-connected graphs and digraphs

✍ Dankelmann, Peter; Volkmann, Lutz 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB 👁 2 views

In this paper we give simple degree sequence conditions for the equality of edge-connectivity and minimum degree of a (di-)graph. One of the conditions implies results by Bollobás, Goldsmith and White, and Xu. Moreover, we give analogue conditions for bipartite (di-)graphs.

Convexity of degree sequences

✍ Anstee, R. P.; Nam, Yunsun 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 1 views

We explore the convexity of the set of vectors consisting of degree sequences of subgraphs of a given graph. Results of Katerinis and Fraisse, Hell and Kirkpatrick concerning vertex deleted f -factors are generalized.

The degree sequence of a random graph. I

The degree sequence of a random graph. I. The models

✍ Brendan D. McKay; Nicholas C. Wormald 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 2 views

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of 1 random graphs with n vertices and m edges. Fo

On low bound of degree sequences of span

On low bound of degree sequences of spanning trees inK-edge-connected graphs

✍ Zhenhong, Liu; Baoguang, Xu 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 3 views

[•] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d k -tree, and α = 1 for k = 2, α = 2 for k ≥ 3.

The domination and competition graphs of

The domination and competition graphs of a tournament

✍ Fisher, David C.; Lundgren, J. Richard; Merz, Sarah K.; Reid, K. B. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 230 KB 👁 1 views

Vertices x and y dominate a tournament T if for all vertices z / = x, y, either x beats z or y beats z. Let dom(T ) be the graph on the vertices of T with edges between pairs of vertices that dominate T . We show that dom(T ) is either an odd cycle with possible pendant vertices or a forest of cater