CHARACTERIZATION OF LINE GRAPHS.
Abstract
Let G be a finite undirected graph with at most one edge joining a pair of vertices and no edge joining a vertex to itself. L(G) denotes the line graph of G, i.e. the vertices of L(G) are the edges of G and two vertices of L(G) are adjacent if the corresponding edges of G are adjacent. Let d(u) denote the valence of a vertex u. Let d(G) denote the smallest integer which is equal to the valence of some vertex of u. For an edge (u,v), delta(u,v) denotes the number of vertices w which are adjacent to both u and v. The main theorem of this paper is: If (i) d(G) > 43, (ii) -2 is the minimum eigenvalue of the adjacency matrix of G and (iii) for any edge (u,v), delta(u,v) < Min (d(u) -2, d(v) -2), then G is isomorphic to L(H) for some graph H. Conversely if d(H) > 3, then the line graph L(H) satisfies conditions (ii) and (iii) stated above. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1966
- Accession Number
- AD0638652
Entities
People
- D. K. Ray-chaudhuri