| Autor: |
Papan, Bishal Basak, Pranto, Protik Bose, Rahman, Md Saidur |
| Předmět: |
|
| Zdroj: |
Computer Journal; May2023, Vol. 66 Issue 5, p1256-1267, 12p |
| Abstrakt: |
A graph |$G = (V,E)$| is called a pairwise compatibility graph (PCG) if it admits a tuple |$(T, d_{min},d_{max})$| of an edge-weighted tree |$T$| of non-negative edge weights with leaf set |$L$| , two non-negative real numbers |$d_{min} \leq d_{max}$| such that each vertex |$u^{\prime} \in V$| represents a leaf |$u \in L$| and |$G$| has an edge |$(u^{\prime},v^{\prime}) \in E$| if and only if the distance between the two leaves |$u$| and |$v$| in the tree |$T$| lies within interval |$[d_{min}, d_{max}]$|. It has been proven that not all graphs are PCGs. A graph |$G$| is called a |$k$| -interval PCG if there exists an edge-weighted tree |$T$| and |$k$| mutually exclusive intervals of non-negative real numbers such that there is an edge between two vertices in |$G$| if and only if the distance between their corresponding leaves in |$T$| lies within any of the |$k$| intervals. It is known that every graph |$G$| is a |$k$| -interval PCG for |$k=|E|$| , where |$E$| is the set of edges of |$G$|. It is thus interesting to know the smallest value of |$k$| for which |$G$| is a |$k$| -interval PCG. In this paper, we show that grid graphs and a subclass of |$3$| D grid graphs are |$2$| -interval PCGs. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
