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