Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
565 6 |
Ultima descărcare din IBN: 2020-11-06 21:50 |
Căutarea după subiecte similare conform CZU |
519.1 (117) |
Analiză combinatorică. Teoria grafurilor (115) |
SM ISO690:2012 BERCOV, Vladimir. Connected Dominating Sets and a New Graph Invariant. In: Computer Science Journal of Moldova, 2019, nr. 1(79), pp. 23-33. ISSN 1561-4042. |
EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
Computer Science Journal of Moldova | ||||||
Numărul 1(79) / 2019 / ISSN 1561-4042 /ISSNe 2587-4330 | ||||||
|
||||||
CZU: 519.1 | ||||||
Pag. 23-33 | ||||||
|
||||||
Descarcă PDF | ||||||
Rezumat | ||||||
Based on concept of connected dominating sets of a simple graph G we introduce a new invariant (G) which does not exceed the number of Hadwiger. The Nordhaus-Gaddum inequalities are: (G)(G) ≥ n(G) and (G) + (G) ≤ 6n(G)/5. For values of chromatic number (G) ≤ 4 we prove (G) ≥ (G). We put forward the hypothesis: the last inequality holds for all simple graphs G. |
||||||
Cuvinte-cheie dominating set, number of Hadwiger, chromatic number, Nordhaus-Gaddum inequalities. |
||||||
|