Papers for

graph theorists

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.

Four connected graphs found without legal systems despite positive curvature

A Four-Connected Graph without a Legal System

Abstract: In a 2021 paper, Jankiewicz, Norin, and Wise asked whether there exists a finite $4$-connected graph of girth at least four and nonnegative Charney--Davis curvature such that no $4$-connected ordinary subgraph admits a legal system. We construct such a graph by starting from the hexagonal prism and attaching three $K_{3,4}$-based caps along pairwise disjoint induced $4$-cycles. The key structural input is a restriction theorem showing that a legal system on an induced-$4$-cycle amalgam restricts to each side, so the obstruction carried by the negatively curved prism survives the attachments. The resulting $33$-vertex graph is $4$-regular and $4$-connected, has girth four and Charney--Davis curvature one, and, by $4$-regularity, is its own unique $4$-connected ordinary subgraph.

Fri 11 SeptDiscrete Mathematics

The gist

The paper answers a complex question about a special type of network called a 4-connected graph. The authors show that there exists a particular network with certain properties—like having no small loops and a positive curvature measure—but still does not have a 'legal system,' a kind of substructure researchers study. They build this example starting from a known shape called a hexagonal prism and attach special parts to it. This construction proves that their example behaves uniquely in the way they asked about.

Open → 2609.13419v1