On the 3-γ_t-Critical Graphs of Order Δ(G)+3

2011/03/12 by Haoli Wang, Xirong Xu, Wang, Haoli +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1103.2415

This paper was accpted by Utilitas Mathematica in 2008

arxiv created 2011/03/12 · arxiv updated 2011/03/15

Abstract

Let γ_t(G) be the total domination number of graph G, a graph G is k-total domination vertex critical (or just k-γ_t-critical) if γ_t(G)=k, and for any vertex v of G that is not adjacent to a vertex of degree one, γ_t(G-v)=k-1. Mojdeh and Rad \citeMR06 proposed an open problem: Does there exist a 3-γ_t-critical graph G of order Δ(G)+3 with Δ(G) odd? In this paper, we prove that there exists a 3-γ_t-critical graph G of order Δ(G)+3 with odd Δ(G)≥ 9.

Related

• Matching and Factor-Critical Property in 3-Dominating-Critical Graphs
• 3-Factor-criticality in double domination edge critical graphs
• Structural Properties of Connected Domination Critical Graphs
• The Existence of Graph whose Vertex Set Can be Partitioned into a Fixed Number of Domination Strong Critical Vertex-sets
• Independence and Connectivity of Connected Domination Critical Graphs