The solution to Dirack and Ore-type graph packing problems is presented. For any n-vertex graph G with an assigned maximum degree then G packs with a cycle of length n. The generalization of Dirac's theorem to packing of general graphs states that for a natural number greater than or equal to 3 and G an n-vertex graph with maximum edge-average degree smaller than 3, then G has Cn cycles. It is also proved that the two graphs G1 and G2 pack if 2ΔG1G2≯n. The maximum edge-average degree of a graph is related to the maximum degree of the line graph L(G), and any bound on maximum edge-average degree is a bound on Δ(L(G)). Ore-type analogue states that every graph G has two graphs pack for an equitable coloring with k colors for any k≥maximum edge-average degree.
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics