Source author record

Moo Young Sohn

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

The Algorithmic Complexity of Bondage and Reinforcement Problems in bipartite graphs

Let $G=(V,E)$ be a graph. A subset $D\subseteq V$ is a dominating set if every vertex not in $D$ is adjacent to a vertex in $D$ . The domination number of $G$ , denoted by $γ(G)$ , is the smallest cardinality of a dominating set of $G$ . The bondage number of a nonempty graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with domination number larger than $γ(G)$ . The reinforcement number of $G$ is the smallest number of edges whose addition to $G$ results in a graph with smaller domination number than $γ(G)$ . In 2012, Hu and Xu proved that the decision problems for the bondage, the total bondage, the reinforcement and the total reinforcement numbers are all NP-hard in general graphs. In this paper, we improve these results to bipartite graphs.

preprint2010arXiv

On the existence problem of the total domination vertex critical graphs

The existence problem of the total domination vertex critical graphs has been studied in a series of articles. The aim of the present article is twofold. First, we settle the existence problem with respect to the parities of the total domination number m and the maximum degree Delta : for even m except m=4, there is no m-gamma_t-critical graph regardless of the parity of Delta; for m=4 or odd m \ge 3 and for even Delta, an m-gamma_t-critical graph exists if and only if Delta \ge 2 \lfloor \frac{m-1}{2}\rfloor; for m=4 or odd m \ge 3 and for odd Delta, if Delta \ge 2\lfloor \frac{m-1}{2}\rfloor +7, then m-gamma_t-critical graphs exist, if Delta < 2\lfloor \frac{m-1}{2}\rfloor, then m-gamma_t-critical graphs do not exist. The only remaining open cases are Delta = 2\lfloor \frac{m-1}{2}\rfloor +k, k=1, 3, 5. Second, we study these remaining open cases when m=4 or odd m \ge 9. As the previously known result for m = 3, we also show that for Delta(G)= 3, 5, 7, there is no 4-gamma_t-critical graph of order Delta(G)+4. On the contrary, it is shown that for odd m \ge 9 there exists an m-gamma_t-critical graph for all Delta \ge m-1.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.