Affordable Access

Equistable simplicial, very well-covered, and line graphs

Authors
Journal
Discrete Applied Mathematics
0166-218X
Publisher
Elsevier
Volume
165
Identifiers
DOI: 10.1016/j.dam.2013.01.022
Keywords
  • Equistable Graph
  • Simplicial Graph
  • Very Well-Covered Graph
  • Line Graph
  • Strongly Equistable Graph
  • General Partition Graph
  • Triangle Graph
  • Triangle Condition
  • Polynomial Time Algorithm
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract We verify the conjectures of Mahadev–Peled–Sun and of Orlin, both related to equistable graphs, for the classes of simplicial, very well-covered and line graphs. Our results are based on the combinatorial features of triangle graphs and general partition graphs. In particular, we obtain several equivalent characterizations of equistable simplicial graphs, equistable very well-covered graphs, and equistable line graphs, some of which imply polynomial time recognition algorithms for graphs in these classes.

There are no comments yet on this publication. Be the first to share your thoughts.