𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On linear and circular structure of (claw, net)-free graphs

✍ Scribed by Andreas Brandstädt; Feodor F. Dragan

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
289 KB
Volume
129
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that every (claw, net)-free graph contains an induced doubly dominating cycle or a dominating pair. Moreover, using LexBFS we present a linear time algorithm which, for a given (claw, net)-free graph, ÿnds either a dominating pair or an induced doubly dominating cycle. We show also how one can use structural properties of (claw, net)-free graphs to solve e ciently the domination, independent domination, and independent set problems on these graphs.

📜 SIMILAR VOLUMES

On factors of 4-connected claw-free grap
On factors of 4-connected claw-free graphs
✍ H. J. Broersma; M. Kriesell; Z. Ryjác̆ek 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian,

On stability of Hamilton-connectedness u
On stability of Hamilton-connectedness under the 2-closure in claw-free graphs
✍ Zdeněk Ryjáček; Petr Vrána 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 1 views

We show that, in a claw-free graph, Hamilton-connectedness is preserved under the operation of local completion performed at a vertex with 2-connected neighborhood. This result proves a conjecture by Bollobás et al.

On the asymptotic structure of sparse tr
On the asymptotic structure of sparse triangle free graphs
✍ Pr�mel, Hans J�rgen; Steger, Angelika 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 567 KB

An important result of Erdos, Kleitman, and Rothschild says that almost every triangle-free graph on n vertices has chromatic number 2. In this paper w e study the asymptotic structure of graphs in y0rb,,,(K3), i.e., in the class of trianglefree graphs on n vertices having rn = rn(n) edges. In parti

On the structure and stability number of
On the structure and stability number of P5- and co-chair-free graphs
✍ Andreas Brandstädt; Raffaele Mosca 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 336 KB

We give a O(nm) time algorithm for the maximum weight stable set (MWS) problem on P5-and co-chair-free graphs without recognizing whether the (arbitrary) input graph is P5and co-chair-free. This algorithm is based on the fact that prime P5-and co-chair-free graphs containing 2K2 are matched co-bipar