Accession Number : AD0638652

Title :   CHARACTERIZATION OF LINE GRAPHS.

Descriptive Note : Technical summary rept.

Corporate Author : MATHEMATICS RESEARCH CENTER UNIV OF WISCONSIN MADISON

Personal Author(s) : Ray-Chaudhuri,D. K.

Report Date : APR 1966

Pagination or Media Count : 22

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)

Descriptors :   (*GRAPHICS, THEOREMS), (*COMBINATORIAL ANALYSIS, GRAPHICS)

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE