✦ LIBER ✦

A lower bound for groupies in graphs

✍ Scribed by Mackey, John

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 145 KB
Volume: 21
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199603)21:3<323::aid-jgt7>3.0.co;2-s

No coin nor oath required. For personal study only.

✦ Synopsis

A non-isolated vertex of a graph G is called a groupie if the average degree of the vertices connected to it is larger than or equal to the average degree of the vertices in G. An isolated vertex is a groupie only if all vertices of G are isolated. While it is well known that every graph must contain at least one groupie, the graph Kne contains just 2 groupie vertices for n 2 2. In this paper w e derive a lower bound for the number of groupies which shows, in particular, that any graph with 2 or more vertices must contain at least 2 groupies.

📜 SIMILAR VOLUMES

A lower bound for interval routing in ge

A lower bound for interval routing in general networks

✍ Tse, Savio S. H.; Lau, Francis C. M. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

Interval routing is a space-efficient routing method for point-to-point communication networks. The method has drawn considerable attention in recent years because of its being incorporated into the design of a commercially available routing chip. The method is based on proper labeling of edges of t

A lower bound for partial list colorings

✍ Chappell, Glenn G. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 1 views

Let G be an n-vertex graph with list-chromatic number χ . Suppose that each vertex of G is assigned a list of t colors. Albertson, Grossman, and Haas [1] conjecture that at least t n /χ vertices can be colored from these lists. We prove a lower bound for the number of colorable vertices. As a coroll

New upper bounds for the chromatic numbe

New upper bounds for the chromatic number of a graph

✍ Ladislav Stacho 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB 👁 1 views

A lower bound for the crossing number of

A lower bound for the crossing number of Cm × Cn

✍ Gelasio Salazar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 1 views

On equality in an upper bound for domina

On equality in an upper bound for domination parameters of graphs

✍ Favaron, O.; Mynhardt, C. M. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB 👁 2 views

We consider the well-known upper bounds µ(G) ≤ |V (G)|-∆(G), where ∆(G) denotes the maximum degree of G and µ(G) the irredundance, domination or independent domination numbers of G and give necessary and sufficient conditions for equality to hold in each case. We also describe specific classes of gr

A strong lower bound for the Node Weight

A strong lower bound for the Node Weighted Steiner Tree Problem

✍ Engevall, Stefan; G�the-Lundgren, Maud; V�rbrand, Peter 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB 👁 1 views

In this paper, we study the Node Weighted Steiner Tree Problem (NSP). This problem is a generalization of the Steiner tree problem in the sense that vertex weights are considered. Given an undirected graph, the problem is to find a tree that spans a subset of the vertices and is such that the total