Loading...

2-coupon coloring of cubic graphs containing 3-cycle or 4-cycle

Akbari, S ; Sharif University of Technology | 2024

556 Viewed
  1. Type of Document: Article
  2. DOI: 10.1016/j.dam.2024.03.012
  3. Publisher: 2024
  4. Abstract:
  5. A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex in S. Recently, the following question was proposed: “Is it true that every connected cubic graph containing a 3-cycle has two vertex disjoint total dominating sets?” In this paper, we give a negative answer to this question. Moreover, we prove that if we replace 3-cycle with 4-cycle the answer is affirmative. This implies every connected cubic graph containing a diamond (the complete graph of order 4 minus one edge) as a subgraph can be partitioned into two total dominating sets, a result that was proved in 2017. © 2024
  6. Keywords:
  7. Total dominating set ; 4-cycle ; Complete graphs ; Coupon coloring ; Cubic graph ; Graph G ; Heawood graph ; Subgraphs ; Total dominating sets ; Vertex disjoint
  8. Source: Discrete Applied Mathematics ; Volume 351 , 2024 , Pages 105-110 ; 0166218X (ISSN)
  9. URL: https://www.sciencedirect.com/science/article/abs/pii/S0166218X24001124