Large regular graphs with no induced \(2K_ 2\) (Q1196569): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3039368 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3780901 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree / rank | |||
Normal rank |
Latest revision as of 15:02, 16 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Large regular graphs with no induced \(2K_ 2\) |
scientific article |
Statements
Large regular graphs with no induced \(2K_ 2\) (English)
0 references
16 January 1993
0 references
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.
0 references
regular graphs
0 references
extremal graphs
0 references
excluded graphs
0 references
interconnection
0 references
networks
0 references
bipartite graph
0 references