Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 167-169 |
| Number of pages | 3 |
| Journal | Combinatorics Probability and Computing |
| Volume | 16 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 2007 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics