Metrik

  • visibility 246 kali dilihat
  • get_app 103 downloads
description Journal article public Electronic Journal of Graph Theory and Applications

On an Edge Partition and Root Graphs of Some Classes of Line Graphs

K. Pravas, A. Vijayakumar
Diterbitkan 2017

Abstrak

The Gallai and the anti-Gallai graphs of a graph $G$ are complementary pairs of spanning subgraphs of the line graph of $G$. In this paper we find some structural relations between these graph classes by finding a partition of the edge set of the line graph of a graph $G$ into the edge sets of the Gallai and anti-Gallai graphs of $G$. Based on this, an optimal algorithm to find the root graph of a line graph is obtained. Moreover, root graphs of diameter-maximal, distance-hereditary, Ptolemaic and chordal graphs are also discussed.

Full text

 

Metrik

  • visibility 246 kali dilihat
  • get_app 103 downloads