𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Dominating sets and domatic number of circular arc graphs

✍ Scribed by Maurizio A. Bonuccelli

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
513 KB
Volume
12
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Maximum independent sets of circular-arc
Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs
✍ Zheng, S. Q. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 421 KB πŸ‘ 2 views

We present a simple optimal algorithm for the problem of finding maximum independent sets of circular-arc graphs. Given an intersection model S of a circular-arc graph G , our algorithm computes a maximum independent set of G in O ( n ) space and O ( n ) or O(n log n ) time, depending on whether the

Graphs with unique minimum edge dominati
Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices
✍ Jerzy Topp πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 816 KB

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 s

Partial characterizations of circular-ar
Partial characterizations of circular-arc graphs
✍ F. Bonomo; G. DurΓ‘n; L.N. Grippo; M.D. Safe πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 224 KB

## Abstract A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minim