Regular graphs with high edge degree |
| |
Authors: | Alan P Sprague |
| |
Affiliation: | Ohio State University, Columbus, Ohio 43210 USA |
| |
Abstract: | For any vertex x of a graph G let Δ(x) denote the set of vertices adjacent to x. We seek to describe the connected graphs G which are regular of valence n and in which for all adjacent vertices x and y |Δ(x) ∩ Δ(y)| = n ? 1 ? s. It is known that the complete graphs are the graphs for which s = 0. For any s, any complete many-partite graph, each part containing s + 1 vertices, is such a graph. We show that these are the only such graphs for which the valence exceeds 2s2 ? s + 1. The graphs satisfying these conditions for s = 1 or 2 are characterized (up to the class of trivalent triangle-free graphs.) |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|