Re: A graph theory problem
- From: "Aldar C-F. Chan" <aldar@xxxxxxxxxxxxxxxx>
- Date: Sat, 4 Jun 2005 01:55:25 GMT
>>Hi, I got the following edge labeling problem. Help is greatly
>>appreciated.
>
>>Given a graph G, label its edges E(G) with 1,2,3,..... so that
>>each vertex in V(G) has atmost k labels. Find a labeling
>>method which achieve the minimum number of labels. If this
>>problem hard?
>
> You can't have described the problem correctly. Perhaps you meant
> "at least" rather than "at most"?
>
> Robert Israel israel@xxxxxxxxxxx
> Department of Mathematics http://www.math.ubc.ca/~israel
> University of British Columbia Vancouver, BC, Canada
>
>
Sorry. I didn't check it carefully. I meant atmost but want to
achieve minimum number of repetitions per label.
Overall, I want to label the edges of a graph G with 1,2,3,..... so that
each vertex in V(G) has atmost k labels. Dentoe a label by l_i and
let N(l_i) be the number of repetitions of the label l_i. Find a labeling
method so that max_i N(l_i) is minimum. What's the max_i N(l_i)?
Thanks.
.
- References:
- A graph theory problem
- From: Aldar Chan
- Re: A graph theory problem
- From: Robert Israel
- A graph theory problem
- Prev by Date: Re: Orlow cardinality question
- Next by Date: Re: A graph theory problem
- Previous by thread: Re: A graph theory problem
- Next by thread: Re: A graph theory problem
- Index(es):
Relevant Pages
|
