% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} \usepackage{tikz} \usetikzlibrary{calc} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%% NEW COMMANDS \newcommand{\TR}[1]{\mbox{$\tau(#1)$}} \newcommand{\DTR}[1]{\mbox{$\tau_D(#1)$}} \newcommand{\ITR}[1]{\mbox{$\tau_I(#1)$}} \newcommand{\gt}{\gamma_t} \newcommand{\gB}{\gamma^d_B} \newcommand{\gBo}{\gamma^d_1} \newcommand{\gBt}{\gamma^d_2} \newcommand{\coro}{\mathop{\mathrm{cor}}} \newcommand{\ecoro}{\mathop{\mathrm{ecor}}} \newcommand{\ioc}{\gamma^{{\rm {\small IOC}}}} \newcommand{\xiD}[1]{\xi^{\Delta}(#1)} \newcommand{\tran}[1]{\mbox{$\tau(#1)$}} \newcommand{\tranP}[1]{\mbox{$\tau_{\cP}(#1)$}} \newcommand{\tranD}[1]{\tau^{\Delta}(#1)} \newcommand{\xim}[1]{\mbox{$\xi(#1)$}} \newcommand{\ximD}[1]{\xi^{\Delta}(#1)} \newcommand{\match}[1]{\mbox{$\alpha'(#1)$}} \newcommand{\matchD}[1]{\alpha^{\Delta}(#1)} \newcommand{\ClaimX}[2]{{\bf Claim #1:} {\em #2} \vspace{0.08cm} } \newcommand{\ClX}[1]{\mbox{Claim #1}} \newcommand{\sdt}{{\rm{{sd}_{\gamma_t}}}} %\newcommand{G_{\bowtie}}{{G \Box K_2(1)}} \newcommand{\sd}{{\rm{{sd}_{\gamma_t}}}} \newcommand{\gtD}{\gamma_t^D} \newcommand{\ONH}{{\rm ONH}} \newcommand{\odd}{\rm{odd}} \newcommand{\diam}{{\rm diam}} \newcommand{\pn}{{\rm pn}} \newcommand{\epn}{{\rm epn}} \newcommand{\ipn}{{\rm ipn}} \newcommand{\sta}{{\rm sta}} %\newcommand{\boxminus}{\Box} %\newcommand{\mod}{{\rm mod}} \newcommand{\pr}{{\rm pr}} \newcommand{\gbar}{{\overline{G}}} \newcommand{\Hbar}{\overline{H}} \newcommand{\vbar}{{\overline{v}}} %\newcommand{\qed}{$\Box$} \newcommand{\vs}{\vspace{0.2cm}} %\newcommand{\proof}{\noindent\textbf{Proof. }} \newcommand{\smallqed}{{\tiny ($\Box$)}} \newcommand{\Is}{{\rm I}} \newcommand{\p}{{\rm P}} \newcommand{\T}{{\rm T}} \newcommand{\B}{{\rm B}} \newcommand{\cP}{{\cal P}} \newcommand{\1}{\vspace{0.1cm}} \newcommand{\2}{\vspace{0.2cm}} \newcommand{\3}{\vspace{0.3cm}} \def \nB {n_{B}} \def \nZ {n_{Z}} \def \nH {n_{H}} \def \nF {n_{F}} \def \nFp {n_{F}'} \newcommand{\oo}{{\rm o}} \newcommand{\cA}{{\cal A}} \newcommand{\cC}{{\cal C}} \newcommand{\cB}{{\cal B}} \newcommand{\cF}{{\cal F}} \newcommand{\cG}{{\cal G}} \newcommand{\cH}{{\cal H}} \newcommand{\cI}{{\cal I}} \newcommand{\cL}{{\cal L}} \newcommand{\cT}{{\cal T}} \newcommand{\wtF}{\widetilde{F}} \newcommand{\dk}{\gamma_{\le k}} %add to all preambles \newcommand{\dtwo}{\gamma_{\le 2}}%add to all preambles \newcommand{\dthree}{\gamma_{\le 3}}%add to all preambles \def\vertex(#1){\put(#1){\circle*{2}}} \def\vertexo(#1){\put(#1){\circle{2}}} \def\vert(#1){\put(#1){\circle*{1.5}}} \def\verto(#1){\put(#1){\circle{1.5}}} \def\lab(#1)#2{\put(#1){\makebox(0,0)[c]{#2}}} \setlength{\unitlength}{1mm} \newenvironment{unnumbered}[1]{\trivlist \item [\hskip \labelsep {\bf #1}]\ignorespaces\it}{\endtrivlist} \newenvironment{claimn}{\textsc{Claim:}}{\par\noindent} \newcommand{\claimproof}{\textsc{Proof.} } \newcommand{\NEW}[1]{{\bf #1}} %%%%%%%%%%%%%%%% %% END NEW COMMANDS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Identifying Vertex Covers in Graphs} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Michael A. Henning\thanks{Research supported in part by the South African National Research Foundation and the University of Johannesburg.} \\ \small Department of Mathematics\\[-0.8ex] \small University of Johannesburg\\[-0.8ex] \small Auckland Park, 2006 South Africa\\ \small\tt mahenning@uj.ac.za \\ \and Anders Yeo\\ \small Department of Mathematics\\[-0.8ex] \small University of Johannesburg\\[-0.8ex] \small Auckland Park, 2006 South Africa\\ \small\tt anders.yeo.work@gmail.com } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\ \small Mathematics Subject Classifications: 05C69} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} An identifying vertex cover in a graph $G$ is a subset $T$ of vertices in $G$ that has a nonempty intersection with every edge of $G$ such that $T$ distinguishes the edges, that is, $e \cap T \ne \emptyset$ for every edge $e$ in $G$ and $e \cap T \ne f \cap T$ for every two distinct edges $e$ and $f$ in $G$. The identifying vertex cover number $\DTR{G}$ of $G$ is the minimum size of an identifying vertex cover in $G$. We observe that $\DTR{G} + \rho(G) = |V(G)|$, where $\rho(G)$ denotes the packing number of $G$. We conjecture that if $G$ is a graph of order~$n$ and size~$m$ with maximum degree~$\Delta$, then $\DTR{G} \le \left( \frac{\Delta(\Delta - 1)}{\Delta^2 + 1} \right) n + \left( \frac{2}{\Delta^2 + 1} \right) m$. If the conjecture is true, then the bound is best possible for all $\Delta \ge 1$. We prove this conjecture when $\Delta \ge 1$ and $G$ is a $\Delta$-regular graph. The three known Moore graphs of diameter~$2$, namely the $5$-cycle, the Petersen graph and the Hoffman-Singleton graph, are examples of regular graphs that achieves equality in the upper bound. We also prove this conjecture when $\Delta \in \{2,3\}$. % keywords are optional \bigskip\noindent \textbf{Keywords:} Vertex cover, Identifying vertex cover, Transversal. \end{abstract} \section{Introduction} For notation and graph theory terminology, we in general follow~\cite{hhs}. Specifically, let $G = (V,E)$ be a graph with vertex set $V = V(G)$, edge set $E = E(G)$, order~$n(G) = |V|$ and size~$m(G) = |E|$. The \emph{open neighborhood} of a vertex $v \in V$ is $N_G(v) = \{u \in V \, | \, uv \in E(G)\}$ and its \emph{closed neighborhood} is the set $N_G[v] = N_G(v) \cup \{v\}$. The degree of $v$ is $d_G(v) = |N_G(v)|$. If the graph $G$ is clear from the context, we simply write $n$, $m$, $N(v)$, $N[v]$ and $d(v)$ rather than $n(G)$, $m(G)$, $N_G(v)$, $N_G[v]$ and $d_G(v)$, respectively. The set of vertices at distance~$2$ from a vertex~$v$ in $G$ we denote by $N_2(G;v)$, or simply by $N_2(v)$ is the graph $G$ is clear from the context. A \emph{subcubic graph} is a graph with maximum degree~$3$. A path and a cycle on $n$ vertices are denoted by $P_n$ and $C_n$, respectively. For a set $S \subseteq V$, its \emph{open neighborhood} is the set $N(S) = \cup_{v \in S} N(v)$ and its \emph{closed neighborhood} is the set $N[S] = N(S) \cup S$. % A set $S$ of vertices in $G$ is a \emph{packing} if the vertices of $S$ are pairwise at distance at least~$3$ apart in $G$; that is, for distinct vertices $u$ and $v$ in $S$, we have $d_G(u,v) \ge 3$ or, equivalently, $N[u] \cap N[v] = \emptyset$. The \emph{packing number} $\rho(G)$ of $G$ is the maximum cardinality of a packing in $G$. A packing of cardinality $\rho(G)$ in $G$ is called a $\rho(G)$-packing. A vertex and an edge are said to \emph{cover} each other in a graph $G$ if they are incident in $G$. A (vertex) \emph{cover} in $G$ is a set of vertices that covers all the edges of $G$. We remark that a cover is also called a \emph{transversal} or \emph{hitting set} in the literature. Thus a cover $T$ has a nonempty intersection with every edge of $G$. The (vertex) \emph{covering number} $\TR{G}$ of $G$ is the minimum cardinality of a cover in $G$. A cover of size~$\TR{G}$ is called a $\TR{G}$-cover. % We say that an edge $e$ in $G$ is \emph{covered} by a set $T$ if $e \cap T \ne \emptyset$. In particular, if $T$ is a cover in $G$, then $T$ covers every edge of $G$. We define a subset $T$ of vertices in $G$ to be an \emph{identifying vertex cover}, abbreviated \emph{id}-\emph{cover}, if $T$ is a cover in $G$ that distinguishes the edges, that is, $e \cap T \ne f \cap T$ for every two distinct edges $e$ and $f$ in $G$. We remark that every graph has an id-cover since $V(G)$ is such a set. The \emph{identifying vertex covering number}, abbreviated \emph{id}-\emph{covering number}, $\DTR{G}$ of $G$ is the minimum size of an id-cover in $G$. An id-cover of size~$\DTR{G}$ is called a $\DTR{G}$-cover. Julien Moncel\footnote{We remark that Moncel used slightly different terminology to the authors and viewed a packing as an error-correcting code.} in his PhD thesis (in French) was the first to observe that an id-cover is precisely the complement of a packing. \begin{observation}{\rm (\cite{Moncel})} A set of vertices in a graph is an id-cover if and only if it is the complement of a packing. \label{ob:Moncel} \end{observation} As an immediate consequence of Observation~\ref{ob:Moncel}, we have the following relationship between the id-covering number and the packing number of a graph. \begin{corollary}{\rm (\cite{Moncel})} For every graph $G$, we have $\DTR{G} + \rho(G) = |V(G)|$. \label{packing} \end{corollary} Covers in graphs and more generally, transversals in hypergraphs, are very well studied in the literature. Identifying vertex covers in graphs and hypergraphs have applications, for example, in identifying open codes (also called \emph{open-locating-dominating sets} or a \emph{strong identifying codes} in the literature (see, for example,~\cite{HeYe12,HoLaRa02,SeSl10,SeSl11}). Identification of edges of a graph have been studied, for example, in~\cite{HoKaLi01,HoKaLi03} and elsewhere. We remark that there is a strong link between id-covers in graphs and \emph{test covers}, which are studied for example in~\cite{MoSh85}. An id-cover is both a set cover and a test cover of a $2$-regular hypergraph. The dual case of test covers of graphs was studied in~\cite{TestCover}. Recently the authors~\cite{HeYe12} obtained results on identifying open codes in cubic graphs using distinguishing transversal in hypergraphs. A bibliography of papers concerned with identifying codes, currently listing over 170 papers, is maintained by Lobstein~\cite{Lobstein}. \section{Main Results} Our aim in this paper is to establish an upper bound on the identifying vertex covering number of a graph in terms of its order, size and maximum degree. In particular, we establish upper bounds on the id-covering number of a regular graph in terms of its order and size and of a subcubic graph in terms of its order and size. The results we present in this paper on id-covers in graphs give support for the following conjecture. \begin{conjecture} If $G$ is a graph of order~$n$ and size~$m$ with maximum degree~$\Delta$, then \[ \DTR{G} \le \left( \frac{\Delta(\Delta - 1)}{\Delta^2 + 1} \right) n + \left( \frac{2}{\Delta^2 + 1} \right) m. \] \label{conj1} \end{conjecture} When $\Delta = 1$, the bound in Conjecture~\ref{conj1} simplifies to $\DTR{G} \le m$, which is trivially true since in this case $G$ consists of a disjoint union of copies of $K_1$ and $K_2$. % In this paper, we prove the following results. Proofs of Theorem~\ref{thmDreg}, Theorem~\ref{thmD2} and Theorem~\ref{thmD3} are given in Section~\ref{S:Dreg}, Section~\ref{S:D2} and Section~\ref{S:D3}, respectively. \begin{theorem} Conjecture~\ref{conj1} is true when $\Delta \ge 1$ and $G$ is a $\Delta$-regular graph. \label{thmDreg} \end{theorem} \begin{theorem} Conjecture~\ref{conj1} is true when $\Delta = 2$. \label{thmD2} \end{theorem} \begin{theorem} Conjecture~\ref{conj1} is true when $\Delta = 3$. \label{thmD3} \end{theorem} %Proofs of Theorem~\ref{thmDreg}, \ref{thmD2} and~\ref{thmD3} are %given in Sections~\ref{S:Dreg}, \ref{S:D2} and~\ref{S:D3}, %respectively. Recall (or see~\cite{HoSi60,Si68}) that the Moore graphs of diameter~$2$ are $\Delta$-regular graphs (of girth~$5$) and order $n=\Delta^2+1$ and exist for $\Delta = 2, 3, 7$ and possibly $57$, but for no other degrees. The Moore graphs for the first three values of $\Delta$ are unique, namely \2 \indent $\bullet$ The 5-cycle ($2$-regular graph on $n = 5$ vertices) \\ \indent $\bullet$ The Petersen graph ($3$-regular graph on $n = 10$ vertices) \\ \indent $\bullet$ The Hoffman-Singleton graph ($7$-regular graph on $n = 50$ vertices). \2 Since these graphs $G$ have diameter~$2$, their packing number $\rho(G) = 1$, implying by Corollary~\ref{packing} that $\DTR{G} = n - 1$. However in this case the conjectured bound in Conjecture~\ref{conj1} simplifies to precisely~$n-1$. Hence the bound in Conjecture~\ref{conj1} is achieved by the three known Moore graphs of diameter~$2$. We remark that if Conjecture~\ref{conj1} is true, then the bound is best possible due to the star $G = K_{1,\Delta}$, where $\Delta \ge 1$, which has order~$n = \Delta+1$, size~$m = \Delta$, maximum degree~$\Delta$ and $\tau_D(G)=\Delta$, implying that \[ \tau_D(G) = \Delta = \frac{ \Delta(\Delta - 1)(\Delta + 1)}{\Delta^2 + 1} + \frac{2 \Delta}{\Delta^2 + 1} = \left( \frac{\Delta(\Delta - 1)}{\Delta^2 + 1} \right) n + \left( \frac{2}{\Delta^2 + 1} \right) m . \] Although we have yet to find a family of connected graphs with arbitrary large order relative to the maximum degree that achieve equality in the bound of Conjecture~\ref{conj1}, there are such graphs with id-covering number arbitrarily close to the conjectured bound. For example, for $s < \Delta$ if we take $s$ disjoint copies of a star $K_{1,\Delta}$ and add $s-1$ edges by joining a leaf from one of the stars to a leaf from each of the other stars, and denote the resulting connected graph by $G$ and its order by~$n$, then $\DTR{G} = n-s$, while the upper bound in Conjecture~\ref{conj1} simplifies to $n-s + 2(s-1)/(\Delta^2+1)$ which can be made arbitrarily close to $\DTR{G}$ by letting $s \ll \Delta$. \section{Proof of Theorem~\ref{thmDreg}} \label{S:Dreg} In this section, we give a proof of Theorem~\ref{thmDreg}. We first present the following theorem. \begin{theorem} If $G$ is a graph of order~$n$ with maximum degree~$\Delta$, then \[ \DTR{G} \le \left( \frac{\Delta^2}{\Delta^2 + 1} \right) n. \] \label{DTR_k=2} \end{theorem} \begin{proof} Let $S$ be a $\rho(G)$-packing. Then, $N(v) \cup N_2(v) \subseteq V \setminus S$ for every vertex $v \in S$. Further if $u \notin S$, then, by the maximality of $S$, we must have that $d(u,v) \le 2$ for some vertex $v \in S$, implying that \[ V \setminus S = \bigcup_{v \in S} ( N(v) \cup N_2(v)). \] Hence since $|N(v)| \le \Delta$ and $|N_2(v)| \le |N(v)| (\Delta - 1)$ for each $v \in S$, we have that \[ n - |S| = |V \setminus S| \le \sum_{v \in S} \left(|N(v)| + |N_2(v)|\right) \le \Delta^2 \cdot |S|, \] and so, $\rho(G) = |S| \ge n/(\Delta^2 + 1)$. The desired result now follows from Corollary~\ref{packing}.\end{proof} \medskip As a consequence of Theorem~\ref{DTR_k=2}, we can readily deduce Theorem~\ref{thmDreg}. Recall its statement. \medskip \noindent \textbf{Theorem~\ref{thmDreg}}. \emph{If $G$ is a $\Delta$-regular graph of order~$n$ and size~$m$, then \[ \DTR{G} \le \left( \frac{\Delta(\Delta - 1)}{\Delta^2 + 1} \right) n + \left( \frac{2}{\Delta^2 + 1} \right) m. \] } \\ \begin{proof} Since $G$ is a $\Delta$-regular graph, $2m = \Delta n$. Hence by Theorem~\ref{DTR_k=2}, we have \[ \begin{array}{lcll} \2 \DTR{G} & \le & \displaystyle{ \left( \frac{\Delta^2}{\Delta^2 + 1} \right) n } & \\ \2 & = & \displaystyle{ \left( \frac{\Delta^2 - \Delta}{\Delta^2 + 1} \right) n + \left( \frac{\Delta}{\Delta^2 + 1} \right) n } & \\ \2 & = & \displaystyle{ \left( \frac{\Delta^2 - \Delta}{\Delta^2 + 1} \right) n + \left( \frac{2}{\Delta^2 + 1} \right) m. } & \hspace*{0.5cm} \\ \2 \end{array} \] %as desired. \end{proof} As observed earlier, the 5-cycle ($2$-regular graph on $n = 5$ vertices), the Petersen graph ($3$-regular graph on $n = 10$ vertices) and the Hoffman-Singleton graph ($7$-regular graph on $n = 50$ vertices) are examples of regular graphs that achieve equality in the bound of Theorem~\ref{thmDreg}. \section{Proof of Theorem~\ref{thmD2}} \label{S:D2} The packing number of a path and a cycle is well-known. Hence using the relationship between the id-covering number and the packing number of a graph in Corollary~\ref{packing}, we have the following result. \begin{proposition} The following holds. \\ \indent {\rm (a)} For $n \ge 1$, $\DTR{P_n} = \lfloor 2n/3 \rfloor$. \\ \indent {\rm (b)} For $n \ge 3$, $\DTR{C_n} = \lceil 2n/3 \rceil$. \label{cycle} \end{proposition} As a consequence of Proposition~\ref{cycle}, we have that if $G$ is a path on $n$ vertices and $m$ edges, then $\DTR{G} \le 2(2n-1)/5 = 2(n + m)/5$ with equality if and only if $G = P_3$. Further if $G$ is a cycle on $n$ vertices and $m$ edges, then $\DTR{G} \le 4n/5 = 2(n + m)/5$ with equality if and only if $G = C_5$. Hence we have the following result, which proves Theorem~\ref{thmD2}. \begin{theorem} If $G$ is a graph of order~$n$ and size~$m$ with maximum degree~$2$, then $\DTR{G} \le 2(n + m)/5$ with equality if and only if every component of $G$ is a path $P_3$ or a cycle $C_5$. \label{tD2} \end{theorem} \section{Proof of Theorem~\ref{thmD3}} \label{S:D3} In order to prove Theorem~\ref{thmD3}, we prove a stronger result. For this purpose, we shall need the following notation. % Let $G = (V,E)$ be a graph. % We call $\cP = (E_2,F_2)$ a $2$-edge-partition of $E$ if $\cP$ is a weak partition of $E$ (that is, some of the subsets of the partition may be empty) such that $E_2 \cup F_2 = E$. Let $T$ be a cover in $G$ such that the edges in $F_2$ are distinguished, i.e., if $e, f \in F_2$ and $e \ne f$, then $e \cap T \ne f \cap T$. We call $T$ a $\cP$-cover of $G$. We call an edge in $E_2$ an $E_2$-edge and an edge in $F_2$ an $F_2$-edge. We define the $\cP$-covering number of $G$, denoted $\tranP{G}$, to be the minimum cardinality of a $\cP$-cover in $G$. Let $X$ be a subset of vertices in $G$ (possibly, $X = \emptyset$). For a given $2$-edge-partition $\cP$ of $E$, let $T$ be chosen to be a $\cP$-cover of $G$ such that $X \subseteq T$. We call such a $\cP$-cover $T$ a $(\cP,X)$-cover of $G$ and we define the $(\cP,X)$-covering number of $G$, denoted $\tran{G;\cP,X}$ to be the minimum size of a $(\cP,X)$-cover in $G$. If $X = \emptyset$, a $(\cP,X)$-cover of $G$ is a $\cP$-cover of $G$ and we write $\tran{G;\cP}$ rather than $\tran{G;\cP,X}$. % In order to prove Theorem~\ref{thmD3}, we need to prove the following stronger result. %We shall prove the following: \begin{theorem} Let $G = (V,E)$ be a graph with $\Delta(G) \le 3$ and let $\cP = (E_2,F_2)$ be a $2$-edge-partition of $E$ and let $X \subseteq V$. Then, \[ 10\tran{G;\cP,X} \le 6 n(G) + 2|F_2| + |E_2| + 4|X|. \] \label{main2} \end{theorem} \begin{proof} Define $\xi(G;\cP,X) = 6 n(G) + 2|F_2| + |E_2| + 4|X|$ for all graphs $G$ with associated $2$-edge-partition $\cP$ and subset $X \subseteq V$. We wish to prove that $10\tran{G;\cP,X} \le \xi(G;\cP,X)$ when $\Delta(G) \le 3$. Assume that the theorem is false. Among all counterexamples, let $G = (V,E)$ with associated $2$-edge-partition $\cP$ and subset $X \subseteq V$ be chosen so that \noindent \hspace*{1cm} (1) $G$ has minimum order~$n(G)$. \\ \hspace*{1cm} (2) Subject to (1), $|F_2|$ is a minimum. Since $G$ is a counterexample to the theorem, $10\tran{G;\cP,X} > \xi(G;\cP,X)$. Clearly, $|E| \ge 1$, for otherwise $10\tran{G;\cP,X} = 10|X| \le 6n(G) + 4|X| = \xi(G;\cP,X)$, a contradiction. Further, $n(G) \ge 3$, for otherwise $10\tran{G;\cP,X} = 10 < \xi(G;\cP,X)$ if $|X|<2$ and $10\tran{G;\cP,X} = 20 < \xi(G;\cP,X)$ if $|X|=2$, a contradiction. If $G$ is not connected, then by the minimality of the order of $G$ the theorem holds for all components of $G$ and therefore for $G$. This is a contradiction to $G$ being a counterexample. Hence, $G$ is connected. We will now prove a number of claims. In these claims we shall adopt the following notation. Let $G' = (E',V')$ be a graph with $\Delta(G') \le 3$ and let $\cP' = (E_2',F_2')$ be a $2$-edge-partition of $E'$ and let $X' \subseteq V'$. We now define \[ \begin{array}{lcl} \xiD{G';\cP',X'} & = & \xi(G;\cP,X)-\xi(G';\cP',X') \\ \tranD{G';\cP',X'} & = & \tran{G;\cP,X} - \tran{G';\cP',X'}. \end{array} \] The usefulness of these definitions will become clear in Lemma~\ref{key_lem} and the following claims. We shall invoke Lemma~\ref{key_lem} throughout the proof of Theorem~\ref{main2}. The essential idea when applying Lemma~\ref{key_lem} is to prove properties on the structure of $G=(V,E)$ with associated $2$-edge-partition $\cP$ and subset $X \subseteq V$ by extending a cover of a modified instance $G'=(V',E')$ with associated $2$-edge-partition $\cP'$ and subset $X' \subseteq V'$ that is smaller than $G$ in terms of the order defined by conditions~(a) and~(b) in Lemma~\ref{key_lem} and deriving a contradiction. \3 \begin{lemma} If $G' = (E',V')$ is a graph, $X' \subseteq V'$, and $\cP' = (E_2',F_2')$ a $2$-edge-partition of $E'$ such that $\xiD{G';\cP',X'} \ge 10 \tranD{G';\cP',X'}$, then the following hold. \\ \indent {\rm (a)} $n(G') \ge n(G)$. \\ \indent {\rm (b)} If equality holds in {\rm (a)}, then $|F_2'| \ge |F_2|$. \label{key_lem} \end{lemma} \begin{proof} Suppose to the contrary that such a graph $G'$, subset $X'$, and associated $2$-edge-partition $\cP'$ exists such that (a) or (b) do not hold. By the minimality of $G$ we have $10\tran{G';\cP',X'} \le \xi(G';\cP',X')$. By assumption, $\xiD{G';\cP',X'} \ge 10 \tranD{G';\cP',X'}$. Hence, $\xi(G;\cP,X)-\xi(G';\cP',X') = \xiD{G';\cP',X'} \ge 10 \tranD{G';\cP',X'} = 10\tran{G;\cP,X} - 10 \tran{G';\cP',X'} \ge 10\tran{G;\cP,X} - \xi(G';\cP',X')$, and so, $\xi(G;\cP,X) \ge 10\tran{G;\cP,X}$, a contradiction.\end{proof} \3 \noindent \ClaimX{A}{$X = \emptyset$.} \\ \begin{proof} Suppose that $X \ne \emptyset$. Suppose that there exist distinct edges $e_1, e_2 \in F_2$ that intersect $X$ such that $e_1 \cap X = e_2 \cap X$. Then, $|e_1 \cap X| = 1$. Let $e_1 = \{v,v_1\}$ and $e_2 = \{v,v_2\}$. Let $G'$ be obtained from $G - \{e_1,e_2\}$ by adding the edge $e' = \{v_1,v_2\}$ if this edge does not already exist. Let $\cP' = (E_2',F_2')$, where $E_2' = E_2 \cup \{e'\}$ and $F_2' = F_2 \setminus \{e_1,e_2\}$. Let $X' = X$. Then, $n(G') = n(G)$, $|E_2'| \le |E_2| + 1$, $|F_2'| = |F_2| - 2$ and $|X'| = |X|$, implying that $\xiD{G';\cP',X'} \ge 4 - 1 = 3$. Every $(\cP',X')$-cover in $G'$ is a $(\cP,X)$-cover in $G$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'}$ and therefore $\tranD{G';\cP',X'} \le 0$. Hence, $\xiD{G';\cP',X'} \ge 3 > 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}. Hence if $e_1, e_2 \in F_2$ are distinct edges that intersect $X$, then $e_1 \cap X \ne e_2 \cap X$. If $X = V$, then $10\tran{G;\cP,X} = 10n(G) < \xi(G;\cP,X)$, a contradiction. Hence, $X \ne V$. Let $G' = G - X$ (and so, the vertices in $X$ and the edges incident with $X$ are deleted). Let $\cP' = (E_2',F_2')$, where $E_2' = E_2 \cap E(G')$ and $F_2' = F_2 \cap E(G')$. Let $X' = \emptyset$. Since distinct edges in $F_2$ have distinct intersections with $X$, every $\tran{G';\cP',X'}$-cover can be extended to a $\tran{G;\cP,X}$-cover by adding to it the set $X$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'} + |X|$, and so $\tranD{G';\cP',X'} \le |X|$. We note that $n(G') = n(G) - |X|$, and so $\xiD{G';\cP',X'} > 6|X| + 4|X| = 10|X| \ge 10\tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}.\end{proof} \3 \noindent \ClaimX{B}{Every degree-$3$ vertex is incident with three $E_2$-edges or three $F_2$-edges.} \\ \begin{proof} Suppose that some vertex $v$ of degree~$3$ is not incident with three $E_2$-edges or three $F_2$-edges. Then either $v$ is incident with one $E_2$-edge and two $F_2$-edges or with one $F_2$-edge and two $E_2$-edges. % Suppose that $v$ is incident with exactly two $F_2$-edges, say $e_1 = \{v,v_1\}$ and $e_2 = \{v,v_2\}$, and with one $E_2$-edge, say $e_3$. Let $G'$ be obtained from $G - \{e_1,e_2,e_3\}$ by deleting the isolated vertex $v$ and adding the edge $e' = \{v_1,v_2\}$ if this edge does not already exist. Let $\cP' = (E_2',F_2')$, where $E_2' = (E_2 \setminus \{e_3\}) \cup \{e'\}$ and $F_2' = F_2 \setminus \{e_1,e_2\}$. Let $X' = X$. Recall that by Claim~A, $X = \emptyset$. Then, $n(G') = n(G) - 1$, $|E_2'| \le |E_2|$ and $|F_2'| = |F_2| - 2$, implying that $\xiD{G';\cP',X'} \ge 6 + 4 = 10$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the vertex $v$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'} + 1$ and therefore $\tranD{G';\cP',X'} \le 1$. Hence, $\xiD{G';\cP',X'} \ge 10 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}. Hence, $v$ is incident with exactly two $E_2$-edges, say $f_1$ and $f_2$, and with one $F_2$-edge, say $f_3$. Let $G'$ be obtained from $G - \{f_1,f_2,f_3\}$ by deleting the resulting isolated vertex $v$. Let $\cP' = (E_2',F_2')$, where $E_2' = E_2 \setminus \{f_1,f_2\}$ and $F_2' = F_2 \setminus \{f_3\}$. Let $X' = X$. Then, $n(G') = n(G) - 1$, $|E_2'| = |E_2| - 2$ and $|F_2'| = |F_2| - 1$, implying that $\xiD{G';\cP',X'} \ge 6 + 2 + 2 = 10$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the vertex~$v$, implying that $\tranD{G';\cP',X'} \le 1$. Hence, $\xiD{G';\cP',X'} \ge 10 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}.\end{proof} \3 \noindent \ClaimX{C}{$\delta(G) \ge 2$.} \\ \begin{proof} Suppose that $\delta(G) < 2$. As observed earlier, $n(G) \ge 3$. The connectivity of $G$ implies that $\delta(G) = 1$. Let $u$ be a vertex of degree~$1$ in $G$ and let $e_1 = \{u,v\}$ be the edge incident with~$u$. Suppose that $e_1 \in E_2$. Let $G' = G - u$ and let $\cP' = (E_2',F_2')$, where $E_2' = E_2 \setminus \{e_1\}$ and $F_2'=F_2$. Let $X' = X \cup \{v\} = \{v\}$ (recall that by Claim C, $X=\emptyset$). Then, $\xiD{G';\cP',X'} \ge 6 + 1 - 4 =3$. Every $(\cP',X')$-cover in $G'$ is a $(\cP,X)$-cover in $G$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'}$ and therefore $\tranD{G';\cP',X'} \le 0$. Hence, $\xiD{G';\cP',X'} = 3 > \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}. Therefore, $e_1 \in F_2$. Now let $G^* = G - \{u,v\}$ and let $\cP^* = (E_2^*,F_2^*)$, where $E_2^* = E_2 \cap E(G^*)$ and $F_2^*=F_2 \cap E(G^*)$. Let $X^* = \{ w \mid \{v,w\} \in F_2 \setminus \{e_1\} \}$. In other words, $X^*$ contains all vertices different from $u$ that are joined to $v$ by an edge in $F_2$. Then, $\xiD{G^*;\cP^*,X^*} \ge 12 + 2 + 2|X^*| - 4|X^*| = 14 - 2|X^*| \ge 10$, since $|X^*| \le d(v)-1 \le 2$. Every $(\cP^*,X^*)$-cover in $G^*$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the vertex $v$, implying that $\tran{G;\cP,X} \le \tran{G^*;\cP^*,X^*} + 1$ and therefore $\tranD{G^*;\cP^*,X^*} \le 1$. Hence, $\xiD{G^*;\cP^*,X^*} \ge 10 \ge 10 \tranD{G^*;\cP^*,X^*}$, contradicting Lemma~\ref{key_lem}. This completes the proof of Claim~C.\end{proof} \3 %\newpage \noindent \ClaimX{D}{Every vertex is incident with at least one $F_2$-edge.} \\ \begin{proof} Suppose that some vertex $v$ is incident with no $F_2$-edge. \noindent \ClaimX{D.1}{$d_G(v) = 3$.} \\ \begin{proof} Suppose that $d_G(v) = 2$. Let $e_1 = \{v,v_1\}$ and $e_2 = \{v,v_2\}$ be the two edges incident with $v$. Let $G' = G - v$. Let $\cP' = (E_2',F_2')$, where $E_2' = E_2 \setminus \{e_1,e_2\}$ and $F_2' = F_2$. Let $X' = X \cup \{v_1,v_2\}$. Then, $n(G') = n(G) - 1$, $|E_2'| = |E_2| - 2$, $|F_2'| = |F_2|$ and $|X'| = |X| + 2$, implying that $\xiD{G';\cP',X'} \ge 6 + 2 - 8 = 0$. Every $(\cP',X')$-cover in $G'$ is a $(\cP,X)$-cover in $G$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'}$ and therefore $\tranD{G';\cP',X'} \le 0$. Hence, $\xiD{G';\cP',X'} \ge 0 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}.\end{proof} \medskip By Claim~D.1, $d_G(v) = 3$. Let $e_1 = \{v,v_1\}$, $e_2 = \{v,v_2\}$ and $e_3 = \{v,v_3\}$ be the three edges incident with $v$. Let $G' = G - \{v,v_1,v_2,v_3\}$. Let $\cP' = (E_2',F_2')$, where $E_2'$ is obtained from $E_2$ by deleting all $E_2$-edges incident with $v_1$, $v_2$ or $v_3$ and where $F_2'$ is obtained from $F_2$ by deleting all $F_2$-edges incident with with $v_1$, $v_2$ or $v_3$. Let $X' = X$. Then, $n(G') = n(G) - 4$. If a neighbor of $v$ is incident with no $F_2$-edge, then as shown in the proof of Claim~D.1 such a vertex is incident with three $E_2$-edges. If a neighbor of $v$ is incident with an $F_2$-edge, then by Claim~B, such a vertex is incident with exactly one $F_2$-edge (and one $E_2$-edge, namely the edge joining it to $v$). In particular, if no neighbor of $v$ is incident with an $F_2$-edge, then we note that at least six $E_2$-edges are deleted when constructing $G'$, implying that $\xiD{G';\cP',X'} \ge 24 + 6 = 30$. If only one $F_2$-edge is deleted when constructing $G'$, we note that at least five $E_2$-edges were deleted, implying that $\xiD{G';\cP',X'} \ge 24 + 2 + 5 = 31$. If at least two $F_2$-edges are deleted when constructing $G'$, we note that at least three $E_2$-edges were deleted, implying that $\xiD{G';\cP',X'} \ge 24 + 4 + 3 = 31$. In all three cases, we have $\xiD{G';\cP',X'} \ge 30$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the three vertices $v_1$, $v_2$ and $v_3$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'} + 3$ and therefore $\tranD{G';\cP',X'} \le 3$. Hence, $\xiD{G';\cP',X'} \ge 30 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}. This completes the proof of Claim~D.\end{proof} \3 \noindent \ClaimX{E}{For all $F_2$-edges $\{u,v\}$, we have $d(u) = 2$ or $d(v) = 2$ (or both)} \\ \begin{proof} Suppose that there is an $F_2$-edge $e = \{u,v\}$ with $d(u)=d(v)=3$. Let $e_1=\{u,u_1\}$, $e_2=\{u,u_2\}$, $f_1=\{v,v_1\}$ and $f_2=\{v,v_2\}$ be the edges in $G$ adjacent with $e$. By Claim~B, all these edges are $F_2$-edges. Let $G'$ be obtained from $G - \{u,v\}$ by adding the two edges $\{u_1,u_2\}$ and $\{v_1,v_2\}$, and let $\cP' = (E_2',F_2')$, where $E_2' = E_2 \cup \{ \{u_1,u_2\}, \{v_1,v_2\} \}$ and $F_2' = F_2 \setminus \{e,e_1,e_2,f_1,f_2\}$. Let $X' = X = \emptyset$. Then, $n(G') = n(G) - 2$, $|E_2'| \le |E_2| + 2$, $|F_2'| = |F_2| - 5$ and $|X'| = |X| = 0$, implying that $\xiD{G';\cP',X'} \ge 12 + 10 - 2 = 20$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the two vertices $u$ and $v$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'} + 2$ and therefore $\tranD{G';\cP',X'} \le 2$. Hence, $\xiD{G';\cP',X'} \ge 20 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}.\end{proof} \3 \noindent \ClaimX{F}{Every edge is an $F_2$-edge.} \\ \begin{proof} Suppose that there is an $E_2$-edge $e = \{v_1,v_2\}$. By Claims~D, E, and F, every vertex that is incident with an $E_2$-edge has degree exactly~$2$ and is incident with an $F_2$-edge. In particular, $d(v_1) = d(v_2) = 2$. Let $e_1$ and $e_2$ be the $F_2$-edges incident with $v_1$ and $v_2$, respectively. \noindent \ClaimX{F.1}{The vertices $v_1$ and $v_2$ do not have a common neighbor.} \\ \begin{proof} Suppose that $v_1$ and $v_2$ have a common neighbor, $v_3$ say. Hence, $e_1 = \{v_1,v_3\}$ and $e_2 = \{v_2,v_3\}$. Since $\Delta(G) = 3$ and $G$ is connected, we have that $d(v_3) = 3$. Let $e_3 = v_3v_4$ be the third edge incident with $v_3$ that is distinct from $e_1$ and $e_2$. By Claim~B, $e_3$ is an $F_2$-edge. We now consider the graph $G' = G - \{v_1,v_2,v_3\}$. Let $\cP' = (E_2',F_2')$, where $E_2' = E_2 \setminus \{e\}$ and $F_2' = F_2 \setminus \{e_1,e_2,e_3\}$. Let $X' = X \cup \{v_4\} = \{v_4\}$. Then, $n(G') = n(G) - 3$, $|E_2'| = |E_2| - 1$, $|F_2'| = |F_2| - 3$ and $|X'| = |X| + 1$, implying that $\xiD{G';\cP',X'} \ge 18 + 6 + 1 - 4 = 21$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the vertices~$v_1$ and $v_3$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'} + 2$ and therefore $\tranD{G';\cP',X'} \le 2$. Hence, $\xiD{G';\cP',X'} \ge 21 > 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}.\end{proof} \medskip Let $e_1 = \{v_1,w_1\}$ and $e_2 = \{v_2,w_2\}$. By Claim~F.1, $w_1 \ne w_2$. \medskip \noindent \ClaimX{F.2}{$d(w_1) = d(w_2) = 3$.} \\ \begin{proof} Suppose that $d(w_1) = 2$. Let $e_3 = \{w_1,w_3\}$ be the edge incident with $w_1$ that is distinct from $e_1$. Suppose that $e_3 \in E_2$. Let $G'$ be obtained from $G$ by deleting the four edges $e,e_1,e_2,e_3$ and the resulting isolated vertices $v_1$, $v_2$ and $w_1$. Let $\cP' = (E_2',F_2')$, where $E_2' = E_2 \setminus \{e,e_3\}$ and $F_2' = F_2 \setminus \{e_1,e_2\}$. Let $X' = X \cup \{w_2\} = \{w_2\}$. Then, $n(G') = n(G) - 3$, $|E_2'| = |E_2| - 2$, $|F_2'| = |F_2| - 2$ and $|X'| = |X| + 1$, implying that $\xiD{G';\cP',X'} \ge 18 + 4 + 2 - 4 = 20$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the vertices~$v_2$ and $w_1$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'} + 2$ and therefore $\tranD{G';\cP',X'} \le 2$. Hence, $\xiD{G';\cP',X'} \ge 20 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}. Therefore, $e_3 \in F_2$. We now let $G' = G - \{v_1,v_2,w_1\}$. Let $\cP' = (E_2',F_2')$, where $E_2' = E_2 \setminus \{e\}$ and $F_2' = F_2 \setminus \{e_1,e_2,e_3\}$. Let $X' = X \cup \{w_3\} = \{w_3\}$. Then, $n(G') = n(G) - 3$, $|E_2'| = |E_2| - 1$, $|F_2'| = |F_2| - 3$ and $|X'| = |X| + 1$, implying that $\xiD{G';\cP',X'} \ge 18 + 6 + 1 - 4 = 21$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the vertices $v_2$ and $w_1$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'} + 2$ and therefore $\tranD{G';\cP',X'} \le 2$. Hence, $\xiD{G';\cP',X'} > 20 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}. Therefore, $d(w_1) = 3$. Analogously, $d(w_2) = 3$.\end{proof} \medskip By Claim~F.2, $d(w_1) = d(w_2) = 3$. By Claim~B, all three edges incident with $w_1$ (respectively, $w_2$) are $F_2$-edges. Let $N(w_1) = \{v_1,x_1,y_1\}$ and let $f_1 = \{w_1,x_1\}$ and $g_1 = \{w_1,y_1\}$ be the two edges incident with $w_1$ that are distinct from~$e_1$ (note that $w_2 \in \{x_1,y_1\}$ is possible). Renaming $x_1$ and $y_1$, if necessary, we may assume that $x_1 \ne w_2$. Let $G^* = G - \{v_1,v_2,w_1,x_1,y_1\}$. Let $\cP^* = (E_2^*,F_2^*)$, where $E_2^* = E_2 \cap E(G^*)$ and $F_2^* = F_2 \cap E(G^*)$. Let $X^* = X = \emptyset$. Then, $n(G^*) = n(G) - 5$ and $|X^*| = |X|$. Since $x_1 \ne w_2$, we note that apart from the edges $e,e_1,e_2,f_1,g_1$ we also delete at least one further edge which is incident to $x_1$. On the one hand, if such an edge is an $E_2$-edge, then $|E_2^*| \le |E_2| - 2$ and $|F_2^*| \le |F_2| - 4$, implying that $\xiD{G^*;\cP^*,X^*} \ge 30 + 8 + 2 = 40$. On the other hand, if such an edge is an $F_2$-edge, then $|E_2^*| \le |E_2| - 1$ and $|F_2^*| \le |F_2| - 5$, implying that $\xiD{G^*;\cP^*,X^*} \ge 30 + 10 + 1 = 41$. In both cases, $\xiD{G^*;\cP^*,X^*} \ge 40$. By Claim~C and Claim~E, we note that $d(x_1)=d(y_1)=2$. Hence every $(\cP^*,X^*)$-cover in $G^*$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the vertices $v_2$, $w_1$, $x_1$ and $y_1$, and so $\tran{G;\cP,X} \le \tran{G';\cP',X'} + 4$ and therefore $\tranD{G';\cP',X'} \le 4$. Hence, $\xiD{G';\cP',X'} \ge 40 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}.\end{proof} \3 \noindent \ClaimX{G}{$G$ is triangle-free.} \\ \begin{proof} Suppose that there is a triangle $T \colon v_1v_2v_3v_1$ in $G$. By Claim~C and Claim~E, at least two of the vertices in $T$ have degree~$2$ in $G$. Renaming vertices, if necessary, we may assume that $d(v_1) = d(v_2) = 2$. Since $\Delta(G) = 3$ and $G$ is connected, we have that $d(v_3) = 3$. Let $w$ be the neighbor of $v_3$ not in $T$. Let $G' = G - \{v_1,v_2,v_3\}$ and let $\cP' = (E_2',F_2')$, where $E_2' = E_2 = \emptyset$ and where $F_2'$ is obtained from $F_2$ by deleting the four edges incident with vertices in $\{v_1,v_2,v_3\}$. Let $X' = X \cup \{w\}$. Then, $\xiD{G';\cP',X'} = 18 + 8 - 4 = 22$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the set $\{v_2,v_3\}$, implying that $\tranD{G';\cP',X'} \le 2$ and $\xiD{G';\cP',X'} > 20 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}.\end{proof} \3 \noindent \ClaimX{H}{$G$ contains no $5$-cycle.} \\ \begin{proof} Suppose that there is a $5$-cycle $C \colon v_1v_2v_3v_4v_5v_1$ in $G$. By Claim~G, $G$ is triangle-free, and so $C$ is an induced cycle in $G$. Since $\Delta(G) = 3$ and $G$ is connected, we may assume, renaming vertices of $C$ if necessary, that $d(v_1) = 3$. Let $v_6$ be the neighbor of $v_1$ not on $C$. By Claim~C and Claim~E, $d(v_2) = d(v_5) = d(v_6) = 2$. By Claim~E, at least one of $v_3$ and $v_4$ has degree~$2$ in $G$. Renaming vertices if necessary, we may assume that $d(v_3) = 2$. Let $G' = G - V(C)$ and let $\cP' = (E_2',F_2')$, where $E_2' = E_2 = \emptyset$ and where $F_2'$ is obtained from $F_2$ by deleting all edges incident with vertices in $V(C)$. On the one hand, if $d(v_4) = 2$, let $X' = X = \emptyset$. On the other hand, if $d(v_4) = 3$, let $w$ be the neighbor of $v_4$ not in $C$ and let $X' = X \cup \{w\}$. Therefore if $d(v_4) = 2$, we have that $\xiD{G';\cP',X'} = 30 + 12 = 42$, while if $d(v_4) = 3$, we have that $\xiD{G';\cP',X'} = 30 + 14 - 4 = 40$. In both cases, $\xiD{G';\cP',X'} \ge 40$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the set $\{v_1,v_2,v_4,v_5\}$, implying that $\tranD{G';\cP',X'} \le 4$ and $\xiD{G';\cP',X'} \ge 40 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}.\end{proof} \3 \noindent \ClaimX{I}{$G$ contains no $4$-cycle.} \\ \begin{proof} Suppose that there is a $4$-cycle $C \colon w_1w_2w_3w_4w_1$ in $G$. By Claim~G, $G$ is triangle-free, and so $C$ is an induced cycle in $G$. Since $\Delta(G) = 3$ and $G$ is connected we may assume, renaming vertices of $C$ if necessary, that $d(w_1)=3$. Let $w_5$ be the neighbor of $w_1$ not in $C$. By Claim~C and Claim~E, $d(w_2) = d(w_4) = d(w_5) = 2$. Let $w_6$ be the neighbor of $w_5$ different from $w_1$. If $w_3 = w_6$, then $G = K_{2,3}$ and $10\tran{G;\cP,X} = 40 < 30 + 12 = \xi(G;\cP,X)$, a contradiction. Hence, $w_3 \ne w_6$. Let $W = \{w_1,w_2,\ldots,w_6\}$. By Claim~H, $w_3$ is not adjacent to $w_6$, and so the vertex $w_5$ is the only neighbor of $w_6$ that belongs to the set $W$. On the one hand, if $d(w_6) = 2$, let $G' = G - W$. On the other hand if $d(w_6) = 3$, then let $G'$ be obtained from $G - W$ by adding an $E_2$-edge $e'$ joining the two neighbors of $w_6$ not in $W$. Let $\cP' = (E_2',F_2')$, where $E_2' = \emptyset$ if $d(w_6) = 2$ and $E_2' = \{e'\}$ if $d(w_6) = 3$, and where $F_2'$ is obtained from $F_2$ by deleting all edges incident with vertices in $W$. Let $X' = X = \emptyset$. Then, $n(G') = n(G) - 6$ and $|X'| = |X| = 0$. If $d(w_6) = 2$, then $|E_2'| = |E_2| = 0$ and $|F_2'| = |F_2| - 5 - d(w_3) \le |F_2| - 7$, implying that $\xiD{G';\cP',X'} \ge 36 + 14 = 50$. If $d(w_6) = 3$, then $|E_2'| = |E_2| + 1 = 1$ and $|F_2'| = |F_2| - 6 - d(w_3) \le |F_2| - 8$, implying that $\xiD{G';\cP',X'} \ge 36 + 16 - 1 = 51$. In both cases, $\xiD{G';\cP',X'} \ge 50$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the set $W \setminus \{w_1\}$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'} + 5$ and therefore $\tranD{G';\cP',X'} \le 5$. Hence, $\xiD{G';\cP',X'} \ge 50 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}.\end{proof} \medskip We now return to the proof of Theorem~\ref{main2}. Let $u$ be any vertex of degree~$3$ in $G$ and let $N(u)=\{u_1,u_2,u_3\}$. Further let $e_1=\{u,u_1\}$, $e_2=\{u,u_2\}$ and $e_3=\{u,u_3\}$ be the three edges incident with $u$ in $G$. By Claim~C and Claim~E, we note that $d(u_1)=d(u_2)=d(u_3)=2$. For $i \in \{1,2,3\}$, let $f_i = \{u_i,v_i\}$ be the edge incident with $u_i$ that is different from~$e_i$. By Claim~G, the set $N(u)$ is an independent set. By Claim~I, no two vertices in $N(u)$ have a common neighbor other than the vertex~$u$; that is, $v_i \ne v_j$ for $1 \le i < j \le 3$. By Claim~H, the set $\{v_1,v_2,v_3\}$ is an independent set. Let $W$ be the set of all vertices within distance~$2$ from $u$, and so $W = \{u,u_1,u_2,u_3,v_1,v_2,v_3\}$. As observed earlier, for $i \in \{1,2,3\}$, the vertex $u_i$ is the only neighbor of $v_i$ that belongs to the set $W$. Let $G'$ be obtained from $G - W$ as follows: For each vertex $v_i$, $1 \le i \le 3$, of degree~$3$ in $G$, add an $E_2$-edge containing the two neighbors of $v_i$ not in $W$. Hence if $d(v_i) = 2$, then we delete two $F_2$-edges incident with $v_i$ when constructing $G'$, while if $d(v_i) = 3$, we delete three $F_2$-edges incident with $v_i$ when construction $G'$ but add an $E_2$-edge. Let $\cP' = (E_2',F_2')$, where $E_2'$ consists of the added $E_2$-edges, if any, and where $F_2'$ is obtained from $F_2$ by deleting all edges incident with vertices in $W$. Hence if $\ell$ denotes the number of vertices in $\{v_1,v_2,v_3\}$ of degree~$3$ in $G$, then $|E_2'| = |E_2| + \ell = \ell$ and $|F_2'| = |F_2| - 9 - \ell$. Let $X' = X = \emptyset$. Then, $n(G') = n(G) - 7$ and $|X'| = |X| = 0$. Hence, $\xiD{G';\cP',X'} \ge 42 + 18 + 2\ell - \ell = 60 + \ell \ge 60$. Every $(\cP',X')$-cover in $G'$ can be extended to a $(\cP,X)$-cover in $G$ by adding to it the set $W \setminus \{u\}$, implying that $\tran{G;\cP,X} \le \tran{G';\cP',X'} + 6$ and therefore $\tranD{G';\cP',X'} \le 6$. Hence, $\xiD{G';\cP',X'} \ge 60 \ge 10 \tranD{G';\cP',X'}$, contradicting Lemma~\ref{key_lem}. This completes the proof of Theorem~\ref{main2}.\end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{10} \bibitem{TestCover} K. M. J. De Bontridder, B. V. Halld\'{o}rsson, M. M. Halld\'{o}rsson, C. A. J. Hurkens, J. K. Lenstra, R. Ravi, and L. Stougie. \newblock Approximation algorithms for the test cover problem. \newblock \textit{Mathematical Programming Series B} \textbf{98} (2003), 477--491. \bibitem{hhs} T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, \newblock \emph{Fundamentals of Domination in Graphs}, Marcel Dekker, Inc. New York, 1998. \bibitem{HeYe12} M. A. Henning and A. Yeo, \newblock Identifying open codes in cubic graphs, manuscript. \bibitem{HoSi60} A. J. Hoffman and R. R. Singleton, \newblock On Moore graphs with diameter 2 and 3. \newblock \textit{IBM J. of Research and Development} \textbf{5} (1960) 497–-504. \bibitem{HoKaLi01} I. Honkala, M. G. Karpovsky, S. Litsyn. \newblock On the identification of vertices and edges using cycles. \newblock \textit{Lecture Notes in Computer Science} \textbf{2227} (2001), 308--314. \bibitem{HoKaLi03} I. Honkala, M. G. Karpovsky, S. Litsyn. \newblock Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori. \newblock \textit{Discrete Applied Math.} \textbf{129} (2003), 409--419. \bibitem{HoLaRa02} I. Honkala, T. Laihonen, and S. Ranto, \newblock On strongly identifying codes. \newblock \textit{Discrete Math.} \textbf{254} (2002), 191–-205. \bibitem{Lobstein} http://www.infres.enst.fr/~lobstein/debutBIBidetlocdom.pdf. \bibitem{Moncel} J. Moncel, \newblock Codes Identifants dans les graphes. \newblock PhD thesis, Universit\'{e} Joseph Fourier Grenoble I, France, 2005 - available online at http://tel.archives-ouvertes.fr/tel-00010293/en/. \bibitem{MoSh85} M. M. E. Moret and H. D. Shapiro, \newblock On minimizing a set of tests. \newblock \textit{SIAM J. Scientific and Statistical Computing} \textbf{6} (1985), 983--1003. \bibitem{SeSl10} S. J. Seo and P. J. Slater, \newblock Open neighborhood locating-dominating sets. \newblock \textit{Australasian J. Combin.} \textbf{46} (2010), 109–-120. \bibitem{SeSl11} S. J. Seo and P. J. Slater, \newblock Open neighborhood locating-dominating in trees. \newblock \textit{Discrete Applied Math.} \textbf{159} (2011), 484–-489. \bibitem{Si68} R. R. Singleton, \newblock There is no irregular Moore graph. \newblock \textit{Amer. Math. Monthly} \textbf{75} (1968) 42-–43. \end{thebibliography} \end{document}