✦ LIBER ✦

Irredundance in inflated graphs

✍ Scribed by Favaron, Odile

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 263 KB
Volume: 28
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199806)28:2<97::aid-jgt3>3.0.co;2-9

No coin nor oath required. For personal study only.

✦ Synopsis

The inflation G I of a graph G with n(G) vertices and m(G) edges is obtained by replacing every vertex of degree d of G by a clique K d . We study the lower and upper irredundance parameters ir and IR of an inflation. We prove in particular that if γ denotes the domination number of a graph, γ(G I ) -ir(G I ) can be arbitrarily large, IR(G I ) ≤ m(G) and IR(G I ) ≤ n 2 (G)/4. These results disprove a conjecture of Dunbar and Haynes (Congr. Num. 118 (1996), 143-154) and answer another open question.

📜 SIMILAR VOLUMES

Irredundance perfect andP6-free graphs

✍ Puech, Jo�l 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 307 KB 👁 1 views

The domination number γ(G) and the irredundance number ir(G) of a graph G have been considered by many authors. It is well known that ir(G) ≤ γ(G) holds for all graphs G, which leads us to consider the concept of irredundance perfect graphs: graphs that have all their induced subgraphs satisfying th

CO-irredundant Ramsey numbers for graphs

✍ E. J. Cockayne; G. MacGillivray; J. Simmons 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 1 views

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

Embedding of graphs in two-irregular gra

Embedding of graphs in two-irregular graphs

✍ M. Axenovich; Z. Füredi 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 1 views

Hamilton cycles in random graphs and dir

Hamilton cycles in random graphs and directed graphs

✍ Colin Cooper; Alan Frieze 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB 👁 2 views

Gauge-invariant perturbations in general

Gauge-invariant perturbations in generalized inflation

✍ S. Matarrese 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 391 KB

One consitlcrs tlic birth and evolution of scalar and tensor gauge-invariant perturbations in "generalized inflationary models", that is cosmological models with a suitable early phase of accelerated expansion. I n this framc the classical analysis that BARDEEN e t al. performed for the standard de