✦ LIBER ✦

Subdivisions, parity and well-covered graphs

✍ Scribed by Caro, Yair

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 121 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199705)25:1<85::aid-jgt6>3.0.co;2-e

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is well-covered if every maximal independent set is maximum. This concept, introduced by Plummer in 1970 (J. Combin. Theory 8 (1970)), is the focal point of much interest and current research. We consider well-covered 2-degenerate graphs and supply a structural (and polynomial time algorithm) characterization of the class called 3-separable graphs. Also we consider parity graphs studied by Finbow and Hartnell and answer the question posed by them (Ars. Combin. 40 (1995)) by proving, among other results, that the decision problem: ''given a graph G which is a parity graph, is G also well-covered graph?'' is in the class CO-NPC. In addition we supply some complexity results that answer some problems due to Plummer (

📜 SIMILAR VOLUMES

ModelingK-coteries by well-covered graph

ModelingK-coteries by well-covered graphs

✍ Yamashita, Masafumi; Kameda, Tsunehiko (Tiko) 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 1 views

The concept of k-coterie is useful for achieving k-mutual exclusion in distributed systems. A graph is said to be well covered if any of its maximal independent sets is also maximum. We first show that a graph G is well covered with independence number k if and only if G represents the incidence rel

Well covered simplicial, chordal, and ci

Well covered simplicial, chordal, and circular arc graphs

✍ Prisner, Erich; Topp, Jerzy; Vestergaard, Preben Dahl 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 427 KB 👁 2 views

A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper, we,characterize well covered simplicial, chordal and circular arc graphs.

Tracking the P-NP boundary for well-cove

Tracking the P-NP boundary for well-covered graphs

✍ Sankaranarayana, Ramesh S. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB 👁 1 views

Certain fundamental graph problems like recognition, dominating set, Hamiltonian cycle and path, and clique partition, which are hard for well-covered graphs in general, can be solved efficiently for very well covered graphs. We address the question of how far the class of very well covered graphs c

Parity equivalence in eulerian graphs

✍ Sabidussi, Gert 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 1 views

Given a connected eulerian graph, we consider the question-related to the factorisation of regular graphs of even degree-under what conditions the distance of two edges e, e in an eulerian walk (i.e., the number of edges intervening between e and e ) always is of the same parity. A characterisation

A characterization of Zm-well-covered gr

A characterization of Zm-well-covered graphs of girth 6 or more

✍ Caro, Y.; Hartnell, B. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views

The class of Z m -well-covered graphs, those in which the cardinality of every maximal independent subset of vertices is congruent to the same number modulo m, contains the well-covered graphs as well as parity graphs. Here we consider such graphs, where there is no small cycle present and obtain a

Packing and covering dense graphs

✍ Noga Alon; Yair Caro; Raphael Yuster 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB