Physical Sciences and Mathematics Commons^™

Structures Of Derived Graphs, Khawlah Hamad Alhulwah

Dissertations

One of the most familiar derived graphs are line graphs. The line graph L(G) of a graph G is the graph whose vertices are the edges of G where two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. One of the best- known results on the structure of line graphs deals with forbidden subgraphs by Beineke. A characterization of graphs whose line graph is Hamiltonian is due to Harary and Nash-Williams. Iterated line graphs of almost all connected graphs were shown to be Hamiltonian by Chartrand. The girth of a graph G …