All Graphs with at Most 8 Nodes are 2-interval-PCGs

Abstract

A graph G is a multi-interval PCG if there exist an edge weighted tree T with non-negative real values and disjoint intervals of the non-negative real half-line such that each node of G is uniquely associated to a leaf of T and there is an edge between two nodes in G if and only if the weighted distance between their corresponding leaves in T lies within any such intervals. If the number of intervals is k, then we call the graph a k-interval-PCG; in symbols, G = k-interval-PCG (T, I₁,…, I_k).

It is known that 2-interval-PCGs do not contain all graphs, and the smallest known graph outside this class has 135 nodes. Here, we prove that all graphs with at most 8 nodes are 2-interval-PCGs, so doing one step towards the determination of the smallest value of n such that there exists an n node graph that is not a 2-interval-PCG.

Keywords

Pairwise Compatibilty Graphs Multi-Interval PCGs.

Get full access to this article

View all access options for this article.

References

Ahmed

Rahman

. Multi-interval pairwise compatibility graphs, Proc. Theory and Applications of Models of Computation (TAMC 2017) Lecture Notes in Computer Science, Springer International Publishing, 2017, pp. 71–84. doi:10.1007/978-3-319-55911-7_6.

Azam

Shurbevski

Nagamochi

. A method for enumerating pairwise compatibility graphs with a given number of vertices, Discrete Applied Mathematics 2021. 303:171–185. doi:10.1016/j.dam.2020.08.016.

Azam

Shurbevski

Nagamochi

. On the enumeration of minimal non-pairwise compatibility graphs, Journal of Combinatorial Optimization (Sep. 2021).

Calamoneri

Frangioni

Sinaimeri

. Pairwise compatibility graphs of caterpillars, The Computer Journal 2013. 57(11):1616–1623. doi:10.1093/comjnl/bxt068.

Calamoneri

Frascaria

Sinaimeri

. All graphs with at most seven vertices are pairwise compatibility graphs, The Computer Journal 2012. 56(7):882–886. doi:10.1093/comjnl/bxs087.

Calamoneri

Montefusco

Petreschi

Sinaimeri

. Exploring pairwise compatibility graphs, Theor. Comput. Sci. 2013. 468:23–36. doi:10.1016/j.tcs.2012.11.015.

Calamoneri

Lafond

Monti

Sinaimeri

On generalizations of pairwise compatibility graphs, manuscript (2022).

Calamoneri

Sinaimeri

. Pairwise compatibility graphs: A survey, SIAM Review 2016. 58(3):445–460. doi:10.1137/140978053.

Durocher

Mondal

Rahman

. On graphs that are not PCGs, Theoretical Computer Science 2015. 571:78–87.

10.

Kearney

Munro

Phillips

. Efficient generation of uniform samples from phylogenetic trees, Proc. Workshop on Algorithms in Bioinformatics (WABI 2003) Lecture Notes in Computer Science, Springer Berlin Heidel-berg, 2003, pp. 177189. doi: 10.1007/978-3-540-39763-2_14.

11.

Mehnaz

Rahman

. Pairwise compatibility graphs revisited, Proc. International Conference on Informatics, Electronics and Vision (ICIEV 2013), IEEE, 2013. doi:10.1109/ICIEV.2013.6572681.

12.

Papan

Pranto

Rahman

. On 2-Interval Pairwise Compatibility Properties of Two Classes of Grid Graphs, The Computer Journal 2023. 66(5):1256–1267. doi:10.1093/comjnl/bxac011.

13.

Phillips

Uniform sampling from phylogenetic trees, Masters thesis, University of Waterloo, Canada (2002).

14.

Rahman

Ahmed

. A survey on pairwise compatibility graphs, AKCE International Journal of Graphs and Combinatorics 2020. 17(3):788–795. doi:10.1016/j.akcej.2019.12.011.

15.

Yanhaona

Bayzid

Rahman

. Discovering pairwise compatibility graphs, Proc. International Computing and Combinatorics Conference (COCOON 2010), Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2010, pp. 399–408. doi:10.1007/978-3-642-14031-0_43.