Penta-Extensions of Hereditary Classes of Graphs

Igor E. Zverovich () and Inessa I. Zverovich
Additional contact information
Igor E. Zverovich: The State University of New Jersey
Inessa I. Zverovich: The State University of New Jersey

Journal of Combinatorial Optimization, 2005, vol. 10, issue 2, No 4, 169-178

Abstract: Abstract Penta is the configuration shown in figure 1(a), where continuous lines represent edges and dotted lines represent non-edges. The vertex u in figure 1(a) is called the center of Penta. A graph G is called a pentagraph if every induced subgraph H of G has a vertex v which is not a center of induced Penta in H. The class of pentagraphs is a common generalization of chordal [triangulated] graphs and Mahadev graphs. We construct a polynomial-time algorithm that either find a maximum stable set of G or concludes that G is not a pentagraph. We propose a method for extending α-polynomial hereditary classes based on induced Pentas.

Keywords: pentagraph; stability number; hereditary class (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-005-2271-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:10:y:2005:i:2:d:10.1007_s10878-005-2271-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-005-2271-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().