✦ LIBER ✦

A linear Vizing-like relation relating the size and total domination number of a graph

✍ Scribed by Michael A. Henning

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 77 KB
Volume: 49
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20082

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove that m ≤ Δ (n − γ~t~) for every graph each component of which has order at least 3 of order n, size m, total domination number γ~t~, and maximum degree Δ ≥ 3. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 285–290, 2005

📜 SIMILAR VOLUMES

Erratum to: “A linear vizing-like relati

Erratum to: “A linear vizing-like relation relating the size and total domination number of a graph”

✍ Erfang Shan; Liying Kang; Michael A. Henning 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB

## Abstract The proof of the main theorem in the paper [1] is incorrect as it is missing an important case. Here we complete the proof by giving the missing case. © 2007 Wiley Periodicals, Inc. J Graph Theory 54: 350–353, 2007

A linear vizing-like relation between th

A linear vizing-like relation between the size and the domination number of a graph

✍ Rautenbach, Dieter 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB 👁 2 views

We prove m ≤ ∆n -(∆ + 1)γ for every graph without isolated vertices of order n, size m, domination number γ and maximum degree ∆ ≥ 3. This generalizes a result of Fisher et al., CU-Denver Tech Rep, 1996] who obtained the given bound for the case ∆ = 3.

On the independence number of the Erdős-

On the independence number of the Erdős-Rényi and projective norm graphs and a related hypergraph

✍ Dhruv Mubayi; Jason Williford 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

## Abstract The Erdős‐Rényi and Projective Norm graphs are algebraically defined graphs that have proved useful in supplying constructions in extremal graph theory and Ramsey theory. Their eigenvalues have been computed and this yields an upper bound on their independence number. Here we show that