𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Local and global average degree in graphs and multigraphs

✍ Scribed by E. Bertram; P. Erds; P. Horák; J. Širáň; Z. S. Tuza

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
603 KB
Volume
18
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A vertex v of a graph G is called groupie if the average degree t~v~ of all neighbors of v in G is not smaller than the average degree t~G~ of G. Every graph contains a groupie vertex; the problem of whether or not every simple graph on ≧2 vertices has at least two groupie vertices turned out to be surprisingly difficult. We present various sufficient conditions for a simple graph to contain at least two groupie vertices. Further, we investigate the function f(n) = max min~v~ (t~v~/t~G~), where the maximum ranges over all simple graphs on n vertices, and prove that f(n) = 1/42__n__ + o(1). The corresponding result for multigraphs is in sharp contrast with the above. We also characterize trees in which the local average degree t~v~ is constant.

📜 SIMILAR VOLUMES

Improper choosability of graphs and maxi
Improper choosability of graphs and maximum average degree
✍ Frédéric Havet; Jean-Sébastien Sereni 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract Improper choosability of planar graphs has been widely studied. In particular, Škrekovski investigated the smallest integer __g__~k~ such that every planar graph of girth at least __g__~k~ is __k__‐improper 2‐choosable. He proved [9] that 6 ≤ __g__~1~ ≤ 9; 5 ≤  __g__~2~ ≤ 7; 5 ≤ __g__~3

Infinite families of crossing-critical g
Infinite families of crossing-critical graphs with prescribed average degree and crossing number
✍ Drago Bokal 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB 👁 1 views

## Abstract Širáň constructed infinite families of __k__‐crossing‐critical graphs for every __k__⩾3 and Kochol constructed such families of simple graphs for every __k__⩾2. Richter and Thomassen argued that, for any given __k__⩾1 and __r__⩾6, there are only finitely many simple __k__‐crossing‐criti

Average distance in colored graphs
Average distance in colored graphs
✍ Peter Dankelmann; Wayne Goddard; Peter Slater 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

## Abstract For a graph __G__ where the vertices are colored, the __colored distance__ of __G__ is defined as the sum of the distances between all unordered pairs of vertices having different colors. Then for a fixed supply __s__ of colors, __d~s~(G)__ is defined as the minimum colored distance ove

(d,1)-total labeling of graphs with a gi
(d,1)-total labeling of graphs with a given maximum average degree
✍ Mickaël Montassier; André Raspaud 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB 👁 1 views

## Abstract The (__d__,1)‐total number $\lambda \_{d}^{T}(G)$ of a graph __G__ is the width of the smallest range of integers that suffices to label the vertices and the edges of __G__ so that no two adjacent vertices have the same color, no two incident edges have the same color, and the distance

On k-domination and minimum degree in gr
On k-domination and minimum degree in graphs
✍ Odile Favaron; Adriana Hansberg; Lutz Volkmann 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

## Abstract A subset __S__ of vertices of a graph __G__ is __k__‐dominating if every vertex not in __S__ has at least __k__ neighbors in __S__. The __k__‐domination number $\gamma\_k(G)$ is the minimum cardinality of a __k__‐dominating set of __G__. Different upper bounds on $\gamma\_{k}(G)$ are kn

Degree sums for edges and cycle lengths
Degree sums for edges and cycle lengths in graphs
✍ Brandt, Stephan; Veldman, Henk Jan 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 3 views

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference-the length of a longest cycle-of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length be