Graphs with odd cocliques

Let \(\Gamma =(X,E)\) be a graph. For any x in X, denote by \(\Gamma\) (x) the set of neighbours of x in \(\Gamma\) and \(x^{\perp}=\{x\}\cup \Gamma \{x\}.\) A subset A is called odd (even) when \(| x^{\perp}\cup A|\) is odd (even) for all x in X. Property \((CC)_ d\) means each (d- 1)-coclique is contained in some odd d-coclique and property \((C1)_ d\) means for some odd d-coclique C and a point \(x\not\in C\) we have \(| x^{\perp}\cap C| =1.\Gamma\) is called reduced when the equivalence classes are single points, where the equivalence relation xRy is defined by \(x^{\perp}=y^{\perp}.\) It is shown here that \(\Gamma\) satisfies \((CC)_ 1\) iff its radial \(rad \Gamma (=\{x\in X:\;x^{\perp}=X\})\) is empty and that \(\Gamma\) is non-empty, reduced and satisfies \((CC)_ 2\) iff \(\Gamma =f(\Delta)\) for some reduced graph \(\Delta\) with radial rad \(\Delta\) empty and without odd 2-coclique, where \(f(\Delta)=D(\Delta \oplus \{\infty \}),\) the Taylor double of \(\Delta \oplus \{\infty \}.\) Some more necessary and sufficient conditions are given for a graph to be reduced, coconnected and satisfy \((CC)_ d\) and \((C1)_ d\).

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Graphs with odd cocliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q753839)