We show that unless P = NP, this result is best possible with respect to µ(G) by proving that for all integers k ≥3 the problem of determining if P4 decomposes a 2k-regular multigraph with µ(G) ≤⌊ 2k  /  3 ⌋ + 1 is NP-Complete. El-Zanati et al.(2014) showed that for all integers k ≥1, every 6k-regular multigraph with µ(G) ≤2k has a P4-decomposition. We prove that for all integers k ≥2, the problem of determining if P4 decomposes a (2k + 1)-regular graph is NP-Complete. Oksimets (2003) proved that for all integers k ≥3, P4 decomposes a connected 2k-regular graph G if and only if |E(G)| is divisible by 3. We show that P4 decomposes a connected 4-regular multigraph G with µ(G) ≤2 if and only if no 3 vertices of G induce more than 4 edges and |E(G)| is divisible by 3. Heinrich et al.(1999) showed that P4 decomposes a connected 4-regular graph G if and only if |E(G)| is divisible by 3. Let G denote a multigraph with edge set E(G), let µ(G) denote the maximum edge multiplicity in G, and let Pk denote the path on k vertices. The complexity of $P$4-decomposition of regular graphs and multigraphs Ajit Diwan Justine Dion David Mendell Michael Plantholt Shailesh Tipnis. In this article we also estimate and sometimes calculate exactly what is the minimum numbers of colors for each of the Turk's Head Knots, for each relevant modulus $r$. This leads to the question of what is the minimum number of colors it takes to assemble such an $r$-coloring for the knot at issue. Furthermore, it is also known that whenever a knot admits an $r$-coloring using more than one color then all other diagrams of the same knot admit such $r$-colorings (called non-trivial $r$-colorings). In this article we calculate the number of $r$-colorings for the so-called Turk's Head Knots, for each modulus $r$. The number of $r$-colorings is a knot invariant i.e., for each knot, it does not depend on the diagram we are using for counting them. An $r$-coloring of a knot diagram is an assignment of integers modulo $r$ to the arcs of the diagram such that at each crossing, twice the the number assigned to the over-arc equals the sum of the numbers assigned to the under-arcs, modulo $r$. Minimum Number of Colors: the Turk’s Head Knots Case Study Pedro Lopes João Matias.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |