Papers for

network structure analysts

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Square-complementary graphs cannot be chordal or distance-hereditary

There are no nontrivial chordal square-complementary graphs

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.

Wed 23 SeptDiscrete Mathematics
The gist
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.
Open → 2609.28702v1