### Abstract

We introduce a new class of graphs called diametral path graphs that properly contains the class of asteroidal triple-free graphs and the class of dominating pair graphs. We characterize the trees as well as the chordal graphs that are diametral path graphs. We present an O(n^{3} m) algorithm deciding whether a given graph has a dominating diametral path. Finally, we study the structure of minimum connected dominating sets in diametral path graphs.

Original language | English (US) |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science - 21st International Workshop, WG 1995, Proceedings |

Editors | Manfred Nagl |

Publisher | Springer Verlag |

Pages | 344-357 |

Number of pages | 14 |

ISBN (Print) | 3540606181, 9783540606185 |

DOIs | |

State | Published - 1995 |

Event | 21st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1995 - Aachen, Germany Duration: Jun 20 1995 → Jun 22 1995 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1017 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 21st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1995 |
---|---|

Country | Germany |

City | Aachen |

Period | 6/20/95 → 6/22/95 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Diametral path graphs'. Together they form a unique fingerprint.

## Cite this

Deogun, J. S., & Kratsch, D. (1995). Diametral path graphs. In M. Nagl (Ed.),

*Graph-Theoretic Concepts in Computer Science - 21st International Workshop, WG 1995, Proceedings*(pp. 344-357). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1017). Springer Verlag. https://doi.org/10.1007/3-540-60618-1_87