1. Note on p-Competition Graphs and Paths.
- Author
-
Kidokoro, Y., Ogawa, K., Tagusari, S., and Tsuchiya, M.
- Subjects
- *
DIRECTED graphs , *PATHS & cycles in graph theory , *SET theory , *COMPLETE graphs , *INTERSECTION graph theory - Abstract
The p-competition graph Cp(D) of a digraph D = (V,A) is a graph with V (Cp(D)) = V (D), where an edge between distinct vertices x and y if and only if there exist p distinct vertices v1, v2, ..., vp 2 V such that x → vi, y → vi are arcs of the digraph D for each i = 1, 2, ..., p. In this paper, we obtain that a path with order n ≥ 6 is a p-competition graph if and only if n ≥ p + 3. We also show that for a p-competition graph G with no isolated vertices, G+Kn is a p+n-competition graph. And we obtain that a wheel Wn is a p-competition graph if and only if n ≥ p + 3. [ABSTRACT FROM AUTHOR]
- Published
- 2018