𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The irredundance number and maximum degree of a graph

✍ Scribed by B. Bollobás; E.J. Cockayne

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
104 KB
Volume
49
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A vertex x in a subset X of vertices of an undirected graph is redundant if its dosed neighborhood is contained in the union of closed neighborhoods of vertices of X-{x}. In the context of a communications network, this means that any vertex that may receive communications from X may also be irdormed from X-{x}. The irredundance number it(G) is the minimum cardinaiity taken over all maximal sets of vertices having no redundancies. In this note we show that ir(G) ~> nl(2A -1) for a graph G having n vertices and maximum degree A.

📜 SIMILAR VOLUMES

The total chromatic number of graphs hav
The total chromatic number of graphs having large maximum degree
✍ A.J.W. Hilton; H.R. Hind 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 935 KB

Hilton, A.J.W. and H.R. Hind, The total chromatic number ofgraphs having large maximum degree, Discrete Mathematics 117 (1993) 127-140. The total colouring conjecture is shown to be correct for those graphs G having d(G)>21 V(G)I.

Total chromatic number of planar graphs
Total chromatic number of planar graphs with maximum degree ten
✍ Weifan Wang 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB 👁 1 views

## Abstract In this article we prove that the total chromatic number of a planar graph with maximum degree 10 is 11. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 91–102, 2007

On numbers of vertices of maximum degree
On numbers of vertices of maximum degree in the spanning trees of a graph
✍ Jerzy Topp; Preben D. Vestergaard 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 611 KB

For a connected graph G, let ~-(G) be the set of all spanning trees of G and let nd(G) be the number of vertices of maximum degree in G. In this paper we show that if G is a cactus or a connected graph with p vertices and p+ 1 edges, then the set {na(T) : T C ~-(G)) has at most one gap, that is, it

The distribution of the maximum degree o
The distribution of the maximum degree of a random graph
✍ Béla Bollobás 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 184 KB

Consider I:andom graphs with n labelled vertices in which the edges are chosen independently and with a 6lxed probability p, 0 <p C 1. Let y be a fixed real number, q = 1p, and denote by A the maximum degree. Then

The ratio of the irredundance number and
The ratio of the irredundance number and the domination number for block-cactus graphs
✍ Zverovich, V. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB 👁 2 views

Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43-56] and Bollobás and Cock- ayne [J. Graph Theory (1979) 241-249] proved independently that γ(G) < 2ir(G) for