Cycles and p-competition graphs

Details Cycles and p-competition graphs Cycles and p-competition graphs

2009-05-25

arxiv.org/abs/0905.3942v1

Congressus Numerantium 196 (2009) 23-30

Mathematics

Combinatorics

8 pages, 1 figure

Scientific paper

The notion of p-competition graphs of digraphs was introduced by S-R. Kim, T. A. McKee, F. R. McMorris, and F. S. Roberts [p-competition graphs, Linear Algebra Appl., 217 (1995) 167--178] as a generalization of the competition graphs of digraphs. Let p be a positive integer. The p-competition graph C_p(D) of a digraph D=(V,A) is a (simple undirected) graph which has the same vertex set V and has an edge between distinct vertices x and y if and only if there exist p distinct vertices v_1, ..., v_p in V such that (x,v_i), (y,v_i) are arcs of the digraph D for each i=1, ..., p. In this paper, given a cycle of length n, we compute exact values of p in terms of n such that it is a p-competition graph, which generalizes the results obtained by Kim et al. We also find values of p in terms of n so that its complement is a p-competition graph.

Affiliated with

Also associated with

No associations

Rating

Cycles and p-competition graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cycles and p-competition graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cycles and p-competition graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-294185