Large regular graphs with no induced \(2K_ 2\) (Q1196569): Difference between revisions

Let \(H\) be the disjoint union of two edges. A graph is \(H\)-free if it does not contain \(H\) as induced subgraph. This paper studies regular \(H\)- free graphs, of which the cycle \(C\) on 5 nodes is an example. It is first shown that any regular \(H\)-free graph of degree \(r\) has at most \(5r/2\) vertices. Let \(v\) denote the number of vertices of a regular \(H\)-free graph of degree \(r\), then it is conjectured that when \(v>2r\) then \(r\) is even and \(v/r\) is of the form \(2+1/(2k)\) for some \(k\). After deriving several structural properties of such graphs, a proof of this conjecture is obtained when \(v\geq 21r/10\), in which case only 7 basic graphs exist from which all others may be derived by expansion, i.e. replacing all vertices by a fixed number of nonadjacent vertices, and each edge by a complete bipartite graph. It is also conjectured that this type of result holds more generally.