Independent point-set domination in line graphs
Line graph of a graph G is an intersection graph of the edge set E(G) of G. In this paper, we obtain a sharp upper bound on the diameter of graph G whose line graph is an ipsd graph (graph possessing an independent point-set dominating set) by establishing a fundamental relation between diameter of...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Taylor & Francis Group
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/b92e3f8397bb4782a9662d610615280e |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | Line graph of a graph G is an intersection graph of the edge set E(G) of G. In this paper, we obtain a sharp upper bound on the diameter of graph G whose line graph is an ipsd graph (graph possessing an independent point-set dominating set) by establishing a fundamental relation between diameter of G and diameter of its line graph L(G). We prove that if for a graph G, the length of the longest induced cycle is greater than 5, then its line graph does not possess an ipsd-set. Further we characterize certain classes of graphs viz., trees, complete graphs and complete bipartite graphs whose line graphs possess an independent point set dominating set. |
|---|