Download PDF - Dominant-matching graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Dominant-matching graphs

Authors 1, 1

Affiliations

  1. RUTCOR - Rutgers Center for Operations Research, Rutgers, University of New Jersey, 640 Bartholomew Rd, Piscataway, NJ 08854-8003, USA

Abstract

We introduce a new hereditary class of graphs, the dominant-matching graphs, and we characterize it in terms of forbidden induced subgraphs.

Keywords

ENG
domination number, matching number, hereditary class of graphs

Bibliography

  1. L. Lovász and M. Plummer, Matching Theory, North-Holland Math. Stud. 121, Annals Discrete Math. 29 (North-Holland Publ. Co., Amsterdam-New York; Akad. Kiadó, Budapest, 1986) xxvii+544 pp.
  2. L. Volkmann, On graphs with equal domination and edge independence numbers, Ars Combin. 41 (1995) 45-56.
  3. I.E. Zverovich, k-bounded classes of dominant-independent perfect graphs, J. Graph Theory 32 (1999) 303-310, doi: 10.1002/(SICI)1097-0118(199911)32:3<303::AID-JGT8>3.0.CO;2-B
  4. I.E. Zverovich, Perfect connected-dominant graphs, Discuss. Math. Graph Theory 23 (2003) 159-162, doi: 10.7151/dmgt.1192.
  5. I.E. Zverovich and V.E. Zverovich, A semi-induced subgraph characterization of upper domination perfect graphs, J. Graph Theory 31 (1999) 29-49, doi: 10.1002/(SICI)1097-0118(199905)31:1<29::AID-JGT4>3.0.CO;2-G
  6. I.E. Zverovich and V.E. Zverovich, An induced subgraph characterization of domination perfect graphs, J. Graph Theory 20 (1995) 375-395, doi: 10.1002/jgt.3190200313.
Discussiones Mathematicae Graph Theory
2004/24/3
Export to PBN, Opens in new tab
Pages:
485-490
Main language of publication
English
Received
2003-07-14
Accepted
2003-11-17
Published
2004

DOI: 10.7151/dmgt.1246

Exact and natural sciences