Square-complementary graphs cannot be chordal or distance-hereditary
There are no nontrivial chordal square-complementary graphs
Discrete Mathematics
Summary
This paper explores a special type of graph where the square of the graph looks like its complement. The authors found that in such graphs, vertices cannot have neighborhoods that fit inside one another, which means these graphs can't have a certain simple structure called 'chordal'. They also showed these graphs don’t have some simple vertices and can’t be distance-hereditary, solving earlier open questions. Their work narrows down what these special graphs can look like.
What this means in practice
- •For graph algorithm designers: Avoid chordal and distance-hereditary graphs when designing algorithms involving square-complementary graphs, as these graph classes are ruled out.
- •For network structure analysts: Exclude chordal and distance-hereditary assumptions when modeling networks whose squared structure matches the network’s complement.
A theory result. No direct application yet.
Authors
Pierre Aboulker, Martin Milanič, Peter Muršič, Miguel A. Pizaña
Abstract
We study square-complementary graphs $G$ (satisfying $G^2 \cong \overline{G}$). We show that in such graphs, no two vertices have comparable closed neighborhoods. This implies that nontrivial square-complementary graphs have no simplicial vertices and are not chordal, thus solving two open problems posed in Discrete Mathematics 327 (2014) 62-75. We also show that no nontrivial square-complementary graph is distance-hereditary.