On the number of irregular assignments on a graph
| Author(s): | G. Ebert, J. Hemmeter, F. Lazebnik, Andrew Woldar |
|---|---|
| Year of Publication: | 1991 |
| Journal Title: | Discrete Math |
| ISSN: | 0012365X |
| Volume: | 93 |
| Issue: | 2 |
| Date (MM/DD/YYYY): | 11/25/1991 |
| Start Page: | 131 |
| End Page: | 142 |
| Abstract: |
Let G be a simple graph which has no connected components isomorphic to K1 or K2, and let + be the set of positive integers. A function is called an assignment on G, and for an edge e of G, ω(e) is called the weight of e. We say that w is of strength s if s = max{ω(e): e ε E(G)}. The weight of a vertex in G is defined to be the sum of the weights of its incident edges. We call assignment w irregular if distinct vertices have distinct weights. Let Irr(G,λ) be the number of irregular assignments on G with strength at most λ. We prove that
|Irr(G, λ) − λq+ c1λq−1|= O(λq−2), λ→∞ where q =|E(G)| and c1 is a constant depending only on G. An explicit expression for c1 is given. Analysis of this expression enables us to determine which graph with q edges has the least number of irregular assignments of strength at most λ, for λ sufficiently large. |
| Link to Full Text: | Full Text |
