Abstract: A graph G=(V,E) is a Pairwise Compatibility Graph (PCG) if there exists an edge-weighted tree T and an interval [d_min,d_max] such that uv ⋳ E ⇔ d_min≤ d_T(u,v) ≤  d_max for all distinct u,v ⋳ V. This thesis investigates PCGs and their extensions, such as multi-interval, OR, AND, and threshold PCGs, from constructive, computational, and asymptotic perspectives.

 

The study first explores the pairwise compatibility of grid graphs, proving that every d-dimensional rectangular grid graph is a (d-1)-interval-PCG and a ceil(d/2)-OR-PCG. Furthermore, we tested the tightness of the obtained bounds using the four-dimensional hypercube 〖(Q〗_4).

 

Second, the research advances the finite enumeration of PCGs by formulating recognition as an exact satisfiability problem based on the tree-metric four-point condition. Through a staged computational pipeline that filters for star and caterpillar witnesses, the thesis classifies connected unlabeled graphs up to ten vertices. This enumeration successfully compiles extensive catalogues of minimal non-PCGs upto ten vertices, and verifies that every connected graph on at most ten vertices is a 2-AND-PCG.

 

Finally, the thesis introduces (k,t)-threshold PCGs as a framework to unify existing Boolean PCG combinations. It establishes that the threshold model achieves universality when the number of constituent predicates scales with the graph order, but maintains asymptotic density zero for any fixed k. Additionally, the study strictly separates threshold PCGs from multi-interval PCGs, utilizes set-system incidence graphs to establish explicit structural obstructions, and proves that the k-AND-PCG hierarchy is strict while lacking closure under complement operations.

 

Presenter: Sheikh Azizul Hakim (Std No. 0423052021)

Venue: Graduate Seminar Room

Schedule:  06-Jun-2026 (3:30 PM - 4:00 PM)