An Operation Based on Complete Graphs with an Application to the Line Graphs of Trees

Abstract

Given a disjoint union of some complete graphs, one can define a graph by choosing one vertex from each complete graph and making all of these vertices adjacent. This observation leads us to define a new operation on certain graphs. We compute the characteristic polynomial of the resulting graphs and indicate a method for computing the determinant of this matrix for obtaining the characteristic polynomial of new graphs. We show that line graphs of trees can be obtained by performing this operation on some graphs, and, as an application, we compute the characteristic polynomials of line graphs of trees.