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 -