A characterisation of cubic parity graphs
Carregando...
Data
2003
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
A graph is Zm-well-covered if all maximal independent sets have the same
cardinality modulo m. Zm-well-covered graphs generalise well-covered
graphs, those in which all independent sets have the same cardinality. Z2-
well-covered graphs are also called parity graphs. A characterisation of
cubic well-covered graphs was given by Campbell, Ellingham and Royle.
Here we extend this to a characterisation of cubic Zm-well-covered graphs
for all integers m ≥ 2; the most interesting case is m = 2, cubic parity
graphs. Our main technique involves minimal non-well-covered graphs,
and allows us to build our characterisation as an extension of the existing
characterisation of cubic well-covered graphs.
Descrição
Palavras-chave
Citação
BARBOSA, Rommel; ELLINGHAM, M. N. A characterisation of cubic parity graphs. Australasian Journal of Combinatorics, Queensland, v. 28, p. 273-293, 2003.