scroll identifier for mobile
main-content

## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

11.05.2018 | Ausgabe 2/2018

# Perfect graphs involving semitotal and semipaired domination

Zeitschrift:
Journal of Combinatorial Optimization > Ausgabe 2/2018
Autoren:
Teresa W. Haynes, Michael A. Henning
Wichtige Hinweise
T. W. Haynes: Research supported in part by the University of Johannesburg.
M. A. Henning: Research supported in part by the University of Johannesburg and the South African National Research Foundation.

## Abstract

Let G be a graph with vertex set V and no isolated vertices, and let S be a dominating set of V. The set S is a semitotal dominating set of G if every vertex in S is within distance 2 of another vertex of S. And, S is a semipaired dominating set of G if S can be partitioned into 2-element subsets such that the vertices in each 2-set are at most distance two apart. The semitotal domination number $$\gamma _\mathrm{t2}(G)$$ is the minimum cardinality of a semitotal dominating set of G, and the semipaired domination number $$\gamma _\mathrm{pr2}(G)$$ is the minimum cardinality of a semipaired dominating set of G. For a graph without isolated vertices, the domination number $$\gamma (G)$$, the total domination $$\gamma _t(G)$$, and the paired domination number $$\gamma _\mathrm{pr}(G)$$ are related to the semitotal and semipaired domination numbers by the following inequalities: $$\gamma (G) \le \gamma _\mathrm{t2}(G) \le \gamma _t(G) \le \gamma _\mathrm{pr}(G)$$ and $$\gamma (G) \le \gamma _\mathrm{t2}(G) \le \gamma _\mathrm{pr2}(G) \le \gamma _\mathrm{pr}(G) \le 2\gamma (G)$$. Given two graph parameters $$\mu$$ and $$\psi$$ related by a simple inequality $$\mu (G) \le \psi (G)$$ for every graph G having no isolated vertices, a graph is $$(\mu ,\psi )$$-perfect if every induced subgraph H with no isolated vertices satisfies $$\mu (H) = \psi (H)$$. Alvarado et al. (Discrete Math 338:1424–1431, 2015) consider classes of $$(\mu ,\psi )$$-perfect graphs, where $$\mu$$ and $$\psi$$ are domination parameters including $$\gamma$$, $$\gamma _t$$ and $$\gamma _\mathrm{pr}$$. We study classes of perfect graphs for the possible combinations of parameters in the inequalities when $$\gamma _\mathrm{t2}$$ and $$\gamma _\mathrm{pr2}$$ are included in the mix. Our results are characterizations of several such classes in terms of their minimal forbidden induced subgraphs.

### Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit dem Kombi-Abo erhalten Sie vollen Zugriff auf über 1,8 Mio. Dokumente aus mehr als 61.000 Fachbüchern und rund 500 Fachzeitschriften aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit dem Wirtschafts-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 45.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Technik"

Online-Abonnement

Mit dem Technik-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 40.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Zur Ausgabe

## BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

## Whitepaper

- ANZEIGE -

### Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.