\documentstyle[11pt]{article}
\textwidth=6.5in
\textheight=9in
\evensidemargin=0in
\oddsidemargin=0in
\topmargin=-0.3in
\topskip=0pt
\baselineskip=12pt
\parskip=0pt
\parindent=1em
\newtheorem{obs}{Observation}
\newtheorem{defn}{Definition}
\newtheorem{thm}{Theorem}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\begin{document}
\bibliographystyle{plain}
\title{Nearly Perfect Sets in Graphs}
\author{ Jean E. Dunbar \\
Department of Mathematics \\
Converse College \\
Spartanburg, South Carolina 29302\\
\\
Frederick C. Harris, Jr.\\
Sandra M. Hedetniemi\\
Stephen T. Hedetniemi \\
Alice A. McRae\\
Department of Computer Science \\
Clemson University \\
Clemson, South Carolina 29634\\
\\
Renu C. Laskar \\
Department of Mathematics \\
Clemson University \\
Clemson, South Carolina 29634\\
\\
}
\date{\quad}
\maketitle
 
\begin{abstract}
	In a graph $G = (V,E)$, a set of vertices $S$ is nearly perfect
	if every vertex in $V - S$ is adjacent to at most one vertex in
	$S$.  Nearly perfect sets are closely related to 2-packings of
	graphs, strongly stable sets, dominating sets and efficient
	dominating sets.  We say a nearly perfect set $S$ is 1-minimal
	if for every vertex $u$ in $S$, the set $S - \{u\}$ is not
	nearly perfect.  Similarly, a nearly perfect set $S$ is
	1-maximal if for every vertex u in $V - S$,  $S \cup \{u\}$ is
	not a nearly perfect set.  Lastly, we define $n_{p}(G)$ to be
	the minimum cardinality of a 1-maximal nearly perfect set, and
	$N_{p}(G)$ to be the maximum cardinality of a 1-minimal nearly
	perfect set.  In this paper we calculate these parameters for
	some classes of graphs.  We show that the decision problem for
	$n_{p}(G)$ is NP-complete; we give a linear algorithm for
	determining $n_{p}(T)$ for any tree $T$; and we show that
	$N_{p}(G)$ can be calculated for any graph $G$ in polynomial
	time.
\end{abstract}
 
\section{Introduction}

	Let $G = (V,E)$ be a graph.  We say that a set $S$ of vertices
	in $V$ is a {\em P-set} if $S$ has property $P$, for some property
	under consideration.  Frequently we say that a set $S$ has
	property $P$ if the subgraph of $G$ induced by $S$, denoted
	$<S>$, has some property $P$, eg. $<S>$ is acyclic, or planar
	or has degree at most k for some non-negative integer $k$.
	Other properties, however, are not defined in terms of induced
	subgraph structures.  For example, $S$ is a {\em dominating set} if
	every vertex in $V - S$ is adjacent to at least one vertex in
	$S$ or  $S$ is  an {\em irredundant set} if for every vertex u in
	$S$, $N[u] - N[S - \{u\}]$ is not empty.  Most optimization
	problems in graph theory are concerned with finding either the
	minimum or maximum cardinality of a P-set in a graph $G$.
	However, recent research has studied the spectrum of
	cardinalities of a wide variety of minimal and maximal P-sets
	in a graph.  But care should be taken in defining a minimal or
	a maximal P-set.  There are usually two definitions given for
	each term.

 
	  (1)  A P-set $S$ is maximal if no proper superset $S'$ of $S$
		is a P-set.

	  (1')  A P-set $S$ is maximal if for every vertex $u$ in $V -
		S$, $S \cup \{u\}$ is not a P-set.

	  (2) A P-set $S$ is minimal if no proper subset $S'$ of $S$ is
		a P-set.

	  (2') A P-set $S$ is minimal if for every vertex $u$ in $S$,
		the set $S - \{u\}$ is not a P-set.

	A property $P$ of a graph is {\em hereditary} if whenever a set $S$
	has property $P$, every proper subset $S'$ of $S$ also has
	property $P$.  For example, the properties of being an
	independent set of vertices (no two vertices in the set are
	adjacent) or an irredundant set of vertices are hereditary.  It
	is easy to see that definitions (1) and (1') of maximal P-sets
	are equivalent if $P$ is a hereditary property.


	A property $P$ is called {\em super-hereditary} (or {\em expanding}) 
	if
	whenever a set $S$ has property $P$, every superset $S'$ of $S$
	also has property $P$.  For example the properties of being a
	dominating set or a vertex cover are super-hereditary.  It is
	also easy to see that definitions (2) and (2') of minimal
	P-sets are equivalent for super-hereditary properties P.

	In \cite{bcm}  Bollob$\acute{a}$s, Cockayne and Mynhardt
	defined new notions of minimality and maximality as follows.  A
	set of vertices $S$ in $V$ is a {\em k-minimal P-set} if the removal
	of any set $X$ of $k \leq |S|$ 
	vertices from $S$ followed by the
	addition of any $l < k$ vertices results in a set that does not
	have property $P$.

	Similarly a set of vertices $S$ in $V$ is a {\em k-maximal P-set} if
	the addition of any set $X$ of $k$ vertices, followed by the
	removal of any $l < k$ vertices does not result in a P-set.  It
	is easy to see that 1-minimal P-sets are minimal P-sets according to
	definition (1') and 1-maximal P-sets are maximal P-sets
	according to definition (2').  It is also easy to see that
	there are 1-minimal P-sets which are not 2-minimal P-sets, eg.
	in Figure~\ref{fig:one} each set of solid vertices is 1-minimal
	but the set in Figure~\ref{fig:one}(a) is not a 2-minimal set,
	since if we remove the two endvertices and then add the
	center vertex to $S$, we obtain another dominating set.

	\begin{figure} \begin{center}
		\begin{picture}(90,10) \put(0,0){\circle*{10}}
		\put(5,0){\line(1,0){10}} \put(20,0){\circle{10}}
		\put(25,0){\line(1,0){10}} \put(40,0){\circle*{10}}

		\end{picture} \begin{picture}(70,10)

		\put(0,0){\circle{10}} \put(5,0){\line(1,0){10}}
		\put(20,0){\circle*{10}} \put(25,0){\line(1,0){10}}
		\put(40,0){\circle{10}}

		\end{picture} \end{center} \caption{ (a)\hspace{1in}
	(b) \hspace*{1in}} \label{fig:one} \end{figure}

	The study of k-minimal and k-maximal sets is still very new;
	not much is known about these sets.  The reader is referred to
	\cite{bcm}, \cite{cm} and \cite{cmm}.  The following property
	provides an example for which the definition of minimal or
	maximal must be given carefully.


\section{Definition of Nearly Perfect Sets}

	Let $G = (V,E)$ be a graph and let $u$ be a vertex in $V$.  The {\em
	open neighborhood of u\/} is defined as the set of vertices $v$
	adjacent to $u$; i.e., $ N(u) = \{v | uv \in E\}$.  The {\em
	closed neighborhood of u\/} is $ N[u] =  N(u) \cup \{ u \} $.
	In a graph G, a set of vertices S is {\em nearly perfect} if
	for every vertex $u \in V - S$, $ |N(u) \cap
	S| \leq 1 $; i.e., every vertex $u \in V - S$ is adjacent to at
	most one vertex in $S$.

	Nearly perfect sets are closely related to 2-packings of
	graphs, strongly stable sets, dominating sets and efficient
	dominating sets, as indicated in Table 1.

	\begin{table} \begin{center} \begin{tabular}{|c|c|c|} \hline
		& $\forall u \in V - S$
			& $\forall u \in V$ \\ \hline
	$|N(u) \bigcap S| \leq 1$
		& near perfect
			& total near perfect \\
	maximal sets
		& $n_{p}$
			& $n_{tp} \leq N_{tp}$ \\ \hline
	$|N[u] \bigcap S| \leq 1$
		& near perfect
			& independent near perfect \\
	maximal sets
		& $n_{p}$
			& (strong stable set or 2-packing) \\ &
			& $p_{2} \leq P_{2}$ \\ \hline
	$|N(u) \bigcap S| = 1$
		& perfect domination
			& total perfect domination \\ & $\gamma_{p}$
			& $\gamma_{tp} \leq \Gamma_{tp}$ \\ \hline
	$|N[u] \bigcap S| = 1$
		& perfect domination
			& efficient domination \\ & $\gamma_{p}$
			& $\gamma_{e} \leq \Gamma_{e}$ \\ \hline
	$|N(u) \bigcap S| \geq 1$
		&  domination
			& total domination \\
	minimal sets
		& $\gamma \leq \Gamma$
			& $\gamma_{t} \leq \Gamma_{t}$ \\ \hline
	$|N[u] \bigcap S| \geq 1$
		&  domination
			&  domination \\
	minimal sets
		& $\gamma \leq \Gamma$
			& $\gamma \leq \Gamma$ \\ \hline
	\end{tabular}
	\end{center} 
	\caption{} 
	\label{table:cockayne} 
	\end{table}

	Table~\ref{table:cockayne} first appeared in a paper by
	Cockayne, Hartnell, Hedetniemi, and Laskar \cite{chhl}, which
	focused on perfect dominating sets, and in particular on
	families of graphs whose only perfect dominating set is the
	entire vertex set $V$.  Nearly perfect sets, although first
	defined in \cite{chhl}, were not studied there.  In this paper
	we initiate the study of nearly perfect sets in graphs.

	Notice that for any graph $G$, the empty set $\phi$ of
	vertices, any set $S = \{u\}$ consisting of a single vertex,
	and the set $V$ are all nearly perfect sets.
	Thus, using definition (1), the only minimal nearly perfect set
	in any graph is the empty set.  And using definition (2), the
	only maximal nearly perfect set in any graph is the set $V$.


	However, using definitions (1') and (2'), a graph can have
	nontrivial minimal and maximal nearly perfect sets.  For
	example, in the graph $C_{4}$ in Figure 2 the set $\{1,2\}$ is
	a 1-maximal nearly perfect set; and in Figure 3 the set
	$\{1,2,5\}$ is a 1-minimal nearly perfect set in the graph $G$.


	\begin{figure} \begin{center} \begin{picture}(120,20)

	\put(0,0){\circle*{10}} \put(5,0){\line(1,0){10}}
	\put(20,0){\circle{10}}

	\put(0,5){\line(0,1){10}} \put(20,5){\line(0,1){10}}

	\put(0,20){\circle*{10}} \put(5,20){\line(1,0){10}}
	\put(20,20){\circle{10}}

	\put(0,27){\makebox(0,0)[b]{1}}
	\put(20,27){\makebox(0,0)[b]{4}}
	\put(0,-7){\makebox(0,0)[t]{2}}
	\put(20,-7){\makebox(0,0)[t]{3}} \end{picture}
	\begin{picture}(50,20)

	\put(0,0){\circle*{10}} \put(5,0){\line(1,0){10}}
	\put(20,0){\circle{10}}

	\put(0,5){\line(0,1){10}} \put(20,5){\line(0,1){10}}

	\put(0,20){\circle*{10}} \put(5,20){\line(1,0){10}}
	\put(20,20){\circle{10}}

	\put(-20,10){\circle*{10}} \put(-15,10){\line(2,1){12}}
	\put(-15,10){\line(2,-1){12}}

	\put(0,27){\makebox(0,0)[b]{1}}
	\put(20,27){\makebox(0,0)[b]{4}}
	\put(0,-7){\makebox(0,0)[t]{2}}
	\put(20,-7){\makebox(0,0)[t]{3}}
	\put(-20,3){\makebox(0,0)[t]{5}} 
	\end{picture} 
	\end{center}
	\caption{\hspace*{1in}Figure 3: \hspace*{0.3in}}
	\label{fig:two} 
	\end{figure} 
	\addtocounter{figure}{1}


	Define {\bf $n_{p}(G)$} to equal the minimum cardinality of a
	1-maximal nearly perfect set, and {\bf$N_{p}(G)$} to equal the
	maximum cardinality of a 1-minimal nearly perfect set in $G$.
	Notice that $n_{p}(G)$ is well-defined since $V$ is always a
	1-maximal nearly perfect set; i.e., $ n_{p}(G) \leq |V| $ .  In
	particular, $n_{p}(K_{n}) = 1$ , for $n \geq 3$ and
	$n_{p}(\bar{K}_{n}) = n$ .

	Also $N_{p}(G)$ is well-defined since the empty set is always a
	1-minimal nearly perfect set; i.e., $N_{p}(G) \geq0$.  In
	particular, $N_{p}(K_{n}) = n$ for $n \geq 3$, and
	$N_{p}(\bar{K}_{n}) = 0$.

\section{Characteristics of the Parameter $n_{p}(G)$ }

	The first result characterizes the property of 1-maximality in
	a nearly perfect set.

	\begin{lemma} 
	\label{lemma:small} 
	A nearly perfect set $S$ in a graph $G = (V,E)$ is 1-maximal if
	and only if every vertex $u$ in $V - S$ is adjacent to a vertex
	$v \neq u$ in $V - S$ which is adjacent to exactly one vertex
	in $S$.
	\end{lemma}

	{\bf Proof}.  The characterizing property given above is
	illustrated in Figure~\ref{fig:four}.  Suppose a set $S$ is
	1-maximal nearly perfect.  Let $u$ be an element of $V - S$ and
	assume that every vertex $w$ adjacent to $u$ in $V - S$ is not
	adjacent to any vertex in $S$.  Then every element outside of
	the set $S \cup \{u\}$ is adjacent to at most one element in
	the set $S \cup \{u\}$.  Thus, the set $S \cup \{u\}$  is
	nearly perfect.  This contradicts the assumption that $S$ is
	1-maximal nearly perfect.

	\begin{figure} 
	\begin{center} 
		\begin{picture}(20,20)
		\put(0,0){\circle*{10}} \put(5,0){\line(1,0){25}}
		\put(35,0){\circle{10}} \put(35,5){\line(0,1){10}}

		\put(10,20){\circle*{10}} \put(15,20){\line(1,0){15}}
		\put(35,20){\circle{10}} \put(35,25){\line(0,1){10}}
		\put(47,20){\makebox(0,0)[b]{v}}
		\put(35,40){\circle{10}}
		\put(47,40){\makebox(0,0)[b]{u}}

		\put(-40,-15){\dashbox{.7}(58,50)[t]{}}
		\put(0,10){\makebox(0,0)[b]{S}}
		\end{picture} 
	\end{center}
	\caption{} \label{fig:four} 
	\end{figure}

	On the other hand if $S$ is nearly perfect and satisfies the
	property above, then for any vertex $u$ in $V - S$, there is a
	vertex $u'$ in $(V - S) \cup N(u) $, with $u'$ adjacent to some
	vertex $v$ in $S$.  Thus,  $S \cup \{u\}$ is not a nearly
	perfect set, since $u'$ is adjacent to the two vertices $u$ and
	$v$ in $S \cup \{u\}$.  Since $u$ was chosen arbitrarily, we
	know that the union of $S$ with any vertex in $V - S$ will not
	be a nearly perfect set.  Thus, $S$ is a 1-maximal nearly
	perfect set.
	\vspace*{0.2in} 
	$\Box$

	Using Lemma \ref{lemma:small}, the values of $n_{p}(G)$ for
	some classes of graphs are easily determined.  For example, the
	complete bipartite graph $K_{m,n}$ (for $ m,n \geq 2$) has a
	smallest 1-maximal nearly perfect set of size two.  One such
	set can be found by selecting one vertex from each of the
	partite sets of the vertex set.  Since such a set is nearly
	perfect, it follows from Lemma \ref{lemma:small} that the set
	is also 1-maximal.  The following lemma will be used to
	calculate the parameter $n_{p}(G)$ for paths and cycles.


	\begin{lemma} 
	\label{lemma:path}
	Suppose $G =(V,E)$ is a path or a cycle with order at least four
	and that $S$ is a
	subset of the vertices of $G$.  Then $S$ is a 1-maximal nearly
	perfect set if and only if

	(i)  the subgraph spanned by $V - S$ is a disjoint union of
	$K_{2}$ graphs, and

	(ii)  every vertex in $V - S$ is adjacent to exactly one vertex
	of $S$.
	\end{lemma}

	{\bf Proof}.  Suppose $S$ is a 1-maximal nearly perfect set and
	let $v$ be an element of $V - S$.  By Lemma \ref{lemma:small},
	we know there is an element $w \neq v$ in $V - S$ with $w$
	adjacent to $v$ and $w$ adjacent to one vertex $x$ of $S$.
	Since the maximum degree of G is two, $N(w) = \{v,x\}$.  Further
	since $w$ is in $V - S$, Lemma \ref {lemma:small} guarantees
	that a neighbor of $w$ must lie outside of $S$ and be adjacent
	to an element of $S$.  Since all neighbors of $w$ are accounted
	for, this element must be $v$.  So $v$ must be adjacent to a
	vertex, say $y$, in $S$.  Note that $y \neq x$.  Since the
	maximum degree in $G$ is two, we must have that $ N(v) =
	\{w,y\}$ .  Since $v$ was an arbitrary element of $V - S$, we
	must have that $<V-S>$ consists of disjoint copies of $K_{2}$
	and that every element of $V-S$ is adjacent to exactly one
	element in $S$.

	Conversely, if $S$ is a subset of $V$ for which properties (i)
	and (ii) hold, then property (ii) guarantees that $S$ is a
	nearly perfect set.  Moreover, any vertex of $V - S$ will be
	adjacent to another vertex of $V - S$ which is adjacent to a
	vertex in $S$.  Thus by Lemma \ref{lemma:small} we know that
	$S$ is a 1-maximal nearly perfect set.
	$\Box$


	\begin{prop} 
	\label{prop:npath}
	If $P_{n}$ is a path with $n$ vertices, then
	\[ n_{p}(P_{n})  = \left\{ \begin{array}{ll}
				k + 2, & \mbox{if n = 3k} \\ 
				k + 1, & \mbox{if n = 3k + 1} \\ 
				k + 2, & \mbox{if n = 3k + 2} 
			\end{array} \right.    \]
	\end{prop}

	{\bf Proof}.  Let $P$ be the path $p_{1}p_{2}\ldots p_{n}$.
	The proof is by induction on $n$.  Clearly the
	result holds for paths with $n = 1, 2 \ or \ 3$ vertices.
	Suppose $n > 3$ and assume the result holds for all paths with
	less than $n$ vertices.

	\paragraph{Case 1.  n = 3k} \hspace*{1em}\\ 
	\begin{figure} 
	\begin{center} 
		\begin{picture}(240,10)(-80,0)
		\put(-75,0){\line(1,0){30}} \put(-40,0){\circle{10}}
		\put(-35,0){\line(1,0){30}} \put(0,0){\circle*{10}}
		\put(5,0){\line(1,0){30}} \put(40,0){\circle{10}}
		\put(45,0){\line(1,0){30}} \put(80,0){\circle{10}}
		\put(85,0){\line(1,0){30}} \put(120,0){\circle*{10}}
		\put(125,0){\line(1,0){30}} %\put(40,-5){\oval(160,10)[b]}
		\put(-40,-15){\dashbox{0.8}(160,0)}
		\put(-40,-15){\dashbox{0.8}(0,10)}
		\put(120,-15){\dashbox{0.8}(0,10)}
		\put(-40,7){\makebox(0,0)[b]{$j-3$}}
		\put(0,7){\makebox(0,0)[b]{$j-2$}}
		\put(40,7){\makebox(0,0)[b]{$j-1$}}
		\put(80,7){\makebox(0,0)[b]{$j$}}
		\put(120,7){\makebox(0,0)[b]{$j+1$}}
		\end{picture}
	\end{center} 
	\caption{} 
	\label{fig:five} 
	\end{figure}
	Let $S = \{p_{1}, p_{4}, p_{7}, \ldots, p_{n-2}, p_{n-1}, p_{n} \}$.
	Note first that $n - 2 = 3(k-1) + 1$.  Since $V - S$ is a
	disjoint collection of $K_{2}$ graphs and every vertex of $V -
	S$ is adjacent to exactly one vertex of $S$, we know by Lemma
	\ref{lemma:path} that $S$ is a 1-maximal nearly perfect set.
	Further note that $|S| = (k - 1) + 3 = k + 2$.  Suppose there
	exists a 1-maximal nearly perfect set T with cardinality less
	than the cardinality of $S$.  Let $j = max \{i | p_{i}  \in  V
	- T\} $.  Since every element of $V - T$ must have degree two,
	we know $j < n$.  Further, $j > 3$, for if not then with $j
	\leq 3$ we would know that all vertices to the right of $p_{j}$
	were in $T$ and at least one vertex to the left of $p_{j}$ must
	be in $T$.  Thus under this assumption we would have $|T| \geq
	3k - 2 \geq k + 2 = |S|$.  The last inequality holds because $k
	\geq 2$.  So we must have $3 < j < n$.  Since $T$ is 1-maximal
	nearly perfect, we must have $p_{j-1}$ in $V - T$, and
	$p_{j-2}$ in $T$.  Let $ U = \{p_{j-2}, p_{j-1}, p_{j} \} $,
	and consider the graph $G'$ obtained by adding an edge $p_{j-3}
	p_{j+1}$  to the graph $G - U$.  See Figure 5.  Since $p_{j-2}$
	is in $T$ and $p_{j+1}$ is in $T$, the new edge allows the same
	adjacencies for $p_{j-3}$ in $G'$ as in $G$.  Then $T - U$ is a
	nearly perfect set in $G'$ (which is $P_{n-3}$) and the
	cardinality of $T - U$ is $|T| - 1 < (k+2) - 1 = (k-1) + 2$,
	contradicting the inductive hypothesis on $P_{n-3}$.

	\paragraph{Case 2.  n = 3k+1} \hspace*{1em}\\ 
	Let $S = \{p_{1}, p_{4}, p_{7}, \ldots, p_{n}\}$.  Note that $|S| =
	k + 1$, and, as before, $S$ is a 1-maximal nearly perfect
	set.  In exactly the same way as in Case 1, we may assume $T$
	has cardinality less than that of $S$ and is a 1-maximal nearly
	perfect set in the path.  It is immediate to see that a subset
	of the path $P_{n-3}$ can be found which is 1-maximal nearly
	perfect and which contradicts the inductive hypothesis on
	$P_{n-3}$.


	\paragraph{Case 3.  n = 3k+2} \hspace*{1em}\\   
	Let $S = \{p_{1}, p_{4}, p_{7}, \ldots, p_{3k + 1}, p_{3k+2} \}$.
	Note that $|S| = k + 2$, and that $S$ is a 1-maximal nearly
	perfect subset of the path.  The proof that $S$ is of smallest
	size uses the same argument as that for the first two cases.
	$\Box$


	\begin{prop}
	If $C_{n}$ is a cycle with n vertices, then
	\[ n_{p}(C_{n})  = \left\{ \begin{array}{ll}
				k,     & \mbox{if n = 3k}\\ 
				k + 1, & \mbox{if n = 3k + 1} \\ 
				k + 2, & \mbox{if n = 3k + 2} 
			\end{array} \right.    \]
	\end{prop}

	The proof is similar to that of Proposition \ref{prop:npath}
	and is omitted.

	For some graphs the smallest 1-maximal nearly perfect set must
	include all vertices in the graph.  One such example already
	mentioned is $\bar{K}_{n}$.  Another easily verified example is
	$K_{1,n}$ (a star).  In fact as the next two results show,
	stars are the only connected graphs for which $n_{p}(G) = n$.

	\begin{thm} 
	\label{thm:np_tree}
	For any tree $T$ with $n$ vertices, $n_{p}(T) = n$ if and only
	if $T$ has diameter at most 2; i.e., $T$ is a star.
	\end{thm}

	{\bf Proof.}  Let $T$ be a tree with $n$ verticies and diameter
	at most 2 and let $S$ be an $n_{p}$-set, that is, $S$ is a
	minimum cardinality 1-maximal nearly perfect set.  Assume the
	$|S| < n$ and let $x$ be a vertex in $V-S$.  
	Then there is a vertex $y \in (V - S) \cap N(x)$ such that 
	$y$ is adjacent to a vertex  $y'$ in $S$. Since $y \not\in S$,
	$y$ must be adjacent to some vertex $z$ in $V - S$ and $z$ must
	be adjacent to a vertex $z'$ in $S$. Now $y'$ is not adjacent
	to $z$ and $z'$ is not adjacent to $y$, for if so a cycle would
	be formed.  Thus $z',z,y,y'$ constitutes a shortest path of length
	3 from $z'$ to $y'$, contradicting the diameter of $T$.

	Conversely let $T$ be a tree with diameter at least 3.  For this
	class of trees we will prove by induction on $n$ that $n_{p}(T)
	< n$.  The only tree with diameter at least 3 and $n = 4$ is
	$P_{4}$ and by Proposition \ref{prop:npath}, $n_{p}(P_{4}) =
	2$.

	So let $T$ be a tree with $n > 4$ vertices and diameter $d$ 
	at least 3.  Let $u$ be an endvertex such 
	that $T - \{u\}$ has diameter
	at least 3.  Such a $u$ must exist as follows.  Let $w-v$ be any
	path of length $d$ ($w$ and $v$ are necessarily endvertices).
	If $d > 3$, then $diameter (T - \{u\}) \geq 3$.  If $d = 3$
	(and $n > 4$), then there is at least one endvertex $u$, not on
	this $w-v$ path.  Therefore $T - \{u\}$ has diameter at least 3.

	Let $T - \{u\}$ have diameter at least 3 and $T' = T - \{u\}$.
	Then by the inductive hypothesis $n_{p}(T') < n - 1$.  Let $S$
	be an $n_{p}$-set of $T'$.

	\paragraph{Case 1. $u$ is adjacent to a vertex in $S$}
	\hspace*{1em}\\ In this case, by Lemma \ref{lemma:small}, $S
	\cup \{u\}$ is a 1-maximal nearly perfect set of $T$ and
	therefore $n_{p}(T) < n$.

	\paragraph{Case 2.  $u$ is adjacent to vertex in $V(T') - S$}
	\hspace*{1em}\\ Let $u$ be adjacent to $v$.

	\paragraph{Case 2a.  $v$ is adjacent to a vertex in $S$}
	\hspace*{1em}\\ In this case $S$ is an $n_{p}$-set in $T$.
	Hence $n_{p}(T) <  n - 1 < n$.

	\paragraph{Case 2b.  $v$ is not adjacent to any vertex in $S$}
	\hspace*{1em}\\ By Lemma \ref{lemma:small}, $v$ must be adjacent
	to a vertex $w$ in $V(T') - S$, which in turn is adjacent to
	exactly one vertex in $S$.  In this case $S \cup \{u\}$ is a
	nearly perfect set in $T$ and, by Lemma~\ref{lemma:small}, is
	a 1-maximal nearly perfect set.  Hence $n_{p}(T) < n$.  
	$\Box$

	\begin{thm}
	For any connected graph $G$ with $n$ vertices, $n_{p}(G) = n$
	if and only if $G$ is a star.
	\end{thm}
 
	{\bf Proof.}  If $G$ is a star with $n$ vertices then $n_{p}(G)
	= n$ by Theorem~\ref{thm:np_tree}.  It remains to show that if
	$n_{p}(G) = n$ then $G$ is a star.

	\paragraph{Case 1. $G$ is acyclic} \hspace*{1em} \\
	Since $G$ is connected, G is a tree, and again by
	Theorem~\ref{thm:np_tree}, $G$ is a star.

	\paragraph{Case 2. $G$ contains a triangle} \hspace*{1em} \\
	Let the vertices of $G=(V,E)$ be ordered such that $v_{1}$,
	$v_{2}$, and $v_{3}$ form a triangle.  In this case we can
	construct a 1-minimal nearly perfect set $S$ in $G$ for which
	$|S| < n$, which implies that $n_{p}(G) < n$.  We do this as
	follows.  Initially let $S=\{v_{1}\}$.  Clearly, $S$ is a
	nearly perfect set.  Furthermore, neither $S \bigcup \{v_{2}\}$
	nor $S \bigcup \{v_{3}\}$ is a nearly perfect set.  We
	construct a 1-maximal nearly perfect set which contains
	neither $v_{2}$ nor $v_{3}$ by executing the following:
	\vspace*{0.25in} 
\newpage
\parindent=0em
	{\tt Procedure Make 1-maximal \\
		\hspace*{3em}Input: A nearly perfect set $S$ \\
		\hspace*{3em}Output: A 1-maximal nearly perfect set $S$\\
		\hspace*{3em}\\
	Begin \\
		\hspace*{3em}while $ \exists w \in V-S-\{v_{2}, v_{3}\}$ 
	for which $S \bigcup \{w\}$ is nearly perfect do \\
			\hspace*{6em} $S \leftarrow S \bigcup \{w\}$ \\
		\hspace*{3em} od \\
	End Make 1-maximal. \\
	%\vspace*{0.25in}
	}
\parindent=1em

	Clearly  when this procedure has finished, the resulting set $S$
	is nearly perfect, contains neither $v_{2}$ nor $v_{3}$,
	and for every vertex $u$ in $V-S$, $S \bigcup \{u\}$ is not a
	nearly perfect set.  Thus, $S$ is a 1-maximal nearly perfect
	set, and $|S| < n$; i.e., $n_{p}(G) < n$.

	\paragraph{Case 3. $G$ contains no triangles but contains a cycle
	of length four} \hspace*{1em} \\
	Let $C= \{v_{1}, v_{2}, v_{3}, v_{4}\}$ be the vertices
	in cyclic order of such a cycle.  As in the previous case, we
	show that we can construct a 1-maximal nearly perfect set $S$
	with $|S| < n$, which implies that $n_{p}(G) < n$.  We do this
	as follows.  Initially let $S=\{v_{1}, v_{4}\}$.  Since $G$ has
	no triangles, $S$ is a nearly perfect set.  We can now execute
	{\tt Procedure Make 1-maximal} (as defined in Case 2) and
	construct a 1-maximal nearly perfect set $S$ with $|S| < n$
	(the final set will contain neither $v_{2}$ nor $v_{3}$).

	\paragraph{Case 4. $G$ contains no triangles and no cycles of
	length four} \hspace*{1em} \\
	Let $C= \{v_{1}, v_{2}, v_{3}, v_{4}, \ldots, v_{m}\}$ 
	be the vertices, in cyclic order, of a cycle 
	in $G$, where $m \geq 5$.  Once again we construct a 1-maximal
	nearly perfect set $S$ with $|S| < n$.  Initially let
	$S=\{v_{1}, v_{4}\}$.  If $S$ is a nearly perfect set, then we
	can again apply {\tt Procedure Make 1-maximal} and construct a
	1-maximal nearly perfect set $S$ with $|S| < n$.

	If $S$ is not a nearly perfect set then there must be a vertex,
	say $w$, adjacent to both $v_{1}$ and $v_{4}$.  Note that there
	can only be one such vertex, $w$, else $G$ contains a cycle of
	length four.  Let $S=\{v_{1}, v_{4}, w\}$.  It
	follows that $S$ must be a nearly perfect set since no vertex
	can be adjacent to two of these three vertices (note that if a
	vertex is adjacent to $v_{1}$ and $w$, or $v_{4}$ and $w$ then
	$G$ must have a triangle).  Thus we can apply {\tt Procedure
	Make 1-maximal} to $S$ and construct a 1-maximal nearly perfect
	set $S$ with $|S| < n$.
	$\Box$

	\begin{prop}
	For any graph $G=(V,E)$ $n_{p}(G)=1$ if and only if there is a
	vertex $u$ in $V$ such that for every vertex $v \not = u$ there
	is a path of length two from $u$ to $v$.
	\end{prop}

	{\bf Proof.}  Clearly if such a vertex $u$ exists then the set
	$S = \{u\}$ is a 1-maximal nearly perfect set, and hence
	$n_{p}(G) = 1$.

	Conversely, let $n_{p}(G) = 1$ and let $S=\{u\}$ be a 1-maximal
	nearly perfect set.  By definition, for every vertex
	$v \not = u$ the set $S' = \{u\} \bigcup \{v\}$ is not a nearly
	perfect set.  This means that there is a third vertex $w$ which is
	adjacent to both $u$ and $v$; i.e., that there is a path of
	length two from $u$ to $v$.
	$\Box$

	\begin{cor}
	For complete graphs $K_{n}$ and wheels, $W_{n} \cong
	K_{1} + C_{n}$, $n \geq 3$, $n_{p}(K_{n}) = 1$ and
	$n_{p}(W_{n}) = 1$.
	\end{cor}

\section{Complexity Issues for  $n_{p}$ }

	In this section several complexity results are given.  A linear
	time algorithm is given which  computes the value $n_{p}(T)$
	for any tree $T$.  In the general case, however, the decision
	problem for $n_{p}(G)$ is NP-complete, even when restricted to
	bipartite or chordal graphs.

	For the first result, a dynamic programming style algorithm is
	constructed using a blend of methodologies developed by Wimer
	in 1988 \cite{w}, as illustrated in \cite{whl} and \cite{hhlpw},
	and by Mitchell in 1977 \cite{m}, as illustrated in \cite{chm}.

	The class of (rooted) trees can be constructed recursively from
	copies of a single vertex, $K_{1}$, using only one rule of
	composition.  This rule combines two rooted trees $(T_{1},
	r_{1})$ and $(T_{2}, r_{2})$ by adding an edge between $r_{1}$
	and $r_{2}$ and calling $r_{1}$ the root of the resulting
	tree.  This is denoted by $ (T,r_{1}) = (T_{1},r_{1}) \circ
	(T_{2},r_{2}).$ In particular, if $S$ is a 1-maximal nearly
	perfect set in $T$, then $S$ splits into two subsets $S_{1}$
	and $S_{2}$ according to this composition/decomposition.  In
	order to construct an algorithm for $n_{p}(T)$ it is necessary
	to characterize the classes, $TS$, of possible tree-subset
	pairs $(T,S)$ which can occur in the process of
	decomposing a tree $T$ and a 1-maximal nearly perfect set
	$S$.

	For a given set of vertices $S$, we say that a vertex $v$ has
	{\bf Property P(S)} if either $v \in S$ or there is a vertex $u$
	in the intersection of $N(v)$ and $V - S$ such that 
	$|N(u) \cap S| = 1$.

	Next we define the collection of possible tree-subset pairs
	$TS$ as the set of all ordered pairs $(T,S)$ which satisfy
	these properties:
	\begin{itemize}
	\item $T$ is a rooted tree with root $r$, 
	\item $S$ is a nearly perfect set in $T$, and
	\item if $r$ is not in $S$, then all vertices of
	$T$, except possibly those in $N[r]$, have property $P(S)$, 
	otherwise all vertices of $T$ have property $P(S)$.
	\end{itemize}

	Consider next the seven subclasses of $TS$ defined by
	Table~\ref{table:two}.  Each subclass is defined by the
	presence (indicated with $\surd$) or absence (indicated with
	$\times$) of the five properties listed in the table.  The
	symbol $r$ denotes the root of $T$.  We will denote these
	subclasses with $[i], i = 1 \ldots 7$.  Thus for example,
	subclass $[2]$ is the set of all tree-set pairs $(T,S)$ in
	which the root is not a member of $S$, $S$ is a 1-maximal
	nearly perfect set in $T$, all vertices in $T - {r}$ have
	property $P(S)$, $r$ is adjacent to some element of $S$, and
	$r$ has property $P(S)$.  Finally, note that subclasses
	[4], [5], [6] and [7] are exactly those in which $S$ is not a
	1-maximal nearly perfect set in $T$.

\begin{table}[h]
	\begin{center} \begin{tabular}{|rl|c|c|c|c|c|c|c|} \hline
	   &            & [1]     & [2] & [3]   & [4] 
			& [5]   & [6]   & [7]   \\ \hline 
	   & Property   &&&&&&& \\ \hline 
	1) & $r \in S$  & $\surd$ & $\times$ & $\times$ 
		& $\times$ & $\times$ & $\times$ & $\times$ \\ \hline 
	2)& S is 1-maximal & $\surd$  & $\surd $ & $\surd $ 
		& $\times$ & $\times$ & $\times$ & $\times$  \\ 
	  & nearly perfect in T   & & & & & & & \\ \hline 
	3)& all verticies in & $\surd$  & $\surd $ & $\surd $ 
		& $\surd $ & $\times$ & $\surd $ & $\times$  \\ 
	  & $T - r$ have property $P(S)$ & & & & & & & \\ \hline 
	4)& $|N[r] \bigcap S| = 0$ & $\times$ & $\times$ & $\surd $ 
		& $\times$ & $\surd $ & $\surd $ & $\surd $  \\ \hline 
	5)& r has property P(S) & $\surd$  & $\surd $ & $\surd $ 
		& $\times$ & $\surd $ & $\times$ & $\times$  \\ \hline
	\end{tabular} 
	\end{center} 
	\caption{} 
	\label{table:two}
	\end{table}

	\begin{lemma} $TS$ is the disjoint union of the seven classes
	defined in Table~\ref{table:two}.  \end{lemma}

	{\bf Proof.}  Since each class is defined by a unique set of
	boolean values, they must be disjoint.  It remains to show that
	every member of $TS$ is a member of some subclass.  There are
	five properties in Table~\ref{table:two}.  However property 2 :
	``S is 1-maximal nearly perfect in T'' is merely the
	intersection of property 3 and property 5 .  Thus this property
	is determined by the other two.  There are exactly 16 boolean
	assignments to the remaining four properties.  Note, however,
	if property 1 holds ($r$ is an element of $S$), then 
	properties 3 and 5 must hold while property 4 cannot hold. Thus
	the seven remaining cominations which have property 1 cannot
	occur.  Further we note that if property 1 does not hold
	and property 4 does not hold, then property 3 must hold.  So
	two more combinations are eliminated.  Hence, there can be at
	most seven nonempty subclasses of $TS$.
	$\Box$

	These subclasses and the following composition operation will
	be used in the design of the algorithm.  Let $T_{1} = (V_{1},
	E_{1})$ and $T_{2} = (V_{2}, E_{2})$ be trees with roots
	$r_{1}$ and $r_{2}$, respectively, and let $V = V_{1} \cup
	V_{2}$ and $E = E_{1} \cup E_{2}$ $\cup (r_{1},r_{2}).$  Then
	the composition of $T_{1}$ and $T_{2},$ denoted $T_{1} \circ
	T_{2},$ is the tree $T = (V,E)$ with root $r_{1}.$  For two
	tree-set pairs $(T_{1}, S_{1})$ and $(T_{2}, S_{2}),$ we will
	denote the pair $(T_{1} \circ T_{2}, S_{1} \cup S_{2})$ with
	$(T_{1}, S_{1}) \circ (T_{2}, S_{2}).$

	Given members $(T_{1}, S_{1}) \in [n]$ and $(T_{2}, S_{2}) \in
	[m]$ we can determine the class, if any, to which the pair
	$(T_{1},S_{1}) \circ (T_{2},S_{2})$ must belong.  Table 3
	summarizes these compositions.  The symbol $\times$ indicates
	that the resulting tree-set pair, though defined, is not a
	member of $TS$.

	\begin{table}[h] \begin{center}
	\begin{tabular}{|r|l|c|c|c|c|c|c|c|} \hline
		& [1]   & [2]   & [3]   & [4] & [5] & [6] & [7] \\ \hline
	[1]     & [1]   & $\times$ & [1] & $\times$   & [1] & $\times$   
		& $\times$   \\ \hline
	[2]     & $\times$  & [2] & [2] & [2] & $\times$   
		& [2] & $\times$   \\ \hline
	[3]     & [2] & [3] & [3] & [5] & $\times$   & [5] 
		& $\times$   \\ \hline
	[4]     & $\times$   & [2] & [4] & [2] & $\times$   
		& [4] & $\times$   \\ \hline
	[5]     & [2] & [5] & [5] & [5] & $\times$   & [5] 
		& $\times$   \\ \hline
	[6]     & [4] & [3] & [6] & [5] & $\times$   & [7] 
		& $\times$   \\ \hline
	[7]     & [4] & [5] & [7] & [5] & $\times$   & [7] 
		& $\times$   \\ \hline
	\end{tabular} 
	\end{center} 
	\caption{} 
	\label{table:three}
	\end{table}

	We can now derive a set of recurrence equations in terms of
	these subclasses.  By Table~\ref{table:three}  we know that

       \begin{eqnarray*}
    \verb+[1]+ & = & [1] \circ [1] \cup [1] \circ [3] \cup [1] \circ [5]  \\ 
    \verb+[2]+ & = & [2] \circ [2] \cup [2] \circ [3] \cup [2] \circ [4]
	 \cup [2] \circ [6] \cup [3] \circ [1] \cup [4] \circ [2]
	 \cup [4] \circ [4] \cup [5] \circ [1]   \\ 
    \verb+[3]+ & = & [3] \circ [2] \cup [3] \circ [3] \cup [6] \circ [2] \\ 
    \verb+[4]+ & = & [4] \circ [3] \cup [4] \circ [6] \cup [6] \circ [1]
	 \cup [7] \circ [1]  \\
    \verb+[5]+ & = & [3] \circ [4] \cup [3] \circ [6] \cup [5] \circ [2] \cup
	      [5] \circ [3] \cup [5] \circ [4] \cup [5] \circ [6] \cup
	      [6] \circ [4] \cup [7] \circ [2] \cup [7] \circ [4]  \\ 
    \verb+[6]+ & = & [6] \circ [3]  \\ 
    \verb+[7]+ & = & [6] \circ [6] \cup [7] \circ [3] \cup [7] \circ [6]  \\ 
      \end{eqnarray*}
 
	For $1 \leq i \leq 7,$ let $a_{i}(T)$ be defined as follows:
	$a_{i}(T) = min \{ |S| | S \subseteq V, (T,S) \subseteq [i]
	\}$.
 
	Then, for example, $a_{1}(T) = min \{a_{1}(T_{1}) +
	a_{1}(T_{2}), a_{1}(T_{1}) + a_{3}(T_{2}), a_{1}(T_{1}) +
	a_{5}(T_{2}) \}$
 
	To prove the correctness of this dynamic programming algorithm
	for computing $n_{p}(T)$ for any tree $T$, we would have to
	prove a theorem asserting that each of these recurrences is
	correct.  These details are straightforward and are omitted
	here.  The final step in specifying an algorithm for an
	$n_{p}$-set is to define the ``initial vector''.  In this case,
	for trees, the only basis graph is the tree with a single
	vertex, $K_{1}.$  We need to know the minimum cardinality of a
	set $S$ in a class of type $[1] \ldots [7]$ in the graph
	$K_{1}$, if any exists.  It is easy to see that the initial
	vector is $(1, \infty, \infty, \infty, \infty, 0, \infty)$
	which means that for the graph $K_{1}:$
 
     one tree-set pair of class [1] exists and its cardinality is 1;
 
     one tree-set pair of class [6] exists and its cardinality is 0;
 
     no tree-set pairs of classes [2] thru [5] or class [7] exist.
 
	We now have all of the ingredients for an $n_{p}$-set algorithm,
	where the input is the parent array Parent[1..N] for the input
	tree $T$, and where the output is $n_{p}(T)$, which is computed by
	repeatedly applying the recurrence system to each vertex in the
	parent array, with the initial vector $(1, \infty, \infty,
	\infty, \infty, 0, \infty)$ being associated with every vertex
	in the parent array as the computation begins.

 
	  The basic structure for the algorithm is a simple iteration:
	\vspace*{0.25in} \\ 
	{\tt Algorithm $n_{p}$ tree \\ 
		\hspace*{3em}Input: the parent array Parent[1..N] for 
			an arbitrary tree T \\
		\hspace*{3em}Output: $n_{p}(T)$\\
		\hspace*{3em}\\
	Begin \\
		\hspace*{3em}for i $\leftarrow$ 1 to N do\\ 
		   \hspace*{6em} initialize Vector [i,1..7]
		   $\leftarrow (1,\infty,\infty,\infty,\infty,0,\infty)$\\ 
		\hspace*{3em}od \\
		\hspace*{3em}for $j \leftarrow N$ to 2 do\\ 
		   \hspace*{6em}$ k \leftarrow Parent[j]$\\ 
		   \hspace*{6em}Combine (Vector, k, j)\\ 
		\hspace*{3em}od \\ 
		\hspace*{3em}$n_{p}(T) \leftarrow min(Vector[1,1], 
			Vector[1,2], Vector[1,3])$\\
	End $n_{p}-tree.$ \vspace*{0.25in} }
 
	The Combine procedure is derived directly from the recurrence
	system:
	\vspace*{0.25in} \\
	{\tt
	Procedure Combine (Vector,k,j) \\
	Begin \\
		\hspace*{3em}$Vector[k,1] \leftarrow$ min(Vector[k,1] + 
			Vector[j,1], Vector[k,1] + Vector[j,3], \\
			\hspace*{6em}Vector[k,1] + Vector[j,5]) \\
		\hspace*{3em}etc.\ldots \\
	End Combine
	\vspace*{0.20in}
	}
 
	\begin{thm}
	$n_{p}(T)$ can be computed for any tree $T$ with $N$ verticies
	in $O(N)$ time.
	\end{thm}

	{\bf Proof.}  The result is immediate by noting that for 
	Algorithm $n_{p}$ tree, the steps in each for-loop can be
	performed in constant time.  It follows that if the tree has
	$N$ vertices, then the algorithm operates in $O(N)$ time.
	%\vspace*{0.1in}
	$\Box$
 
	To show that the decision problem for arbitrary graphs is
	NP-complete, we need to use a known NP-completeness result,
	\vspace*{0.2in}
	called Exact Three Cover (X3C) which is defined as follows.
 
	X3C
 
     INSTANCE:  A finite set $X$ with $|X| = 3q$ and a collection $C$ of
		3-element subsets of $X$.
 
     QUESTION:  Does $C$ contain an exact cover for $X$, that is, a
		subcollection $C' \subseteq C$ such that \\  
		\hspace*{1em}every element
	\vspace*{0.2in}
		of $X$ occurs in exactly one member of $C'$?
 
     FACT:  X3C is NP-complete \cite{gj}
	\vspace*{0.2in}
 
     $n_{p}$ SET
 
     INSTANCE:  A graph $G = (V,E)$ and a positive integer $k$.
 
     QUESTION:  Is there a 1-maximal nearly perfect set $S$ contained in
     $V$ with $|S| \leq k$?


	 
	\begin{thm}
	\label{thm:np}
	$n_{p}$ SET is NP-complete, even when restricted to  bipartite
	graphs.
	\end{thm}
	{\bf Proof}.  A nondeterministic algorithm could guess a subset
	$S \subseteq V$ of $k$ vertices and, in deterministic
	polynomial time, verify whether or not $S$ is 1-maximal nearly
	perfect.  Hence the problem is in NP.  In order to show
	NP-completeness, we reduce an equivalent version of X3C (in
	which every element of $X$ lies in at least two subsets in C)
	to the $n_{p} \ SET$ problem as follows.

	Let $X = \{x_{1},x_{2}, \ldots, x_{3q}\} $ and $C = \{C_{1},
	C_{2}, \ldots, C_{m}\}$ be an instance of X3C, where $q$ and
	$m$ are positive integers and each $C_{i}$ is a 3-element
	subset of $X$.  We will show how to construct an undirected
	graph $G = (V,E)$ and a positive integer $k$ such that C
	contains an exact cover for $X$ if and only if $n_{p}(G) \leq
	k$.  First construct a collection of subgraphs, $G_{i}$, $1
	\leq i \leq m$, by adding a $P_{2}$ to a non-center vertex of a
	$K_{1,3}$ graph and label the vertices as shown in Figure 6.
	Next construct a set of $3q$ paths with $2$ vertices and label
	the vertices of each path as $x_{i}$, $y_{i}$.  Add a set of
	edges $E = \{(x_{i},c_{j}) | x_{i} \in C_{j}\}$ (cf. Figure 7).
	Finally, let $k = 3m$.  Clearly the above reduction can be
	performed in time that is polynomial in $m$ and $q$, and it is
	easy to verify that this graph G is bipartite.  We now show
	that the set $C$ contains an exact 3-cover for $X$ if and only
	if $n_{p}(G) \leq k$.

	\begin{figure}[h] 
	\begin{center} 
	\begin{picture}(40,100)
	\put(0,0){\circle{10}} \put(0,5){\line(0,1){10}}

	\put(0,20){\circle{10}}
	\put(0,25){\line(1,1){11}}
	\put(0,25){\line(-1,1){11}}

	\put(15,40){\circle{10}}
	\put(-15,40){\circle{10}}
	\put(-17,44){\line(-1,1){11}}

	\put(-30,60){\circle{10}}
	\put(-30,65){\line(0,1){10}}
	\put(-30,80){\circle{10}}

	\put(-30,89){\makebox(0,0)[b]{$a_{i}$}}
	\put(15,49){\makebox(0,0)[b]{$e_{i}$}}
	\put(11,-2){\makebox(0,0)[b]{$c_{i}$}}
	\put(11,18){\makebox(0,0)[b]{$d_{i}$}}
	\put(-41,62){\makebox(0,0)[b]{$b_{i}$}}
	\put(-23,40){\makebox(0,0)[b]{$f_{i}$}}
	\end{picture}
	\end{center}
	\caption{}
	\label{fig:six}
	\end{figure}

	\paragraph{(only if)}  Suppose that $C$ contains an exact 3-cover
	$C' \subseteq C$.  Construct a set $S = \cup V_{i}$, $i = 1
	\ldots 3$, where
		\begin{eqnarray*} 
		V_{1} & = & \{ a_{i} | 1 \leq i \leq m \} \\
		V_{2} & = & \{f(G_{i}) | 1 \leq i \leq m \} \\
		V_{3} & = & \{g(G_{i}) | 1 \leq i \leq m \} 
		\end{eqnarray*} 
	   where $f(G_{i})$ and $g(G_{i})$ are defined as follows:
	\[ 
		   f(G_{i}) = \left\{ 
			\begin{array}{ll}
				c_{i}, & if \ C_{i} \in C'\\ 
				d_{i}, & otherwise
			\end{array} \right. 
	\]
	\[ 
		   g(G_{i}) = \left\{ 
			\begin{array}{ll}
				b_{i}, & if \ C_{i} \in C'\\ 
				e_{i}, & otherwise
			\end{array} \right. 
	\]
 
	In Figure~\ref{fig:seven} the solid vertices are in $S$.  It is
	easy to verify that $S$ is a 1-maximal nearly perfect set in
	$G$ and since the cardinality of $S$ is $3m$, clearly $n_{p}(G)
	\leq 3m$.

   \begin{figure}[h]
	\begin{center}
	\begin{picture}(220,180)(0,-90)

		\put(30,0){\circle*{10}}
		\put(30,5){\line(0,1){10}}
		\put(30,20){\circle{10}}
		\put(30,25){\line(1,1){11}}
		\put(30,25){\line(-1,1){11}}
		\put(45,40){\circle{10}}
		\put(15,40){\circle{10}}
		\put(13,44){\line(-1,1){11}}
		\put(0,60){\circle*{10}}
		\put(0,65){\line(0,1){10}}
		\put(0,80){\circle*{10}}
		\put(11,78) {\makebox(0,0)[b]{$a_{1}$}}
		\put(11,58) {\makebox(0,0)[b]{$b_{1}$}}
		\put(5,38){\makebox(0,0)[b]{$f_{1}$}}
		\put(45,49){\makebox(0,0)[b]{$e_{1}$}}
		\put(41,18){\makebox(0,0)[b]{$d_{1}$}}
		\put(41,-2){\makebox(0,0)[b]{$c_{1}$}}

		\put(30,-5){\line(0,-1){40}}
		%\put(30,-5){\line(-1,-2){21}}
		\put(5,-45){\line(1,2){22}}
		%\put(30,-5){\line(4,-3){54}}
		\put(85,-45){\line(-4,3){54}}

		\put(85,0){\circle{10}}
		\put(85,5){\line(0,1){10}}
		\put(85,20){\circle*{10}}
		\put(85,25){\line(1,1){11}}
		\put(85,25){\line(-1,1){11}}
		\put(100,40){\circle*{10}}
		\put(70,40){\circle{10}}
		\put(68,44){\line(-1,1){11}}
		\put(55,60){\circle{10}}
		\put(55,65){\line(0,1){10}}
		\put(55,80){\circle*{10}}
		\put(66,78) {\makebox(0,0)[b]{$a_{2}$}}
		\put(66,58) {\makebox(0,0)[b]{$b_{2}$}}
		\put(60,38){\makebox(0,0)[b]{$f_{2}$}}
		\put(100,49){\makebox(0,0)[b]{$e_{2}$}}
		\put(96,18){\makebox(0,0)[b]{$d_{2}$}}
		\put(96,-2){\makebox(0,0)[b]{$c_{2}$}}

		\put(85,-5){\line(0,-1){40}}
		%\put(85,-5){\line(-1,-2){22}}
		\put(57.5,-45){\line(1,2){22}}
		%\put(85,-5){\line(1,-2){22}}
		\put(112.5,-45){\line(-1,2){22}}

		\put(140,20){\makebox(0,0)[b]{\ldots}}

		\put(200,0){\circle*{10}}
		\put(200,5){\line(0,1){10}}
		\put(200,20){\circle{10}}
		\put(200,25){\line(1,1){11}}
		\put(200,25){\line(-1,1){11}}
		\put(215,40){\circle{10}}
		\put(185,40){\circle{10}}
		\put(183,44){\line(-1,1){11}}
		\put(170,60){\circle*{10}}
		\put(170,65){\line(0,1){10}}
		\put(170,80){\circle*{10}}
		\put(181,78) {\makebox(0,0)[b]{$a_{m}$}}
		\put(181,58) {\makebox(0,0)[b]{$b_{m}$}}
		\put(175,38){\makebox(0,0)[b]{$f_{m}$}}
		\put(215,49){\makebox(0,0)[b]{$e_{m}$}}
		\put(212,18){\makebox(0,0)[b]{$d_{m}$}}
		\put(212,-2){\makebox(0,0)[b]{$c_{m}$}}



		\put(5,-50){\circle{10}}
		\put(5,-65){\line(0,1){10}}
		\put(5,-70){\circle{10}}
		\put(17,-50){\makebox(0,0)[b]{$x_{1}$}}
		\put(17,-70){\makebox(0,0)[b]{$y_{1}$}}

		\put(30,-50){\circle{10}}
		\put(30,-65){\line(0,1){10}}
		\put(30,-70){\circle{10}}
		\put(42,-50){\makebox(0,0)[b]{$x_{2}$}}
		\put(42,-70){\makebox(0,0)[b]{$y_{2}$}}

		\put(57.5,-50){\circle{10}}
		\put(57.5,-65){\line(0,1){10}}
		\put(57.5,-70){\circle{10}}
		\put(69.5,-50){\makebox(0,0)[b]{$x_{3}$}}
		\put(69.5,-70){\makebox(0,0)[b]{$y_{3}$}}

		\put(85,-50){\circle{10}}
		\put(85,-65){\line(0,1){10}}
		\put(85,-70){\circle{10}}
		\put(97,-50){\makebox(0,0)[b]{$x_{4}$}}
		\put(97,-70){\makebox(0,0)[b]{$y_{4}$}}

		\put(112.5,-50){\circle{10}}
		\put(112.5,-65){\line(0,1){10}}
		\put(112.5,-70){\circle{10}}
		\put(124.5,-50){\makebox(0,0)[b]{$x_{5}$}}
		\put(124.5,-70){\makebox(0,0)[b]{$y_{5}$}}

		\put(150,-70){\makebox(0,0)[b]{\ldots}}
		\put(205,-50){\circle{10}}
		\put(205,-65){\line(0,1){10}}
		\put(205,-70){\circle{10}}
		\put(217,-50){\makebox(0,0)[b]{$x_{3q}$}}
		\put(217,-70){\makebox(0,0)[b]{$y_{3q}$}}


	\end{picture}
	\end{center}
	\caption{}
	\label{fig:seven}
	\end{figure}

	\paragraph{(if)}  Now suppose $n_{p}(G) \leq k$ and let S be a
	1-maximal nearly perfect set of vertices with cardinality $\leq k$.

	Observation 1.  $a_{i} \in S$. \\*
	For if not, by Lemma~\ref {lemma:small} , $b_{i} \not \in S$ and
	$f_{i} \in S$.  But then $b_{i}$ does not satisfy Lemma \ref
	{lemma:small}  and $S$ is not a 1-maximal nearly perfect set.

	Observation 2.  $b_{i} \in S$  or $d_{i} \in S$. \\*
	This observation is true for the same reasons as in Observation 1,
	for if not, we either violate Lemma \ref{lemma:small} or the
	fact that S is 1-maximal nearly perfect.

	Observation 3.  $e_{i} \in S$  or $f_{i} \in S$ or
	    $c_{i} \in S$. \\*
	Otherwise $e_{i}$ does not satisfy Lemma \ref
	{lemma:small}  and S is not a 1-maximal nearly perfect set.

	Notice that each subgraph
	$G_{i}$ must have three vertices in $S$, thus accounting
	for  all $3m$ vertices in $S$.

	Now define $C' \subseteq C$
	as $C' = \{C_{i} | c_{i} \in S\}$.
	It follows from the
	above observations that $C'$ is an exact 3-cover for $X$.  If
	not, then some $x_{i}$ is not covered by any set in $C'$
	or some $x_{i} \in X$ is covered by more than one set in $C'$.

	If $x_{i}$ is covered by more than one set in $C'$, then $x_{i}$ is
	outside $S$ and is adjacent to two elements of $S$.  Thus $S$
	is not a nearly perfect set.  If for some $x_{i}$, $x_{i}$ is
	not adjacent to any $c_{i}$ in $S$, then $y_{i}$ could be added
	to $S$ without altering its nearly perfect status.  In
	this case $S$ would not be a 1-maximal nearly perfect set.
	$\Box$
 
	\begin{cor}
	   $n_{p}$ SET is NP-complete when restricted to chordal
	   graphs.
	\end{cor}
	{\bf Proof.}
	    Forming a clique among the $x_{i}$ vertices in the construction
	    in Theorem \ref{thm:np}, yields a graph G which is chordal.
	    The same argument holds for this graph.
	\vspace {0.2in}
	    $\Box$

	The problem of finding a smallest 1-maximal nearly perfect
  set will be NP-hard for general graphs.  For some
  NP-hard problems
  there are polynomial approximation algorithms that can find
  a solution within a constant factor $f$ of an optimal solution.  For others,
  there can be no polynomial approximation algorithms that are guaranteed to
  come within a given constant factor $f$ of an optimal solution,
  unless $P = NP$.
  With a slight modification to the construction in Theorem \ref{thm:np},
  we can show the problem of finding a smallest 1-maximal nearly
  perfect set falls into this second category.

	The proof is based upon a construction derived by Irving
	\cite{irv} which shows that independent domination cannot be
	approximated within a factor of $f$.


  A graph constructed from an instance of X3C will be described so
  that the instance of X3C will have an exact cover if and only if
  the graph has a 1-maximal nearly perfect set of cardinality $3m$, where
  $m$ is the number of subsets in the X3C instance.  It will also be
  shown that if the graph has a 1-maximal nearly perfect set of cardinality
  $\leq f * 3m$, then the X3C instance has an exact cover.

	\begin{thm}
	\label{thm:np2}
  Unless P=NP, there is no polynomial approximation algorithm A  that
  can take as input a bipartite graph $G$ and find
  a 1-maximal nearly perfect set for $G$ of cardinality within a factor $f$ of
  a smallest 1-maximal nearly perfect set.
	\end{thm}

  {\bf Proof.}  For a given constant $f$, consider the following graph
  constructed from an instance of X3C,  which is similar to the
  graph constructed in Theorem \ref{thm:np}.  Construct a collection of
  subgraphs, $G_{i}$, $1 \leq i \leq m$, by adding a $P_{2}$ to a
  non-center vertex of a $K_{1,3}$ graph and label these as shown in
  Figure 6, where $m$ refers to the number of subsets in $C$.  Next
  construct a set of $(3mf-3m+1) * 3q$ paths with $2$ vertices each and
  label the vertices of each path as $x_{i,j}$ and $y_{i,j}$, $1 \leq i
  \leq 3q$, $1 \leq j \leq 3mf-3m+1$.  Add a set of edges $E =
  \{(x_{i,j},c_{k}) | x_{i} \in C_{k}\}$.  Since $f$ is a constant, this
  construction is polynomial in $m$ and $q$.


  Using the same argument as in Theorem \ref{thm:np}, we can show that
  $G$ has a 1-maximal nearly perfect set of cardinality $\leq 3m$ if and only
  if $C$ has an exact cover.  But we can also show that $C$ has an
  exact cover if $G$ has a 1-maximal nearly perfect set of cardinality
  $\leq 3mf$.

  Let $S$ be a 1-maximal nearly perfect set for $G$ with $|S| \leq 3mf$.
  As before, let $C' = \{C_{i} | c_{i} \in S\}$.
% where $C_{i} = \{x| (c_{i},x) \in G\}$.
  It follows that $C'$ is an exact 3-cover for $X$.  If
  some $x_{i}$ had not been covered, then all $y_{i,j}$ vertices
  would have to be included in any 1-maximal nearly perfect set $S$.
  In this case,
  $|S| \ge 3mf + 1$, a contradiction.
  If $x_{i}$ is included in more than one set in $C'$, then all $x_{i,j}$
  vertices in $G$
  are adjacent to more than one element of $S$.  Thus for $S$ to
  be nearly perfect, all $x_{i,j}$ vertices must be included in $S$.
  Again this implies $|S| \ge 3fm + 1$, which is a contradiction.
  Therefore if $|S| \leq 3fm$, then $C$ has an exact cover.

	Suppose $A$ is an algorithm that can find a 
	1-maximal nearly
	perfect set within a factor $f$ of an optimal solution.  Then
	algorithm $A$ can be used to solve the decision problem for
	X3C.  In polynomial time, a graph $G$ is
	constructed as described above.  This graph is given to
	algorithm $A$ as input.  Algorithm $A$ finds a 1-maximal nearly
	perfect set with cardinality $\leq 3fm$ if and only if $C$ has
	an exact cover.  If algorithm $A$ is polynomial, then the
	decision problem for X3C is polynomial as well.
	$\Box$

  \section {  Characteristics of the Parameter $N_{p}(G)$}
 
	The parameter $N_{p}(G)$, given by the size of a largest
	1-minimal nearly perfect set, is surprisingly different from its
	counterpart $n_{p}(G).$  For example, the value of $N_{p}(G)$
	can be calculated in linear time for any graph G.  Before
	proving this, a useful characterizing lemma is necessary.
 
	\begin{lemma}
	\label{lemma:big}
	Every non-empty nearly perfect set $S$ is 1-minimal if and only
	if the subgraph induced by $S$,  $<S>,$ has minimum degree two.
	\end{lemma}
 
	{\bf Proof.}  Let $S$ be a non-empty, nearly perfect set in a
	graph $G$.  Assume $S$ is 1-minimal and let $x$ be a vertex in
	$S$.  Since $S$ is 1-minimal, we know that $S - \{x\}$ is not a
	nearly perfect set.  Thus $x$ must be adjacent to at least two
	vertices in $S$.  Since $x$ was chosen arbitrarily, the minimum
	degree of $<S>$ must be at least 2. The converse follows in
	exactly the same way. \vspace*{0.2in}
	$\Box$
 
	The following three corollaries are immediate and are given
	without proof.
 
	\begin{cor}
	\label{cor:bign}
	$N_{p}(G) = n$ if and only if $\delta(G) \geq 2.$
	\end{cor}
 
	\begin{cor}
	\label{cor:tree}
	For any tree $T$, $N_{p}(T) = 0.$
	\end{cor}
 
	\begin{cor}
	\label{cor:forest}
	For any graph $G$, $N_{p}(G) = 0$ if and only if $G$ is a forest.
	\end{cor}
	{\tt
	Algorithm $N_{p}$ \\
	\hspace*{3em}Input:  an arbitrary graph G \\
	\hspace*{3em}Output: $N_{p}(G)$ and a maximum cardinality 1-minimal
		 nearly perfect set S\\ \hspace*{3em} \\
	Begin \\
	\hspace*{3em}G' = G        \\
	\hspace*{3em}While G' has a vertex u of degree at most 1  do\\
		\hspace*{6em} V(G') = V(G') - \{u\}\\
	\hspace*{3em}od\\
	\hspace*{3em}$N_{p}(G) = |V(G')|$\\
	\hspace*{3em}S = V(G') \\
	 End $N_{p}$
	}
 
	\begin{thm}
	\label{thm:algo}
	For any graph $G$, $Algorithm \ N_{p}$ computes $N_{p}(G)$ and
	finds a maximum cardinality 1-minimal nearly perfect set $S$.
	\end{thm}
 
	{\bf Proof.}  The $N_{p}$-set $S$ which results at the end of
	Algorithm $N_{p}$ is nearly perfect.  Clearly if $S$ is empty,
	then $S$ is nearly perfect, and in this case the graph $G$ has
	no cycles, and is therefore a forest.  Corollary
	\ref{cor:forest} then shows that in this case $N_{p}(G)$ has
	been correctly calculated.
 
	Let us assume without loss of generality, that $G$ is
	connected.  Assume next that the graph $G$ has no cycle; i.e.,
	$G$ is a tree.  One can easily prove by induction, that
	Algorithm $N_{p}$ removes every vertex of $G$.  Hence Algorithm
	$N_{p}$ correctly asserts, that $N_{p}(G) = 0.$
	Assume therefore that $G$ has a cycle $C$.  Algorithm $N_{p}$
	cannot remove any vertex of $C$, regardless of the order in
	which the vertices of $G$ are removed.  For in order to remove
	a vertex of a cycle, its degree must become at most 1, which
	means that another vertex on the cycle must have been removed
	previously.
 
	Assume therefore that $S$ is not empty and further assume that
	$S$ is not a nearly perfect set.  Then there exists a vertex
	$v$ in $V - S$ which is adjacent to at least two vertices, $x$
	and $y$, in $S$.  Since $v$ is in $V - S$, Algorithm $N_{p}$
	removed $v$ from $V(G')$, implying that when it was removed its
	degree was at most 1.  This implies that either $x$ or $y$ must
	have been removed from $S$ before $v$,  which contradicts the
	assumption that $x$ and $y$ are in $S$.  Thus, $S$ is nearly
	perfect.  By Lemma \ref{lemma:big} it follows that $S$ is
	1-minimal nearly perfect.  It remains to show that $S$ has
	maximum cardinality.


	Assume that $S$ is not of maximum cardinality and let $M$ be a
	1-minimal nearly perfect set with $|M| > |S|.$ Let the vertices
	of $V(G) - S$ be ordered as $\{u_{1}, u_{2}, \ldots, u_{k}\}$ in the
	order in which they are removed by Algorithm $N_{p}$ and let $w
	= u_{i}$ be the first vertex of $M - S$ which is removed by
	Algorithm $N_{p}.$ It follows from Lemma \ref{lemma:big} that
	$w$ is adjacent to at least two vertices in $M$, say $r$ and $s$.
	But $w$ is removed by Algorithm $N_{p}$ only if its
	degree becomes at most 1,; i.e., either $r$ or $s$ must have been
	removed from $V(G')$ before $w$.  But this contradicts the
	assumption that w is the first vertex of $M - S$ which is
	removed by Algorithm $N_{p}.$ Thus $S$ is a maximum cardinality
	1-minimal nearly perfect set.
	$\Box$
 
	\begin{thm}
	\label{thm:unique}
	Every graph $G$ has a unique maximum cardinality 1-minimal nearly
	perfect set.
	\end{thm}
 
	{\bf Proof.}  We can assume without loss of generality that
	$N_{p}(G)$ $\neq 0.$  Let $S$ be produced by Algorithm
	$N_{p}$.  By Theorem \ref{thm:algo},  we know that $S$ is a
	maximum cardinality 1-minimal nearly perfect set.  Let $N$ be
	any other maximum cardinality 1-minimal nearly perfect set of
	$G$ and let w be the first vertex of $N - S$ which is removed
	by Algorithm $N_{p}$.  Since $w$ is in $N$, it must have degree
	at least 2 in $<N>$, by Lemma \ref{lemma:big}.  Let vertices $x$ and
	$y$ be vertices adjacent to $w$ in $<N>$.  Consider the point in
	Algorithm $N_{p}$ when w is removed.  Vertex $w$ can only
	be removed when its degree has become at most 1; i.e., either
	$x$ or $y$ has been previously removed.  But this contradicts
	the assumption that $w$ is the first vertex of $N - S$ that is
	removed by Algorithm $N_{p}.$  Thus $N - S$ is empty and $S$ is
	unique.
	$\Box$

 
	\begin{thm}
	For any graph $G$, its unique maximum cardinality 1-minimal
	nearly perfect set consists of the set of all vertices which
	are contained in either a cycle or a path connecting two
	disjoint cycles.
	\end{thm}
 
	{\bf Proof.}  Let us assume without loss of generality that $G$
	is connected and that $N_{p}(G) \neq 0.$
	\begin{figure}[b]
	\begin{center}
	\begin{picture}(180,60)(-60,-25)
		\put(-55,-20){\dashbox{0.8}(60,50)}
		\put(-40,0){\makebox(0,0)[t]{$G_{x}$}}
		\put(0,0){\circle{10}}
		\put(0,-12){\makebox(0,0)[t]{$x$}}
		\put(5,0){\line(1,0){10}}
		\put(20,0){\circle{10}}
		\put(20,-12){\makebox(0,0)[t]{$z$}}
		\put(25,0){\line(1,0){40}}
		\put(45,2){\makebox(0,0)[b]{$P$}}
		%\put(65,-20){\dashbox{0.8}(50,50)}
		\put(85,0){\circle{60}}
		\put(90,0){\makebox(0,0)[t]{$C$}}
	\end{picture}
	\end{center}
	\caption{}
	\label{fig:eight}
	\end{figure}
	Using an argument similar to that used in proving Theorem
	\ref{thm:algo}, one can easily show that Algorithm $N_{p}$
	cannot remove any vertex in a cycle or on a path connecting two
	disjoint cycles.  Let $x$ be any vertex in $S$ which is not on
	a cycle or a path connecting two disjoint cycles.  Since $G$ is
	connected and we have assumed that $N_{p}(G) \neq 0,$ then by
	Corollary \ref{cor:forest} $G$ must contain a cycle $C$.  Let
	$P$ be a path from $x$ to $C$.  Let $z$ be the vertex adjacent
	to $x$ on $P$ (cf. Figure~\ref{fig:eight}).  Note that the edge
	$xz$ is a bridge.  Consider the connected component $G_{x}$
	containing $x$ in $G - xz$.  It follows that $G_{x}$ is a tree
	(else $x$ is on a path connecting two disjoint cycles) and
	therefore Algorithm $N_{p}$ removes every vertex of $G_{x},$
	which contradicts the assumption that $x$ is in $S$.
	$\Box$

	In order to illustrate the data structures which may be used to
	implement this algorithm, examples are shown in Figure
	\ref{fig:nine}.  For the given graph $G$, an array Degree, 
	triply-connected adjacency lists and a removal queue Q are shown.

 
	\begin{figure}
	\begin{center}
	\begin{picture}(120,10)
 
	\put(0,0){\circle{10}}
	\put(5,0){\line(1,0){10}}
	\put(20,0){\circle{10}}
	\put(25,0){\line(1,0){10}}
	 
	\put(30,20){\circle{10}}
	\put(30,15){\line(1,-1){10}}
	\put(30,15){\line(-1,-1){10}}
	 
	\put(40,0){\circle{10}}
	\put(45,0){\line(1,0){10}}
	\put(60,0){\circle{10}}
	\put(65,0){\line(1,0){10}}
	 
	\put(70,20){\circle{10}}
	%\put(70,15){\line(1,-1){10}}
	\put(70,15){\line(-1,-1){10}}
	 
	\put(80,0){\circle{10}}
	\put(0,-7){\makebox(0,0)[t]{1}}
	\put(20,-7){\makebox(0,0)[t]{2}}
	\put(30,27){\makebox(0,0)[b]{3}}
	\put(40,-7){\makebox(0,0)[t]{4}}
	\put(60,-7){\makebox(0,0)[t]{5}}
	\put(70,27){\makebox(0,0)[b]{6}}
	\put(80,-7){\makebox(0,0)[t]{7}}
 
	\end{picture}
	\begin{tabular}{l}
	\begin{tabular}{|l|c|c|c|c|c|c|c|} \hline
	Vertex        & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
	Degree  & 1 & 3 & 2 & 3 & 3 & 1 & 1 \\ \hline
	\end{tabular} \\
	\\
	\begin{tabular}{ll|ccc|l} \cline{3-5}
	{\cal Q} & $\leftarrow$ & 1 & 6 & 7 & $\leftarrow$ \\ \cline{3-5}
	\end{tabular}
	\end{tabular}
 
	\begin{picture}(200,180)(0,10)
	\put(0,0){\framebox(10,10){7}}
		\put(22,5){\vector(1,0){15}}
		\put(22,5){\vector(-1,0){10}}
 
		\put(35,0){\framebox(10,10){.}}
		\put(45,0){\framebox(10,10){5}}
		\put(55,0){\framebox(10,10){.}}
		\put(65,0){\framebox(10,10){/}}
 
		\put(60,15){\vector(0,-1){10}}
		\put(60,15){\line(1,0){130}}
 
	\put(0,30){\framebox(10,10){6}}
		\put(22,35){\vector(1,0){15}}
		\put(22,35){\vector(-1,0){10}}
 
		\put(35,30){\framebox(10,10){.}}
		\put(45,30){\framebox(10,10){5}}
		\put(55,30){\framebox(10,10){.}}
		\put(65,30){\framebox(10,10){/}}
 
		\put(60,50){\vector(0,-1){15}}
		\put(60,50){\line(1,0){65}}
 
	\put(0,60){\framebox(10,10){5}}
		\put(22,65){\vector(1,0){15}}
		\put(22,65){\vector(-1,0){10}}
 
		\put(35,60){\framebox(10,10){.}}
		\put(45,60){\framebox(10,10){4}}
		\put(55,60){\framebox(10,10){.}}
		\put(65,60){\framebox(10,10){.}}
 
		\put(87.5,65){\vector(1,0){15}}
		\put(87.5,65){\vector(-1,0){15}}
 
		\put(100,60){\framebox(10,10){.}}
		\put(110,60){\framebox(10,10){6}}
		\put(120,60){\framebox(10,10){.}}
		\put(130,60){\framebox(10,10){.}}
 
		\put(125,50){\vector(0,1){15}}
 
		\put(152.5,65){\vector(1,0){15}}
		\put(152.5,65){\vector(-1,0){15}}
 
		\put(165,60){\framebox(10,10){.}}
		\put(175,60){\framebox(10,10){7}}
		\put(185,60){\framebox(10,10){.}}
		\put(195,60){\framebox(10,10){/}}
 
		\put(190,15){\vector(0,1){50}}
		\put(60,80){\vector(0,-1){15}}
		\put(60,80){\line(1,0){130}}
 
	\put(0,90){\framebox(10,10){4}}
		\put(22,95){\vector(1,0){15}}
		\put(22,95){\vector(-1,0){10}}
 
		\put(35,90){\framebox(10,10){.}}
		\put(45,90){\framebox(10,10){2}}
		\put(55,90){\framebox(10,10){.}}
		\put(65,90){\framebox(10,10){.}}
 
		\put(87.5,95){\vector(1,0){15}}
		\put(87.5,95){\vector(-1,0){15}}
 
		\put(100,90){\framebox(10,10){.}}
		\put(110,90){\framebox(10,10){3}}
		\put(120,90){\framebox(10,10){.}}
		\put(130,90){\framebox(10,10){.}}
 
		\put(152.5,95){\vector(1,0){15}}
		\put(152.5,95){\vector(-1,0){15}}
 
		\put(165,90){\framebox(10,10){.}}
		\put(175,90){\framebox(10,10){5}}
		\put(185,90){\framebox(10,10){.}}
		\put(195,90){\framebox(10,10){/}}
 
		\put(190,80){\vector(0,1){15}}
		\put(60,110){\vector(0,-1){15}}
		\put(60,110){\line(1,0){130}}
 
	\put(0,120){\framebox(10,10){3}}
		\put(22,125){\vector(1,0){15}}
		\put(22,125){\vector(-1,0){10}}
 
		\put(35,120){\framebox(10,10){.}}
		\put(45,120){\framebox(10,10){2}}
		\put(55,120){\framebox(10,10){.}}
		\put(65,120){\framebox(10,10){.}}
 
		\put(87.5,125){\vector(1,0){15}}
		\put(87.5,125){\vector(-1,0){15}}
 
		\put(100,120){\framebox(10,10){.}}
		\put(110,120){\framebox(10,10){4}}
		\put(120,120){\framebox(10,10){.}}
		\put(130,120){\framebox(10,10){/}}
 
		\put(125,110){\vector(0,1){12}}
		\put(125,110){\vector(0,-1){12}}
 
		\put(60,140){\vector(0,-1){15}}
		\put(60,140){\line(1,0){65}}
 
	\put(0,150){\framebox(10,10){2}}
		\put(22,155){\vector(1,0){15}}
		\put(22,155){\vector(-1,0){10}}
 
		\put(35,150){\framebox(10,10){.}}
		\put(45,150){\framebox(10,10){1}}
		\put(55,150){\framebox(10,10){.}}
		\put(65,150){\framebox(10,10){.}}
 
		\put(87.5,155){\vector(1,0){15}}
		\put(87.5,155){\vector(-1,0){15}}
 
		\put(100,150){\framebox(10,10){.}}
		\put(110,150){\framebox(10,10){3}}
		\put(120,150){\framebox(10,10){.}}
		\put(130,150){\framebox(10,10){.}}
 
		\put(152.5,155){\vector(1,0){15}}
		\put(152.5,155){\vector(-1,0){15}}
 
		\put(165,150){\framebox(10,10){.}}
		\put(175,150){\framebox(10,10){4}}
		\put(185,150){\framebox(10,10){.}}
		\put(195,150){\framebox(10,10){/}}
 
		\put(190,110){\vector(0,1){50}}
		\put(125,140){\vector(0,1){15}}
 
	\put(0,180){\framebox(10,10){1}}
		\put(22,185){\vector(1,0){15}}
		\put(22,185){\vector(-1,0){10}}
 
		\put(60,170){\vector(0,1){12}}
		\put(60,170){\vector(0,-1){12}}
 
		\put(35,180){\framebox(10,10){.}}
		\put(45,180){\framebox(10,10){2}}
		\put(55,180){\framebox(10,10){.}}
		\put(65,180){\framebox(10,10){/}}
 
 
	\end{picture}
	\end{center}
	\caption{}
	\label{fig:nine}
	\end{figure}
 
	\begin{thm}
	Algorithm $N_{p}$ can be implemented to run in $O(|E| + |V|)$ time .
	\end{thm}
 
	{\bf Proof.}  We can assume that the input to Algorithm $N_{p}$
	consists of a list of vertices and a list of edges (ordered
	pairs of vertices).  The data structures in Figure 9,
	consisting of a triply-linked list of adjacencies and an array
	$(1 \ldots n)$ of vertex degrees, can be constructed in
	$O(|E|)$ time.  In $O(|V|)$ time the vertices of degree at most
	1 can be inserted into a simple queue $Q$.  In $O(1)$ time
	Algorithm $N_{p}$ can then remove a vertex of degree at most 1
	from $Q$ and update the linked lists, the array Degree, and the
	queue Q.  Thus, the loop in Algorithm $N_{p}$ can be executed
	in $O(|V|)$ time.
	$\Box$

\quad
\baselineskip=12pt
\parindent=0pt
 
\begin{thebibliography}{1}
 
\bibitem{bcm}
B. Bollob$\acute{a}$s, E.J. Cockayne, C.M. Mynhardt.
\newblock On generalized minimal domination parameters for
paths.
\newblock {\em Discrete Math.}, 86(1990), 89-97.
 
\bibitem{chhl}
E.J. Cockayne, B.L. Hartnell, S.T. Hedetniemi, R. Laskar.
\newblock Perfect domination in graphs.
\newblock to appear in J. Combinatorics Inform. Systems Sci.
 
\bibitem{chm}
E.J. Cockayne, S.T. Hedetniemi, and S. Mitchell.
\newblock Linear algorithms on recursive representations of trees.
\newblock J. Comp. Systems Sci. 18(1979), 76-85.
 
\bibitem{cm}
E.J. Cockayne and C.M. Mynhardt.
\newblock On the product of k-minimal domination numbers of a graph and
its complement.
\newblock J. Comb. Math. Comb. Computing 8(1990), 118-122.
 
\bibitem{cmm}
E.J. Cockayne, G. MacGillivray, and C.M. Mynhardt.
\newblock Generalized maximal independence parameters for paths and cycles.
\newblock {\it Quaestiones Math.}  13(1990), 123-139.
 
\bibitem{gj}
M.R. Garey and D.S. Johnson.
\newblock Computers and Intractability: A Guide to the Theory of
 NP-Completeness.
 \newblock (Freeman, New York, 1979.).
 
 \bibitem{hhlpw}
 E.O. Hare, S.T. Hedetniemi, R. Laskar, K. Peters, and T.V. Wimer.
 \newblock Linear time computability of combinatorial problems on
 generalized-series-parallel graphs.
 \newblock Discrete Algorithms and Complexity, Proc. of the Japan-
 U.S. Joint Seminar, Perspectives in Computing, Vol. 15, D.S.Johnson, ed.,
 Academic Press. 1987, pp. 437 - 457.
 
\bibitem{irv}
%Robert W. Irving.
R. W. Irving.
\newblock On approximating the minimum independent dominating set.
\newblock {\em Inform. Process. Lett.}, 37(4):(1991), 197-200.

\bibitem{m}
S.L.Mitchell.
\newblock Algorithms on trees and maximal outerplanar graphs: design,
complexity analysis and data structures study.
\newblock Ph.D. Thesis, Dept. of Applied Mathematics and Computer Science,
University of Virginia, 1977.
 
\bibitem{w}
T.V. Wimer.
\newblock Linear algorithms on k-terminal graphs.
\newblock Ph.D. Thesis, Dept. of Computer Science, Clemson University, 1987.
 
\bibitem{whl}
T.V. Wimer, S.T. Hedetniemi, and R. Laskar.
\newblock A methodology for constructing linear graph algorithms.
\newblock {\it Congr. Numer.} 50(1985), 43-60.
 
 
\end{thebibliography}
\end{document}
