1999 | OriginalPaper | Buchkapitel
Dihamiltonian Decomposition of Regular Graphs with Degree Three
verfasst von : Jung-Heum Park, Hee-Chul Kim
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the dihamiltonian decomposition problem for 3- regular graphs. A graph G is dihamiltonian decomposable if in the digraph obtained from G by replacing each edge of G as two directed edges, the set of edges are partitioned into 3 edge-disjoint directed hamiltonian cycles. We suggest some conditions for dihamiltonian decomposition of 3-regular graphs: for a 3-regular graph G, it is dihamiltonian decomposable only if it is bipartite, and it is not dihamiltonian decomposable if the number of vertices is a multiple of 4. Applying these conditions to interconnection network topologies, we investigate dihamiltonian decomposition of cubeconnected cycles, chordal rings, etc.