Graphs with odd cocliques
type: Item
instance of: scholarly article
title: Graphs with odd cocliques
zbMATH Open document ID: 0717.05060
DOI: 10.1016/S0195-6698(13)80062-5
author: Andries E. Brouwer
author: E. E. Shult
published in: European Journal of Combinatorics
publication date: 1990-01-01T00:00:00Z
review text: 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\).
reviewed by: Hao Li
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4181390
zbMATH Keywords: coclique
zbMATH Keywords: reduced radial
zbMATH Keywords: Taylor double
MaRDI profile type: Publication
cites work: Locally polar spaces and related rank 3 groups
cites work: Locally cotriangular graphs
cites work: Q5181734
cites work: Characterizations of certain classes of graphs
cites work: Q4065708
full work available at URL: s0195-6698(13)80062-5
OpenAlex ID: W2061056752
description: scientific article; zbMATH DE number 4181390