TY - JOUR

T1 - p-competition numbers

AU - Kim, Suh ryung

AU - McKee, Terry A.

AU - McMorris, F. R.

AU - Roberts, Fred S.

N1 - Funding Information:
Sub-ryung Kim and Fred S. Roberts thank the Air Force Office of Scientific Research for its support under grants AFOSR-85-0271 and AFOSR-89-0066 to Rutgers University. Terry A. McKee thanks the Office of Naval Research for its support under grant number NOOO14-X8-K-0163t o Wright State University. F.R. McMorris thanks the Office of Naval Research for its support under grant number NOOO14-89-J-1643t o the University of Louisville. The authors thank Denise Sakai and Chi Wang for a variety of useful comments.

PY - 1993/9/21

Y1 - 1993/9/21

N2 - If D = (V, A>) is a digraph, its p-competition graph has vertex set V and an edge between x and y if and only if there are distinct vertices a1,...,ap in D with (x, ai) and (y,ai) arcs of D for each i ≤ p. The p-competition number of a graph is the smallest number of isolated vertices which need to be added in order to make it a p-competition graph. These notions generalize the widely studied p = 1 case, where they correspond to ordinary competition graphs and competition numbers. We obtain bounds on the p-competition number in terms of the ordinary competition number, and show that, surprisingly, the p-competition number can be arbitrarily smaller than the ordinary competition number.

AB - If D = (V, A>) is a digraph, its p-competition graph has vertex set V and an edge between x and y if and only if there are distinct vertices a1,...,ap in D with (x, ai) and (y,ai) arcs of D for each i ≤ p. The p-competition number of a graph is the smallest number of isolated vertices which need to be added in order to make it a p-competition graph. These notions generalize the widely studied p = 1 case, where they correspond to ordinary competition graphs and competition numbers. We obtain bounds on the p-competition number in terms of the ordinary competition number, and show that, surprisingly, the p-competition number can be arbitrarily smaller than the ordinary competition number.

UR - http://www.scopus.com/inward/record.url?scp=43949164226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=43949164226&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(93)90160-P

DO - 10.1016/0166-218X(93)90160-P

M3 - Article

AN - SCOPUS:43949164226

SN - 0166-218X

VL - 46

SP - 87

EP - 92

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

ER -