Defendant/appellant Burlington Northern Railroad Company (hereinafter BN) appeals from the district court’s grant of a permanent injunction in favor of plaintiff/appellee Brotherhood of Locomotive Engineers (hereinafter BLE). BLE had sought declaratory and injunctive relief to enjoin BN from using dogs (hereinafter sniffer dogs) trained to detect the presence of controlled substances on the person or in ■ the personal effects of railroad employees in violation of the notice, negotiation, and mediation requirements imposed by the Railway Labor Act (hereinafter RLA), 45 U.S.C. §§ 152, Seventh and 156 (1982). The question we must resolve is whether BN’s random use of sniffer dogs to detect the presence of controlled substances on the person or in the personal effects of railroad employees presents a “minor” or “major” dispute under the Act, 45 U.S.C. §§ 151-188. This case was consolidated for argument with Brotherhood of Locomotive Eng’rs v. Burlington N. R.R. (9th Cir.1986) [838 F.2d 1087] (hereinafter the Chemical Testing Case), wherein we reviewed BN’s practice of mandatory urine and blood testing practice following an accident or operating rule violation. We affirm because the facts demonstrate that BN’s random use of sniffer dogs is not arguably permitted under the parties’ implied agreement. Therefore, the dispute between the parties is major and must be resolved through mediation and negotiation.
I. FACTS AND PROCEDURAL HISTORY
Following two serious train crashes in April 1984, BN intensified its efforts to enforce Rule G which prohibits the possession or use of alcohol, controlled substances or medications that may adversely affect safety.1 BN contracted for the services of trained handlers and sniffer dogs to detect the presence of controlled substances on its premises.2 The sniffer dogs were sent to workplaces throughout BN’s extensive railway system. Locations were usually selected because of a high incidence of accidents or safety violations. Occasionally, however, the dog handlers responded to tips of controlled substance usage. The district court found that some locations were chosen randomly.
The dogs were used to inspect vehicles in railroad parking lots, and were taken through yard offices and company buildings. During the random searches, the dogs also sniffed the personal effects of engineers coming on duty.3 A BN supervisor would randomly request an engineer to place his grip on the ground and to step back while the dog sniffed around the closed container. The dogs were not ordered to sniff the person of the engineer. If the dog “alerted” on the grip, the supervisor would take the engineer to an office and request that the engineer sign a form consenting to a search. BN security staff would then search the grip, the engineer’s person, and his vehicle. If the engineer *1104refused to consent, he was suspended from service pending an investigation for a possible Rule G violation.4
BLE opposed the random use of sniffer dogs and urged BN to end the practice. BN refused to discuss the issue.
On October 5, 1984, BLE obtained a preliminary injunction preventing BN from using sniffer dogs. On July 81, 1985, after an evidentiary hearing, the district court granted the Brotherhood a permanent injunction under section 6 of the Act, 45 U.S.C. § 156.
The district court rejected as “specious” BN’s claim that deciding the method of detection of safety rule violations falls within BN’s managerial prerogative and thus is not a matter for collective bargaining. Brotherhood of Locomotive Eng’rs v. Burlington N. R.R., 620 F.Supp. 163, 169 (D.Mont.1985). The district court noted that the collective bargaining agreements between the parties made no reference to Rule G, nor to any specific method of detecting alcohol or controlled substance abuse, nor to blood and urine tests. The court found, however, that the procedure for the detection and investigation of alcohol or controlled substance abuse adopted by the railroad, and acquiesced in by the union, had existed over a substantial period of time and had become an implied provision or condition of the collective bargaining agreement. Id. at 170. The district court also found that the procedure employed by the railroad to implement Rule G consisted of sensory observation by a supervisor of objective symptoms of alcohol or substance abuse, such as slurred speech, staggered walk, alcoholic breath, followed by a voluntary blood or urine test, if the employee wished to clear himself of suspicion. The court held that because the evidence presented at the hearing demonstrated that the practice of randomly searching the personal effects of employees was never agreed to, or acquiesced in, by BLE, the dispute was major and not “arguably justified” under the terms of the implied agreement extant between the parties. Id. at 171-72. The district court enjoined BN from attempting to change the implied agreement between the parties with respect to the detection of violations of Rule G.
II. STANDARD OF REVIEW
We review the grant of a permanent injunction for an abuse of discretion. Toussaint v. McCarthy, 801 F.2d 1080, 1087 (9th Cir.1986), cert. denied, — U.S. -, 107 S.Ct. 2462, 95 L.Ed.2d 871. Abuse of discretion occurs if the district court rests its conclusion on clearly erroneous factual findings or if its decision relies on erroneous legal conclusions. Sports Form, Inc. v. UPI, 686 F.2d 750, 752 (9th Cir.1982); Miss Universe, Inc. v. Flesher, 605 F.2d 1130, 1133-34 (9th Cir.1979).
III. ANALYSIS
BN has presented three discrete and inconsistent theories in support of its contention that the district court abused its discretion in granting a permanent injunction. First, BN claims the use of sniffer dogs is not a proper subject for collective bargaining. Secondly, the railroad contends that use of sniffer dogs has become an implied term of the collective bargaining agreements through past practice. Finally, it is asserted that the use of sniffer dogs was omitted from the collective bargaining agreements and does not create new rights. The record does not support any of these arguments. We analyze each theory under separate headings.
*1105 A.Managerial Prerogative
BN contends that since no provision of the collective bargaining agreement between the parties restricts the methods or procedures for detecting violations of Rule G, any procedure it chooses to employ is a matter within BN’s managerial prerogative. Therefore, BN reasons, its unilateral implementation of a particular method of detection, such as the use of sniffer dogs, is not a labor dispute under the Act.
This claim lacks merit. As discussed below, because of the existence of an implied agreement regarding the procedures BN may employ in detecting alcohol and substance abuse, BN’s choice of methods to detect violations of Rule G is not a matter of managerial prerogative.5 Accord, Brotherhood of Maintenance of Way Employees, Lodge 16 v. Burlington N. R.R., 802 F.2d 1016, 1021, n. 21 (8th Cir.1986) (summarily rejecting BN’s management prerogative in a related case).
B.The Dog Sniffing Practice Is Not Arguably Justified
BN contends that even if its decision to use sniffer dogs is not a matter of managerial prerogative, the challenged method of detection is only a minor dispute under the Act because the practice is arguably justified by the parties’ implied agreement. We disagree. The parties’ implied agreement required a triggering event — the perception of facts that a specific worker had exhibited symptoms of the use of alcohol or a controlled substance — before further investigation could be undertaken. The use of the sniffer dogs was not triggered by an observation that a specific individual was exhibiting objective symptoms of the use of alcohol or a controlled substance. It is quite true that the choice of the location of a search was not always random. The district court found, however, that the selection of the individual to be searched was random.
Beyond this, under the implied agreement, an investigation was permitted to determine prior consumption of alcohol or controlled substances. The district court found that “[t]he practice which evolved over time was one premised upon a determination, through sensory observation, that cause existed to believe a particular employee was under the influence of a substance prohibited by Rule G.” Brotherhood of Locomotive Eng’rs, 620 F.Supp. at 170 (emphasis added). Additionally, the court determined that “[i]f, on the basis of his observations, a supervisor concluded that an on-duty employee was under the influence of a prohibited substance, the supervisor would conduct a further investigation and, if necessary, ultimately initiate the appropriate disciplinary procedures.” Id. (emphasis added). Thus, the implied terms of the collective bargaining agreements did not include a search for the possession of alcohol or controlled substances to prevent future use. Therefore, the random use of sniffer dogs by BN to detect possession of controlled substances, in the absence of objective facts demonstrating prior use, is not arguably permitted under the implied agreement.
C.“Omitted Case”
BN contends that since there is no specific provision in the collective bargaining agreements limiting the methods of detecting violations of Rule G, the use of dogs to detect the possession of a controlled substance is an “omitted case” under Ry. Labor Executives Ass’n v. Atchison, T. & S.F. Ry. Co., 430 F.2d 994 (9th Cir.1970), cert. denied, 400 U.S. 1021, 91 S.Ct. 582, 27 L.Ed.2d 632 (1971). BN’s reliance on Atchison is misplaced.
The term “omitted case” first appears in Elgin, J. & E. Ry. Co. v. Burley, 325 U.S. 711, 65 S.Ct. 1282, 89 L.Ed. 1886 (1945). In defining a minor dispute, the Supreme Court instructed as follows:
[A minor] dispute relates either to the meaning or proper application of a particular provision with reference to a specific situation or to an omitted case. In the *1106latter event the claim is founded upon some incident of the employment relation, or asserted one, independent of those covered by the collective agreement, e.g., claims on account of personal injuries.
Id. at 723, 65 S.Ct. at 1290 (emphasis added); cf. Airline Flight Attendants in Service of Int’l Texas Airlines, Inc. v. Texas Int’l Airlines, 411 F.Supp. 954, 959 (S.D.Tex.1976) (the court held that the “dispute is arguably covered by the parties’ collective bargaining agreement[,]” id. at 960, and in dictum discussed the omitted case theory, id. at 961), aff'd mem., 566 F.2d 104 (5th Cir.1978). The Supreme Court has not subsequently applied the term “omitted case.”
BN argues that “since the written agreements are admittedly silent, [the dispute] should be considered an omitted case, and thus a minor dispute referrable to the Adjustment Board.” Adoption of this bold and novel proposition would eliminate the major dispute resolution procedures of the Act. Under the Act, as interpreted by this court, major disputes involve “efforts to secure new rights” not now part of a collective bargaining agreement. Int’l Ass’n of Machinists & Aerospace Workers v. Aloha Airlines, Inc., 776 F.2d 812, 815 (9th Cir.1985). BN’s assertion of the right to use sniffer dogs to search the personal effects of its employees for possession of a controlled substance is not a part of the express or implied terms of the existing collective bargaining agreements. Therefore, the issue presents a major dispute.
In Atchison, railway employees brought an action for damages for loss of work resulting from discontinuance of the operation of four interstate trains by the railroad. 430 F.2d at 995. The employees attempted to evade the Railway Labor Act by styling their claim as a tort action for the violation of a statutory duty, and not therefore, a matter within the exclusive jurisdiction of the Adjustment Board. Id. at 997. The district court dismissed the action because the challenged conduct raised a minor dispute “properly cognizable by the National Railroad Adjustment Board under provisions of the Railway Labor Act, 45 U.S.C. §§ 151-162.” Id. at 996. We agreed with the district court and affirmed. Id. at 997. We noted that “[i]t is also undisputed that this is a ‘minor dispute’ in the sense that ‘the claim is to rights accrued, not merely to have new ones created for the future.’ ” Id. at 996 (quoting Elgin, 325 U.S. at 723, 65 S.Ct. at 1290) (emphasis added). Because it was “undisputed” that the dispute was minor, it was not necessary for us to explicate the factual theory supporting this finding. Nevertheless, our opinion contains the following explanatory dictum:
Here the collective agreements make no specific provision for the payment of wages following discontinuance of a train. However, nothing in the agreements exclude such protection for the affected employees. Whether such a provision was omitted because the parties relied on the language of the Interstate Commerce Act, the ‘usage, custom, and practice’ of the industry, or whether it was rejected following negotiation does not appear in the record and is a matter requiring the expertise of the Adjustment Board.
Atchison, 430 F.2d at 996 (citations omitted). Unlike the procedural posture of the case presented to us in Atchison, where we dismissed the action on jurisdictional grounds, this matter is before us after a trial on the merits. Thus, we have a record regarding the “usage, custom, and practice of the industry.” We need not speculate as to BN’s theory or the factual bases for the district court’s holding. BN did not contend before the district court that the use of sniffer dogs to detect possession of a controlled substance was omitted from the collective bargaining agreements because the parties relied on the language of a statute to support the use of sniffer dogs. It cannot do so now for the first time on this appeal. We need not guess whether the parties relied on custom, usage, and practice concerning the procedures followed by BN. The trial court heard evidence on this factual issue and found that there was an implied agreement between the parties based on custom and practice. *1107Brotherhood, of Locomotive Eng’rs, 620 F.Supp. at 170. The district court expressly found that the procedures used by BN and acquiesced in by the Brotherhood did not include the use of sniffer dogs for the random detection of the possession of a controlled substance. Id. at 171-72. The facts support this finding. We review findings of fact following the granting of a permanent injunction under the clearly erroneous standard.
The district court’s determination that the implied agreement did not arguably justify the use of sniffer dogs was not clearly erroneous. Furthermore, the fact that there was an implied agreement covering the procedure to be used in detecting Rule G violations demonstrates that this subject matter was not “omitted” from the collective bargaining agreement.
BN also argues that the use of sniffer dogs was not random. This, too, presents a question of fact which was resolved against BN by the district court. The facts, while conflicting, support the court’s finding that the searches of the personal effects of individual employees were random. The record contains evidence that the dogs were used to sniff the personal effects of railroad workers notwithstanding the fact that there was no evidence that the specific individual had used or was then in the possession of a prohibited substance. Evidence presented by BN showed that on some occasions the dogs were sent to locations where there had been a high incidence of accidents or safety and operating rule violations. No proof was offered, however, that BN supervisors were aware, prior to the search, that each person, whose personal effects were subjected to dog sniffing at such places, had a controlled substance in his possession or was observed to be under the influence of a controlled substance. The district court’s finding that the searches were random is not clearly erroneous.
The district court did not abuse its discretion in granting an injunction. The use of sniffer dogs presented a major dispute.
The judgment is AFFIRMED.
. Rule G provides:
The use of alcoholic beverages, intoxicants, narcotics, marijuana, or other controlled substances by employees subject to duty, or their possession or use while on duty or on company property, is prohibited. Employees must not report for duty under the influence of any marijuana or other controlled substances, or medication, including those prescribed by a doctor, that may in any way adversely affect their alertness, coordination, reaction, response or safety.
. There was evidence that after 1977, BN had occasionally used sniffer dogs to detect controlled substances. A dog handler testified that he had conducted searches using sniffer dogs for controlled substances on BN property on ten occasions prior to 1982. These searches included a search of a crewmember’s personal effects. BN records indicate that between May 1984 and October 1984, BN spent over $90,000 on sniffer dogs, including $36,000 for September alone.
.Engineers and train crews frequently have to spend time away from home as part of their duty. These employees carry their personal belongings in grips.
. Documentary evidence submitted to the district court showed that the dog teams operated in 50 locations in 17 states between May 1984 and October 1984 when the district court preliminarily enjoined the program. The dogs checked the personal effects of approximately 1000 train crew, including 250 engineers. The dogs alerted on the grips of 15 engineers; the subsequent searches did not disclose the presence of controlled substances. The dogs alerted on the grips of 61 non-engineer crewmembers; four positive searches ensued: one produced a bottle of alcohol, three uncovered controlled substances. Uncontroverted BN evidence showed a 26% increase in Rule G violation detections in the five months of the program over the first four months of 1984. In the same period, accidents and safety-related rule violations decreased by 52%.
. We express no opinion as to whether measures such as those imposed by BN in this case could be justified as an exercise of managerial prerogative in the absence of an implied agreement.