SIG-dimension conjecture proved for graphs having a perfect matching
Ramanjit Kumar, Surinder Pal Singh Kainth · Discrete Mathematics Algorithms and Applications · 2016
We prove the Boyer’s conjecture for graphs having a perfect matching. That is, if [Formula: see text] is such a graph of order [Formula: see text] then [Formula: see text] We also prove an upper bound for the SIG-dimension of any graph without isolated vertices, along with some other results on SIG-dimension.