Multidesigns for the graph pair formed by the 6-cycle and 3-prism
<p class="p1">Given two graphs <em>G</em> and <em>H</em>, a (<em>G</em>,<em>H</em>)-multidecomposition of <em>K<sub>n</sub></em> is a partition of the edges of <em>K<sub>n</sub></em> into...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2020-04-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/896 |
| _version_ | 1818531974868893696 |
|---|---|
| author | Yizhe Gao Dan Roberts |
| author_facet | Yizhe Gao Dan Roberts |
| author_sort | Yizhe Gao |
| collection | DOAJ |
| description | <p class="p1">Given two graphs <em>G</em> and <em>H</em>, a (<em>G</em>,<em>H</em>)-multidecomposition of <em>K<sub>n</sub></em> is a partition of the edges of <em>K<sub>n</sub></em> into copies of <em>G</em> and <em>H</em> such that at least one copy of each is used. We give necessary and sufficient conditions for the existence of (C<sub>6</sub>,Ċ<sub>6</sub>)-multidecomposition of <em>K<sub>n</sub></em> where C<sub>6</sub> denotes a cycle of length 6 and C<sub>6</sub> denotes the complement of C<sub>6</sub>. We also characterize the cardinalities of leaves and paddings of maximum (C<sub>6</sub>,Ċ<sub>6</sub>)-multipackings and minimum (C<sub>6</sub>,Ċ<sub>6</sub>)-multicoverings, respectively.</p> |
| first_indexed | 2024-12-11T17:39:28Z |
| format | Article |
| id | doaj.art-6da92cc548c24d048bd2f5ae4f1d6e73 |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-12-11T17:39:28Z |
| publishDate | 2020-04-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-6da92cc548c24d048bd2f5ae4f1d6e732022-12-22T00:56:35ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872020-04-018113314310.5614/ejgta.2020.8.1.10171Multidesigns for the graph pair formed by the 6-cycle and 3-prismYizhe Gao0Dan Roberts1Illinois Wesleyan University, Bloomington, IL, USAIllinois Wesleyan University, Bloomington, IL, USA<p class="p1">Given two graphs <em>G</em> and <em>H</em>, a (<em>G</em>,<em>H</em>)-multidecomposition of <em>K<sub>n</sub></em> is a partition of the edges of <em>K<sub>n</sub></em> into copies of <em>G</em> and <em>H</em> such that at least one copy of each is used. We give necessary and sufficient conditions for the existence of (C<sub>6</sub>,Ċ<sub>6</sub>)-multidecomposition of <em>K<sub>n</sub></em> where C<sub>6</sub> denotes a cycle of length 6 and C<sub>6</sub> denotes the complement of C<sub>6</sub>. We also characterize the cardinalities of leaves and paddings of maximum (C<sub>6</sub>,Ċ<sub>6</sub>)-multipackings and minimum (C<sub>6</sub>,Ċ<sub>6</sub>)-multicoverings, respectively.</p>https://www.ejgta.org/index.php/ejgta/article/view/896graph pair, decomposition, multidecomposition, packing, covering, cycle, prism |
| spellingShingle | Yizhe Gao Dan Roberts Multidesigns for the graph pair formed by the 6-cycle and 3-prism Electronic Journal of Graph Theory and Applications graph pair, decomposition, multidecomposition, packing, covering, cycle, prism |
| title | Multidesigns for the graph pair formed by the 6-cycle and 3-prism |
| title_full | Multidesigns for the graph pair formed by the 6-cycle and 3-prism |
| title_fullStr | Multidesigns for the graph pair formed by the 6-cycle and 3-prism |
| title_full_unstemmed | Multidesigns for the graph pair formed by the 6-cycle and 3-prism |
| title_short | Multidesigns for the graph pair formed by the 6-cycle and 3-prism |
| title_sort | multidesigns for the graph pair formed by the 6 cycle and 3 prism |
| topic | graph pair, decomposition, multidecomposition, packing, covering, cycle, prism |
| url | https://www.ejgta.org/index.php/ejgta/article/view/896 |
| work_keys_str_mv | AT yizhegao multidesignsforthegraphpairformedbythe6cycleand3prism AT danroberts multidesignsforthegraphpairformedbythe6cycleand3prism |