A note on domination and independence-domination numbers of graphs

Milanič, Martin

SLO

First page / Show document

Show document

A- | A+ | Print

Title:	A note on domination and independence-domination numbers of graphs
Authors:	ID Milanič, Martin (Author)
Files:	RAZ_Milanic_Martin_i2013.pdf (300,57 KB) MD5: 653E076C3F1DE2F04B4C14DB3DD5D0BA
Language:	English
Work type:	Unknown
Typology:	1.08 - Published Scientific Conference Contribution
Organization:	ZUP - University of Primorska Press
Abstract:	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$ .
Keywords:	Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph
Year of publishing:	2013
Number of pages:	str. 89-97
Numbering:	Vol. 6, no. 1
PID:	20.500.12556/RUP-2624
UDC:	519.17
ISSN on article:	1855-3966
COBISS.SI-ID:	1024423764
Publication date in RUP:	15.10.2013
Views:	3877
Downloads:	131
Metadata:
:	MILANIČ, Martin, 2013, A note on domination and independence-domination numbers of graphs. In : Ars mathematica contemporanea [online]. Published Scientific Conference Contribution. 2013. p. 89–97. [Accessed 5 April 2025]. Retrieved from: https://repozitorij.upr.si/IzpisGradiva.php?lang=eng&id=2624 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Aditivni ohranjevalci rang-permutabilnosti
Additive mappings on symmetric matrices
Lim, M.H.: Additive mappings between Hermitian matrix spaces preserving rank not exceeding one. (English). - [J] Linear Algebra Appl. 408, 259-267 (2005). [ISSN 0024-3795]
Ob otobraženijah, sohranjajuščih immananty
Petek, Tatjana: A note on unitary similarity preserving linear mappings on $B(H)$. (English). - [J] Linear Algebra Appl. 394, 217-224 (2005). [ISSN 0024-3795]

Similar works from other repositories:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a proceedings

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

Record is a part of a journal

Title:	Ars mathematica contemporanea
Publisher:	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

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back