Multicolored isomorphic spanning trees in complete graphs
Can a complete graph on an even number n (>4) of vertices be properly edge-colored with n-1 colors in such a way that the edges can be partitioned into edge disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n-1 colors occur among its edges. It is proved that this is...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2002-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/306/pdf |
| _version_ | 1797270193827741696 |
|---|---|
| author | Gregory Constantine |
| author_facet | Gregory Constantine |
| author_sort | Gregory Constantine |
| collection | DOAJ |
| description | Can a complete graph on an even number n (>4) of vertices be properly edge-colored with n-1 colors in such a way that the edges can be partitioned into edge disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n-1 colors occur among its edges. It is proved that this is possible to accomplish whenever n is a power of two, or five times a power of two. |
| first_indexed | 2024-04-25T02:00:23Z |
| format | Article |
| id | doaj.art-2ef6ff1429694abe962680a3cbd41808 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:00:23Z |
| publishDate | 2002-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-2ef6ff1429694abe962680a3cbd418082024-03-07T15:04:54ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502002-01-01Vol. 510.46298/dmtcs.306306Multicolored isomorphic spanning trees in complete graphsGregory Constantine0Department of Mathematics [Pittsburgh]Can a complete graph on an even number n (>4) of vertices be properly edge-colored with n-1 colors in such a way that the edges can be partitioned into edge disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n-1 colors occur among its edges. It is proved that this is possible to accomplish whenever n is a power of two, or five times a power of two.https://dmtcs.episciences.org/306/pdfmulticolored treeorthogonal latin squarescolorful matching[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Gregory Constantine Multicolored isomorphic spanning trees in complete graphs Discrete Mathematics & Theoretical Computer Science multicolored tree orthogonal latin squares colorful matching [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Multicolored isomorphic spanning trees in complete graphs |
| title_full | Multicolored isomorphic spanning trees in complete graphs |
| title_fullStr | Multicolored isomorphic spanning trees in complete graphs |
| title_full_unstemmed | Multicolored isomorphic spanning trees in complete graphs |
| title_short | Multicolored isomorphic spanning trees in complete graphs |
| title_sort | multicolored isomorphic spanning trees in complete graphs |
| topic | multicolored tree orthogonal latin squares colorful matching [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/306/pdf |
| work_keys_str_mv | AT gregoryconstantine multicoloredisomorphicspanningtreesincompletegraphs |