All graphs with at most seven vertices are Pairwise Compatibility Graphs

Details All graphs with at most seven vertices are Pairwise Compatibility Graphs All graphs with at most seven vertices are Pairwise Compatibility Graphs

2012-02-21

arxiv.org/abs/1202.4631v1

Computer Science

Discrete Mathematics

8 pages, 2 figures

Scientific paper

A graph $G$ is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree $T$ and two non-negative real numbers $d_{min}$ and $d_{max}$ such that each leaf $l_u$ of $T$ corresponds to a vertex $u \in V$ and there is an edge $(u,v) \in E$ if and only if $d_{min} \leq d_{T,w} (l_u, l_v) \leq d_{max}$ where $d_{T,w} (l_u, l_v)$ is the sum of the weights of the edges on the unique path from $l_u$ to $l_v$ in $T$. In this note, we show that all the graphs with at most seven vertices are PCGs. In particular all these graphs except for the wheel on 7 vertices $W_7$ are PCGs of a particular structure of a tree: a centipede.

Affiliated with

Also associated with

No associations

Rating

All graphs with at most seven vertices are Pairwise Compatibility 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 All graphs with at most seven vertices are Pairwise Compatibility Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and All graphs with at most seven vertices are Pairwise Compatibility Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-423515