×

A neighborhood condition for graphs to be \([a, b; m]\)-uniform. (Chinese. English summary) Zbl 1084.05052

Summary: Let \(G\) be an \(n\)-order graph, let \(a\) and \(b\) be integers such that \(1\leq a< b\), and let \(\delta(G)\) be the minimum degree. It is proved that if \(\delta(G)\geq a+1\), \(n\geq 2(a+b)(a+ b-1)/b\), and \(|N_G(x)\cup N_G(y)|\geq an/(a+ b-1)+ 2\) for any two non-adjacent vertices \(x\) and \(y\) of \(G\), then \(G\) is an \([a,b; m]\)-uniform graph.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite