Study of Graph Partitions Approach satisfies Vizing's Conjecture
For a graph G(V,E) , a subset of vertices D is a dominating set if for each vertex 12x∈"> V either 12x∈D"> , or x is adjacent to at least one vertex of D . The domination number , 12خ³G, "> is the order of smallest dominating set of G . In [7], Vizing conjectured t...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Arabic |
| Published: |
Tishreen University
2019-02-01
|
| Series: | مجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية |
| Online Access: | http://journal.tishreen.edu.sy/index.php/bassnc/article/view/3780 |
| _version_ | 1797410366849810432 |
|---|---|
| author | جميل محمد |
| author_facet | جميل محمد |
| author_sort | جميل محمد |
| collection | DOAJ |
| description |
For a graph G(V,E) , a subset of vertices D is a dominating set if for each vertex 12x∈"> V either 12x∈D"> , or x is adjacent to at least one vertex of D . The domination number , 12خ³G, "> is the order of smallest dominating set of G . In [7], Vizing conjectured that 12خ³Gأ—H ≥ خ³Gأ—خ³H"> for any two graphs G and H , where G×H denotes their Cartesian product . This conjecture is still open .
In this paper , we investigate following relations, if a graph H has a D-partition then it also has a K-partition, and if H has a K-partition , then Vizing's conjecture is satisfied for any graph G , after that, every cycle 12Cn , n≥3"> , has a K-partition. Moreover, if H has a K-partition , then H satisfies the following relations 12خ³H≤2"> , 12P2H=خ³H"> and H is a perfect-dominated graph .
|
| first_indexed | 2024-03-09T04:27:54Z |
| format | Article |
| id | doaj.art-8e864a21de5a4dfc84e661f02f63c324 |
| institution | Directory Open Access Journal |
| issn | 2079-3057 2663-4252 |
| language | Arabic |
| last_indexed | 2024-03-09T04:27:54Z |
| publishDate | 2019-02-01 |
| publisher | Tishreen University |
| record_format | Article |
| series | مجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية |
| spelling | doaj.art-8e864a21de5a4dfc84e661f02f63c3242023-12-03T13:38:37ZaraTishreen Universityمجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية2079-30572663-42522019-02-01393Study of Graph Partitions Approach satisfies Vizing's Conjectureجميل محمد For a graph G(V,E) , a subset of vertices D is a dominating set if for each vertex 12x∈"> V either 12x∈D"> , or x is adjacent to at least one vertex of D . The domination number , 12خ³G, "> is the order of smallest dominating set of G . In [7], Vizing conjectured that 12خ³Gأ—H ≥ خ³Gأ—خ³H"> for any two graphs G and H , where G×H denotes their Cartesian product . This conjecture is still open . In this paper , we investigate following relations, if a graph H has a D-partition then it also has a K-partition, and if H has a K-partition , then Vizing's conjecture is satisfied for any graph G , after that, every cycle 12Cn , n≥3"> , has a K-partition. Moreover, if H has a K-partition , then H satisfies the following relations 12خ³H≤2"> , 12P2H=خ³H"> and H is a perfect-dominated graph . http://journal.tishreen.edu.sy/index.php/bassnc/article/view/3780 |
| spellingShingle | جميل محمد Study of Graph Partitions Approach satisfies Vizing's Conjecture مجلة جامعة تشرين للبحوث والدراسات العلمية، سلسلة العلوم الأساسية |
| title | Study of Graph Partitions Approach satisfies Vizing's Conjecture |
| title_full | Study of Graph Partitions Approach satisfies Vizing's Conjecture |
| title_fullStr | Study of Graph Partitions Approach satisfies Vizing's Conjecture |
| title_full_unstemmed | Study of Graph Partitions Approach satisfies Vizing's Conjecture |
| title_short | Study of Graph Partitions Approach satisfies Vizing's Conjecture |
| title_sort | study of graph partitions approach satisfies vizing s conjecture |
| url | http://journal.tishreen.edu.sy/index.php/bassnc/article/view/3780 |
| work_keys_str_mv | AT jmylmḥmd studyofgraphpartitionsapproachsatisfiesvizingsconjecture |