Premium
Modeling K ‐coteries by well‐covered graphs
Author(s) -
Yamashita Masafumi,
Kameda Tsunehiko Tiko
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199910)34:3<221::aid-net7>3.0.co;2-m
Subject(s) - mutual exclusion , computer science , independence (probability theory) , independence number , combinatorics , graph , discrete mathematics , mathematics , theoretical computer science , statistics
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 relation among quorums forming a k ‐coterie. We then discuss the problem of constructing k ‐coteries having some desirable properties. We also characterize the well‐covered graphs with independence number 2. © 1999 John Wiley & Sons, Inc. Networks 34: 221–228, 1999