Traceability of connected domination critical graphs

摘要

A dominating set in a graph G is a set S of vertices of G such that every vertex outside S is adjacent to a vertex in S. A connected dominating set in G is a dominating set S such that the subgraph G[S] induced by S is connected. The connected domination number of G, γc(G), is the minimum cardinality of a connected dominating set of G. A graph G is said to be k-γc-critical if the connected domination number γc(G) is equal to k and γc(G+uv)