On an edge partition and root graphs of some classes of line graphs
<p>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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2017-04-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/263 |
| _version_ | 1811250456959123456 |
|---|---|
| author | K Pravas A. Vijayakumar |
| author_facet | K Pravas A. Vijayakumar |
| author_sort | K Pravas |
| collection | DOAJ |
| description | <p>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.</p> |
| first_indexed | 2024-04-12T16:04:58Z |
| format | Article |
| id | doaj.art-12a7b569cf594ab69757763eaa3f026d |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-04-12T16:04:58Z |
| publishDate | 2017-04-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-12a7b569cf594ab69757763eaa3f026d2022-12-22T03:26:06ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872017-04-015110.5614/ejgta.2017.5.1.1283On an edge partition and root graphs of some classes of line graphsK Pravas0A. Vijayakumar1Department of Mathematics, K. K. T. M. Government College, Pullut-680663, IndiaDepartment of Mathematics, Cochin University of Science and Technology, Cochin-682022, India<p>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.</p>https://www.ejgta.org/index.php/ejgta/article/view/263line graph, gallai, anti-gallai, root graph |
| spellingShingle | K Pravas A. Vijayakumar On an edge partition and root graphs of some classes of line graphs Electronic Journal of Graph Theory and Applications line graph, gallai, anti-gallai, root graph |
| title | On an edge partition and root graphs of some classes of line graphs |
| title_full | On an edge partition and root graphs of some classes of line graphs |
| title_fullStr | On an edge partition and root graphs of some classes of line graphs |
| title_full_unstemmed | On an edge partition and root graphs of some classes of line graphs |
| title_short | On an edge partition and root graphs of some classes of line graphs |
| title_sort | on an edge partition and root graphs of some classes of line graphs |
| topic | line graph, gallai, anti-gallai, root graph |
| url | https://www.ejgta.org/index.php/ejgta/article/view/263 |
| work_keys_str_mv | AT kpravas onanedgepartitionandrootgraphsofsomeclassesoflinegraphs AT avijayakumar onanedgepartitionandrootgraphsofsomeclassesoflinegraphs |