Partitioning the vertices of a graph or its complement into a total dominating set and an independent dominating set

Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

Abstract

AgraphG whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. There exist infinite families of graphs that are not TI-graphs. We show that, with a few exceptions, every graph or its complement is a TI-graph. From this result, it follows that with the exception of the cycle on five vertices, every nontrivial, self-complementary graph is a TI-graph. We also characterize the complementary prisms which are TI-graphs and explore such partitions in prisms.

Original languageEnglish
Pages (from-to)97-115
Number of pages19
JournalAustralasian Journal of Combinatorics
Volume89
Publication statusPublished - 2024

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Partitioning the vertices of a graph or its complement into a total dominating set and an independent dominating set'. Together they form a unique fingerprint.

Cite this