Mathematics – Combinatorics
Scientific paper
2010-06-14
Congressus Numerantium 202 (2010) 187-194
Mathematics
Combinatorics
8 pages, 2 figures
Scientific paper
S. -R. Kim and F. S. Roberts (2002) introduced the following conditions $C(p)$ and $C'(p)$ for digraphs as generalizations of the condition for digraphs to be semiorders. The condition $C(p)$ (resp. $C'(p)$) is: For any set $S$ of $p$ vertices in $D$, there exists $x \in S$ such that $N^+_D(x) \subseteq N^+_D(y)$ (resp. $N^-_D(x) \subseteq N^-_D(y)$) for all $y \in S$, where $N^+_D(x)$ (resp. $N^-_D(x)$) is the set of out-neighbors (resp. in-neighbors) of $x$ in $D$. The competition graph of a digraph $D$ is the (simple undirected) graph which has the same vertex set as $D$ and has an edge between two distinct vertices $x$ and $y$ if $N^+_D(x) \cap N^+_D(y) \neq \emptyset$. Kim and Roberts characterized the competition graphs of digraphs which satisfy Condition $C(p)$. The competition-common enemy graph of a digraph $D$ is the graph which has the same vertex set as $D$ and has an edge between two distinct vertices $x$ and $y$ if it holds that both $N^+_D(x) \cap N^+_D(y) \neq \emptyset$ and $N^-_D(x) \cap N^-_D(y) \neq \emptyset$. In this note, we characterize the competition-common enemy graphs of digraphs satisfying Conditions $C(p)$ and $C'(p)$.
No associations
LandOfFree
The competition-common enemy graphs of digraphs satisfying Conditions $C(p)$ and $C'(p)$ 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 The competition-common enemy graphs of digraphs satisfying Conditions $C(p)$ and $C'(p)$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The competition-common enemy graphs of digraphs satisfying Conditions $C(p)$ and $C'(p)$ will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-421940