A note on domination and independence-domination numbers of graphs

Milanič, Martin

ENG

Prijava

Prva stran / Izpis gradiva

Izpis gradiva

A- | A+ | Natisni

Naslov:	A note on domination and independence-domination numbers of graphs
Avtorji:	ID Milanič, Martin (Avtor)
Datoteke:	RAZ_Milanic_Martin_i2013.pdf (300,57 KB) MD5: 653E076C3F1DE2F04B4C14DB3DD5D0BA
Jezik:	Angleški jezik
Vrsta gradiva:	Neznano
Tipologija:	1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija:	ZUP - Založba Univerze na Primorskem
Opis:	Vizing's conjecture is true for graphs $G$ satisfying $\gamma^i(G) = \gamma(G)$ , where $\gamma(G)$ is the domination number of a graph $G$ and $\gamma^i(G)$ is the independence-domination number of $G$ , that is, the maximum, over all independent sets $I$ in $G$ , of the minimum number of vertices needed to dominate $I$ . The equality $\gamma^i(G) = \gamma(G)$ is known to hold for all chordal graphs and for chordless cycles of length $0 \pmod{3}$ . We prove some results related to graphs for which the above equality holds. More specifically, we show that the problems of determining whether $\gamma^i(G) = \gamma(G) = 2$ and of verifying whether $\gamma^i(G) \ge 2$ are NP-complete, even if $G$ is weakly chordal. We also initiate the study of the equality $\gamma^i = \gamma$ in the context of hereditary graph classes and exhibit two infinite families of graphs for which $\gamma^i < \gamma$ .
Ključne besede:	Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph
Leto izida:	2013
Št. strani:	str. 89-97
Številčenje:	Vol. 6, no. 1
PID:	20.500.12556/RUP-2624
UDK:	519.17
ISSN pri članku:	1855-3966
COBISS.SI-ID:	1024423764
Datum objave v RUP:	15.10.2013
Število ogledov:	3919
Število prenosov:	131
Metapodatki:
:	MILANIČ, Martin, 2013, A note on domination and independence-domination numbers of graphs. V : Ars mathematica contemporanea [na spletu]. Objavljeni znanstveni prispevek na konferenci. 2013. p. 89–97. [Dostopano 16 april 2025]. Pridobljeno s: https://repozitorij.upr.si/IzpisGradiva.php?lang=slv&id=2624 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Iščem podobna dela... Prosim, počakajte...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del zbornika

Naslov:	Ars mathematica contemporanea
COBISS.SI-ID:	16465753

Gradivo je del revije

Naslov:	Ars mathematica contemporanea
Založnik:	Društvo matematikov, fizikov in astronomov, Društvo matematikov, fizikov in astronomov, Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
ISSN:	1855-3966
COBISS.SI-ID:	239049984

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj