The structure of totally critical graphs of odd order Original Research Article

It has been known for some time that if the Conformability Conjecture is true, then we can say exactly which graphs G of maximum degree Δ(G)⩾12 |V(G)| and even order are totally critical; by contrast, the situation for odd order graphs has been unclear. Here we look in particular at odd order graphs G with low deficiency and high maximum degree relative to the order. We show that such graphs are totally critical if and only if they are conformability critical. We also give a structural characterization of such totally critical graphs. These results do not depend on the truth or otherwise of the Conformability Conjecture.