𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Moments of graphs in monotone families

✍ Scribed by Zoltán Füredi; André Kündgen

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
114 KB
Volume
51
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The __k__th moment of the degree sequence d~1~ ≥ d~2~ ≥ …d~n~ of a graph G is $\mu _k(G)={1\over n}{\sum}{d_i^k}$. We give asymptotically sharp bounds for μ~k~(G) when G is in a monotone family. We use these results for the case k = 2 to improve a result of Pach, Spencer, and Tóth [15]. We answer a question of Erdős [9] by determining the maximum variance ${\mu _2(G)-\mu _1^2(G)}$ of the degree sequence when G is a triangle‐free n‐vertex graph. © 2005 Wiley Periodicals, Inc.

📜 SIMILAR VOLUMES

Monotone drawings of planar graphs
Monotone drawings of planar graphs
✍ János Pach; Géza Tóth 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

## Abstract Let __G__ be a graph drawn in the plane so that its edges are represented by __x__‐monotone curves, any pair of which cross an even number of times. We show that __G__ can be redrawn in such a way that the __x__‐coordinates of the vertices remain unchanged and the edges become non‐cross

Families of Regular Graphs in Regular Ma
Families of Regular Graphs in Regular Maps
✍ Steve Wilson 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 227 KB

The question of when a given graph can be the underlying graph of a regular map has roots a hundred years old and is currently the object of several threads of research. This paper outlines this topic briefly and proves that a product of graphs which have regular embeddings also has such an embeddin

Ramsey Properties of Families of Graphs
Ramsey Properties of Families of Graphs
✍ Ronald Graham; Tomasz Łuczak; Vojtěch Rödl; Andrzej Ruciński 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 106 KB

For a graph F and natural numbers a 1 ; . . . ; a r ; let F ! ða 1 ; . . . ; a r Þ denote the property that for each coloring of the edges of F with r colors, there exists i such that some copy of the complete graph K ai is colored with the ith color. Furthermore, we write ða 1 ; . . . ; a r Þ ! ðb

New families of strongly regular graphs
New families of strongly regular graphs
✍ Yury J. Ionin; Hadi Kharaghani 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB

## Abstract We apply symmetric balanced generalized weighing matrices with zero diagonal to construct four parametrically new infinite families of strongly regular graphs. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 208–217, 2003; Published online in Wiley InterScience (www.interscience.wil

Vertex Ramsey Properties of Families of
Vertex Ramsey Properties of Families of Graphs
✍ Tomasz Łuczak; Andrzej Ruciński; Sebastian Urbański 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 118 KB

For graphs F, G 1 , ..., G r , we write F Q (G 1 , ..., G r ) if for every coloring of the vertices of F with r colors there exists i, i=1, 2, ..., r, such that a copy of G i is colored with the ith color. For two families of graphs G 1 , ..., G r and H 1 , ..., H s , by .., H s ) for every graph F