✦ LIBER ✦

Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices

✍ Scribed by Jerzy Topp

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 816 KB
Volume: 121
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90553-6

No coin nor oath required. For personal study only.

✦ Synopsis

Topp, J., Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices, Discrete Mathematics 12 1 (1993) 199-210.

A set I of vertices of a graph G is an independent set if no two vertices of I are adjacent. A set M of edges of G is an edge dominating set if each edge not in M is adjacent to at least one edge in M. We investigate graphs that have unique minimum edge dominating sets. Moreover, we characterize graphs whose total graphs (line graphs) have unique maximum independent sets of vertices.

📜 SIMILAR VOLUMES

Graphs with unique maximum independent s

Graphs with unique maximum independent sets

✍ Glenn Hopkins; William Staton 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 402 KB

Maximal and maximum independent sets in

Maximal and maximum independent sets in graphs with at most r cycles

✍ Bruce E. Sagan; Vincent R. Vatter 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB 👁 2 views

## Abstract Let __m__(__G__) denote the number of maximal independent sets of vertices in a graph __G__ and let __c__(__n__,__r__) be the maximum value of __m__(__G__) over all connected graphs with __n__ vertices and at most __r__ cycles. A theorem of Griggs, Grinstead, and Guichard gives a formul

Graphs with given odd sets and the least

Graphs with given odd sets and the least number of vertices

✍ Louis Hakimi, S. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 2 views

This note presents a solution to the following problem posed by Chen, Schelp, and Soltés: find a simple graph with the least number of vertices for which only the degrees of the vertices that appear an odd number of times are given.

Graphs with the smallest number of minim

Graphs with the smallest number of minimum cut sets

✍ Derek Smith 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 630 KB

Defective choosability of graphs with no

Defective choosability of graphs with no edge-plus-independent-set minor

✍ Douglas R. Woodall 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB

## Abstract It is proved that, if __s__ ≥ 2, a graph that does not have __K__~2~ + __K__~__s__~ = __K__~1~ + __K__~1, __s__~ as a minor is (__s__, 1)\*‐choosable. This completes the proof that such a graph is (__s__ + 1 − __d__,__d__)\*‐choosable whenever 0 ≤ __d__ ≤ __s__ −1 © 2003 Wiley Periodica

Very rapidly mixing Markov chains for 2Δ

Very rapidly mixing Markov chains for 2Δ-colorings and for independent sets in a graph with maximum degree 4

✍ Michael Molloy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A