On Vizing's conjecture

Brešar, Boštjan

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	On Vizing's conjecture
Authors:	ID Brešar, Boštjan (Author)
Files:	Discussiones_Mathematicae_Graph_Theory_2001_Bresar_On_Vizing_s_conjecture.pdf (126,98 KB) MD5: 286C4062475D3BCDAD7F938289E2AA70 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1129
Language:	English
Work type:	Scientific work
Typology:	1.01 - Original Scientific Article
Organization:	FKBV - Faculty of Agriculture and Life Sciences
Abstract:	A dominating set $D$ gor a graph $G$ is a subset $V(G)$ such that any vertex in $V(G)-D$ has a neighbor in $D$ , and a domination number $\gamma(G)$ is the size of a minimum dominating set for $G$ . For the Cartesian product $G \Box H$ Vizing's conjecture states that $\gamma(G \Box H) \ge \gamma(G)\gamma(H)$ for every pair of graphs $G,H$ . In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when $\gamma(G) = \gamma(H) = 3$ .
Keywords:	mathematics, graph theory, graph, Cartesian product, domination number
Publication status:	Published
Publication version:	Version of Record
Year of publishing:	2001
Number of pages:	str. 5-11
Numbering:	Letn. 21, št. 1
PID:	20.500.12556/DKUM-65351
ISSN:	1234-3099
UDC:	519.17
ISSN on article:	1234-3099
COBISS.SI-ID:	11010137
NUK URN:	URN:SI:UM:DK:PXU92DXH
Publication date in DKUM:	31.03.2017
Views:	1520
Downloads:	125
Metadata:
Categories:	Misc.
:	BREŠAR, Boštjan, 2001, On Vizing’s conjecture. Discussiones mathematicae : Graph theory [online]. 2001. Vol. 21, no. 1, p. 5–11. [Accessed 28 March 2025]. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=65351 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:

Sequential afatinib and osimertinib in patients with EGFR mutation-positive non-small-cell lung cancer
Sequential treatment with afatinib and osimertinib in patients with EGFR mutation-positive non-small-cell lung cancer
Selpercatinib in RET fusion-positive non-small-cell lung cancer (SIREN)
Trans-esophageal endobronchial ultrasound-guided needle aspiration (EUS-B-NA)
Access to novel drugs for non-small cell lung cancer in Central and Southeastern Europe

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 journal

Title:	Discussiones mathematicae : Graph theory
Shortened title:	Discuss. Math., Graph Theory
Publisher:	Technical University Press
ISSN:	1234-3099
COBISS.SI-ID:	7487065

Licences

License:	CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Link:	http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:	The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:	31.03.2017

Secondary language

Language:	Slovenian
Title:	O Vizingovi domnevi
Abstract:	Dominirajoča množica $D$ grafa $G$ je taka podmnožica množice $V(G)$ , za katero ima vsaka točka iz množice $V(G)-D$ kako sosedo v $D$ ; dominantno število $\gamma(G)$ pa je velikost najmanjše dominirajoče množice grafa $G$ . Za kartezični produkt grafov $G \Box H$ Vizingova domneva trdi, da je $\gamma(G \Box H) \ge \gamma(G)\gamma(H)$ , kjer sta $G$ in $H$ poljubna grafa. V članku vpeljemo nov koncept, ki posploši običajno dominacijo grafov in dokažemo, da domneva drži v promeru, ko je $\gamma(G) = \gamma(H) = 3$ .
Keywords:	matematika, teorija grafov, graf, kartezični produkt, dominantno število

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back