Connected Domination Number and a New Invariant in Graphs with Independence Number Three
Adding a connected dominating set of vertices to a graph $G$ increases its number of Hadwiger $h(G)$. Based on this obvious property in [2] we introduced a new invariant $\eta(G)$ for which $\eta(G)\leq h(G)$. We continue to study its property. For a graph $G$ with independence number three without...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2021-04-01
|
| Series: | Computer Science Journal of Moldova |
| Subjects: | |
| Online Access: | http://www.math.md/files/csjm/v29-n1/v29-n1-(pp96-104).pdf |
| _version_ | 1811280543283675136 |
|---|---|
| author | Vladimir Bercov |
| author_facet | Vladimir Bercov |
| author_sort | Vladimir Bercov |
| collection | DOAJ |
| description | Adding a connected dominating set of vertices to a graph $G$ increases its number of Hadwiger $h(G)$. Based on this obvious property in [2] we introduced a new invariant $\eta(G)$ for which $\eta(G)\leq h(G)$. We continue to study its property. For a graph $G$ with independence number three without induced chordless cycles $C_7$ and with $n(G)$ vertices, $\eta(G)\geq n(G)/4$. |
| first_indexed | 2024-04-13T01:15:29Z |
| format | Article |
| id | doaj.art-82a05894ab4448d39a0c7a88cadc5f95 |
| institution | Directory Open Access Journal |
| issn | 1561-4042 |
| language | English |
| last_indexed | 2024-04-13T01:15:29Z |
| publishDate | 2021-04-01 |
| publisher | Vladimir Andrunachievici Institute of Mathematics and Computer Science |
| record_format | Article |
| series | Computer Science Journal of Moldova |
| spelling | doaj.art-82a05894ab4448d39a0c7a88cadc5f952022-12-22T03:08:55ZengVladimir Andrunachievici Institute of Mathematics and Computer ScienceComputer Science Journal of Moldova1561-40422021-04-01291(85)96104Connected Domination Number and a New Invariant in Graphs with Independence Number ThreeVladimir Bercov0Department of Mathematics CUNY Borough of Manhattan Community College 199 Chambers St, New York, NY 10007, USAAdding a connected dominating set of vertices to a graph $G$ increases its number of Hadwiger $h(G)$. Based on this obvious property in [2] we introduced a new invariant $\eta(G)$ for which $\eta(G)\leq h(G)$. We continue to study its property. For a graph $G$ with independence number three without induced chordless cycles $C_7$ and with $n(G)$ vertices, $\eta(G)\geq n(G)/4$.http://www.math.md/files/csjm/v29-n1/v29-n1-(pp96-104).pdfdominating setnumber of hadwigerclique numberindependence number |
| spellingShingle | Vladimir Bercov Connected Domination Number and a New Invariant in Graphs with Independence Number Three Computer Science Journal of Moldova dominating set number of hadwiger clique number independence number |
| title | Connected Domination Number and a New Invariant in Graphs with Independence Number Three |
| title_full | Connected Domination Number and a New Invariant in Graphs with Independence Number Three |
| title_fullStr | Connected Domination Number and a New Invariant in Graphs with Independence Number Three |
| title_full_unstemmed | Connected Domination Number and a New Invariant in Graphs with Independence Number Three |
| title_short | Connected Domination Number and a New Invariant in Graphs with Independence Number Three |
| title_sort | connected domination number and a new invariant in graphs with independence number three |
| topic | dominating set number of hadwiger clique number independence number |
| url | http://www.math.md/files/csjm/v29-n1/v29-n1-(pp96-104).pdf |
| work_keys_str_mv | AT vladimirbercov connecteddominationnumberandanewinvariantingraphswithindependencenumberthree |