11institutetext: Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon
1, LIP UMR5668, France
11email: {pierre.berge, anthony.busson, carl.feghali, remi.watrigant}@ens-
lyon.fr

#  $1$-Extendability of independent sets ††thanks: Partially supported by the
LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program
“Investissements d’Avenir” (ANR-11-IDEX-0007), and the research grant ANR
DIGRAPHS ANR-19-CE48-0013-01, operated by the French National Research Agency
(ANR).

Pierre Bergé  0000-0002-6170-9473 Anthony Busson  0000-0002-9445-637X Carl
Feghali  0000-0001-6727-7213 Rémi Watrigant  0000-0002-6243-5910

###### Abstract

In the 70s, Berge introduced 1-extendable graphs (also called B-graphs), which
are graphs where every vertex belongs to a maximum independent set. Motivated
by an application in the design of wireless networks, we study the
computational complexity of $1$-extendability, the problem of deciding whether
a graph is 1-extendable. We show that, in general, $1$-extendability cannot be
solved in $2^{o(n)}$ time assuming the Exponential Time Hypothesis, where $n$
is the number of vertices of the input graph, and that it remains NP-hard in
subcubic planar graphs and in unit disk graphs (which is a natural model for
wireless networks). Although $1$-extendability seems to be very close to the
problem of finding an independent set of maximum size (a.k.a. Maximum
Independent Set), we show that, interestingly, there exist 1-extendable graphs
for which Maximum Independent Set is NP-hard. Finally, we investigate a
parameterized version of $1$-extendability.

###### Keywords:

1-extendable graphs B-graphs independent set

##  1 Introduction and Motivation

###  1.1 Definitions and Related Work

Understanding the structure of independent sets is among the most studied
subjects in algorithmics and graph theory, and finding graph classes where a
maximum independent set (MIS for short) can be found efficiently is an
important theoretical and practical problem. In 1970, Plummer [21] defined the
class of well-covered graphs, which are graphs where every independent set
which is maximal for inclusion is also an MIS. In other words, they are
exactly the graphs for which the greedy algorithm always returns an optimal
solution. Well-covered graphs were studied mostly from an algorithmic
perspective: their recognition was proven coNP-hard [8, 27] in general graphs,
but polynomial-time solvable for claw-free graphs [28], and perfect graphs of
bounded clique number [12].

A related notion, introduced by Berge [5], is the definition of B-graphs,
which are those graphs where every vertex belongs to an MIS. B-graphs were
mostly introduced in order to study well-covered graphs [25, 26]. Later, the
notion of B-graphs was generalized to that of $k$-extendable graphs [12]: a
graph is $k$-extendable, for a positive integer $k$, if every independent set
of size (exactly) $k$ is contained in an MIS. Thus, B-graphs are exactly the
1-extendable graphs and a graph is well-covered if and only if (iff) it is
$k$-extendable for every $k\in\\{1,2,\dots,\alpha(G)\\}$, where $\alpha(G)$
denotes the size of an MIS of $G$. Dean and Zito [12] obtained a number of
results on 1-extendable graphs; for instance, they proved that a bipartite
graph is 1-extendable iff it admits a perfect matching and, hence, bipartite
1-extendable graphs can be recognized in polynomial time. Recently, certain
structural properties of $k$-extendable graphs were stated [2, 3].

We should note that the notion of $k$-extendability was also studied in the
context of maximum matchings [22, 23]. Recently, it was shown that the
recognition of (matching) $k$-extendable graphs is co-NP-complete [16].

In the remainder, B-graphs will be called 1-extendable graphs, as it is the
terminology used by the most recent papers on the topic. In this article, our
objective is to determine the computational complexity of the recognition of
1-extendable graphs. This question is not only motivated by the state of the
art described above but also by an application on Wi-Fi networks.

###  1.2 CSMA/CA network and $1$-extendability

Indeed, 1-extendable graphs play an important role in the performance of CSMA/
CA (Carrier Sense Multiple Access / Collision Avoidance) networks. CSMA/CA is
the mechanism used by the nodes to access the radio channel in many wireless
network technologies. It aims to prevent collisions, which happens when
several nodes transmit at the same time thereby producing harmful interference
that may cause transmissions losses. Basically, it is a listen-before-talk
mechanism where a potential transmitter listens to the radio channel for a
certain period of time, and transmits if the channel was sensed as idle during
this period.

Graphs stand as a natural model for CSMA/CA wireless networks. Two vertices,
i.e. nodes of the CSMA/CA network, are adjacent if the two corresponding nodes
are able to detect the transmissions from each others. Transmissions from two
vertices can occur in parallel iff they are not adjacent. A set of
instantaneous transmitters is thus an independent set of the graph.

This graph, also named conflict graph in the literature, is used to evaluate
the network performance. The performance parameter that is often computed is
the throughput that offers to each vertex, i.e. the number of bits per second
that a vertex is able to send. The throughput of a vertex is strongly
correlated to the proportion of time this vertex is transmitting. We denote by
$p_{v}$ this quantity for the vertex $v\in V(G)$. If we neglect the network
protocol headers and transmission errors, the throughput of vertex $v$ may be
considered as proportional to $p_{v}$. The first formal work that
characterized $p_{v}$ has been developed in [18]. It was shown that, under
saturation condition, $p_{v}$ is given by:

$p_{v}=\frac{\sum_{S\in\mathcal{S}(G):v\in
S}{\theta^{|S|}}}{\sum_{S\in\mathcal{S}(G)}\theta^{|S|}},$ (1)

where $\theta$ is the ratio between transmission and listen phase durations
and $\mathcal{S}(G)$ is the collection of independent sets of $G$. When
$\theta$ tends to infinity, $p_{v}$ tends to the number of MISs of $G$
containing $v$ ($\\#_{v}\alpha(G)$) divided by the total number $\\#\alpha(G)$
of MISs of $G$:

$\lim_{\theta\rightarrow+\infty}p_{v}=\frac{\\#_{v}\alpha(G)}{\\#\alpha(G)}$
(2)

(a) 4 vertices

(b) 5 vertices

Figure 1:  Wi-Fi network simulated with ns-3 for paths on 4 and 5 vertices.
The simulation parameters are: Wi-Fi 6 (IEEE 802.11ax) with a fixed MCS (He
MCS=5), packet size=1024 bytes, aggregation is enable with a maximum of $16$
aggregated frame. The traffic is saturated.

In practice, the value of $\theta$ tends to be large to ensure an efficient
channel use. In Wi-Fi networks for instance, typical values of $\theta$ then
ranges from $20$ to $100$ depending on the transmission parameters. With such
values, a node/vertex that does not belong to any MIS will experience a very
low throughput. In Fig. 1, we show the throughput obtained in a Wi-Fi network
for paths on $4$ and $5$ vertices using the network simulator ns-3 [20]. The
5-vertex path is not 1-extendable, and we can observe that the two vertices
that do not belong to any MIS are in starvation: they admit a very low
throughput. In the 4-vertex path, there is no starvation as all vertices
belong to at least one MIS.

The fact, for each vertex, of belonging or not to an MIS is thus of prior
importance to ensure a minimal fairness between the vertices and to avoid
starvation. CSMA/CA networks where the parameter $\theta$ is large must thus
be designed in such a way that the resulting conflict graph is 1-extendable.

###  1.3 Contribution

Most of the outcomes of this paper concern the complexity of
$1$-Extendability, the problem of deciding whether an input graph is
1-extendable. First, we focus on the relationship between maximum independent
set and $1$-Extendability. We observe that any polynomial-time algorithm for
maximum independent set on some hereditary family of graphs $\mathcal{C}$
provides us with a polynomial-time algorithm for $1$-Extendability on
$\mathcal{C}$. Based on this result, we could imagine that, perhaps, maximum
independent set and $1$-Extendability are equivalent problems in terms of
complexity. However, we show that Maximum Independent Set is NP-hard on a
certain subfamily of 1-extendable graphs (Theorem 2.1). This result highlights
a gap for the complexity of these two problems.

We provide a linear reduction which implies, under the Exponential Time
Hypothesis (ETH) that $1$-Extendability cannot be solved in time $2^{o(n)}$ on
an $n$-vertex input graph (Corollary 1).

Second, we establish the NP-hardness of $1$-Extendability on certain families
of graphs. We prove that the problem is NP-hard in planar subcubic graphs
(Theorem 4.1) and in unit disk graphs (Theorem 4.3), a natural model for
CSMA/CA networks.

Eventually, we focus on a parameterized version of $1$-Extendability, where we
ask whether every vertex belongs to an independent set of size at least some
parameter $k$. We show that this problem, param-$1$-Extendability, is
W[1]-hard (Theorem 5.1). Nevertheless, it admits a polynomial kernel if
restricted to planar graphs or $K_{r}$-free graphs for fixed $r>0$ (Corollary
2).

###  1.4 Organization of the paper

Section 2 is dedicated to the notation, definitions and some basic results; in
particular, we explore the relationship between the Maximum Independent Set
and $1$-Extendability problems. In Section 3, we study three graph transfor-
-mations and their impact on the $1$-extendability property. In Section 4, we
show that $1$-Extendability cannot be solved in time $2^{o(n)}$ on $n$-vertex
graphs unless the ETH is false. We also prove that $1$-Extendability remains
NP-hard in planar graphs of maximum degree $3$ and in unit disk graphs. Then,
Section 5 presents the parameterized version param-$1$-Extendability and the
results associated with it. We conclude and give several open questions in
Section 6.

##  2 Notation and Basic Results

###  2.1 Notation and definitions

For a positive integer $k$, we write $[k]=\\{1,\dots,k\\}$. In this paper, all
graphs are simple, unweighted and undirected. We denote by $V(G)$ the vertex
set of a graph $G$ and by $E(G)$ its edge set. Edges $(u,v)\in E(G)$ can
sometimes be denoted by $uv$ to improve readability. When the identity of the
graph considered is clear, we set $n=\left|V(G)\right|$ and
$m=\left|E(G)\right|$. For a vertex $v\in V(G)$, we denote by $N_{G}(v)$ its
set of neighbors (we will sometimes omit the subscript if $G$ is clear from
the context). Let $d(v)$ be the degree of $v$, i.e. $d(v)=\left|N(v)\right|$.
For a subset $R\subseteq V(G)$, let $G[R]$ be the subgraph of $G$ induced by
$R$. A family of graphs $\mathcal{C}$ is called hereditary if, for every graph
$G\in\mathcal{C}$, every induced subgraph of $G$ also belongs to
$\mathcal{C}$. An $\ell$-vertex path is denoted by $P_{\ell}$. A clique cover
of a graph $G$ is a partition of $V(G)$ into sets $C_{1}$, $\dots$, $C_{q}$
such that $G[C_{i}]$ is a clique for every $i\in[q]$. A set of pairwise non-
adjacent vertices in a graph is called an _independent set_. A maximum
independent set (MIS) is an independent set of maximum size. We denote by
$\alpha(G)$ the size of an MIS of $G$. The decision problem of finding an
independent set of size at least $k\geq 1$ in a graph $G$ is called Maximum
Independent Set. A graph $G$ is 1-extendable [5] if, for every $u\in V(G)$,
there is an MIS $S$ of $G$ such that $u\in S$.

The subject of this paper is to investigate the computational complexity of
the following decision problem.

$1$-Extendability Input: Graph $G$ Question: Does every vertex of $G$ belong
to an MIS of $G$?

An embedding of a graph $G$ is a representation of $G$ in the plane, where
vertices are points in the plane and edges are curves which connect their two
endpoints. A plane embedding of $G$ is an embedding of $G$ where no two edges
cross. A graph $G$ is planar if it admits a plane embedding. A parameterized
problem is a decision problem where an integer (called the parameter) is
associated to every instance. A Fixed-Parameter Tractable (FPT) algorithm is
an algorithm deciding whether an instance of a parameterized problem is
positive in time $f(k)n^{O(1)}$, where $f$ is a computable function, $n$ is
the size of the instance, and $k$ is the parameter of the instance. The
$W$-hierarchy allows to rule out the existence of FPT algorithms for some
problems: proving that a parameterized problem is $W[1]$-hard implies that it
is unlikely to admit an FPT algorithm. A kernel for a parameterized problem is
a polynomial-time algorithm which transforms an instance $x$ with parameter
$k$ into an instance $x^{\prime}$ with parameter $k^{\prime}$ such that (i)
$x$ is positive iff $x^{\prime}$ is positive (ii) $k^{\prime}\leqslant k$, and
(iii) $|x^{\prime}|\leqslant f(k)$, where $f$ is a computable function called
the size of the kernel. If $f$ is a polynomial, we say that it is a polynomial
kernel. For more details about parameterized algorithms, we refer the reader
to the textbook of Cygan et al. [10].

###  2.2 Links between $1$-Extendability and Maximum Independent Set

In this section, we investigate to what extent the problems $1$-Extendability
and Maximum Independent Set are close to each other. We show a “Turing
equivalence” of the two problems in general graphs. More precisely, we prove
that solving $1$-Extendability on an input graph $G$ can be done by solving
Maximum Independent Set on several induced subgraphs of $G$, while solving
Maximum Independent Set on an input graph $G$ can be done by solving
$1$-Extendability on several induced supergraphs of $G$.

#### Solving $1$-extendability using Maximum Independent Set.

The idea relies on the following lemma, whose straightforward proof is left to
the reader.

###### Lemma 1

Let $G$ be a graph, and $k$ be a non-negative integer. Then a vertex $v$ of
$G$ is contained in an independent set of $G$ of size $k$ iff $G[V(G)\setminus
N(v)]$ contains an independent set of size $k$.

This lemma allows $1$-extendability to inherit many positive results from
Maximum Independent Set. In particular, it implies that $1$-extendability is
polynomial-time solvable in any hereditary class where Maximum Independent Set
is polynomial-time solvable. This is for instance the case for perfect graphs,
$P_{6}$-free graphs [15], chordal graphs and claw-free graphs. Moreover, it is
Fixed-Parameter Tractable (FPT) when parameterized by the tree-width or even
the clique-width of the input graph. As we will see later in Section 5, this
lemma can also be used to transfer more positive FPT results for a
parameterized version of $1$-extendability.

#### Solving Maximum Independent Set using $1$-extendability.

The converse of Lemma 1 does not appear to be as straightforward, and we leave
as open whether solving $1$-extendability in a hereditary graph class
$\mathcal{C}$ in polynomial-time allows one to solve Maximum Independent Set
in $\mathcal{C}$ in polynomial-time. We can show, however, that this is true
if the class satisfies much more conditions than just being hereditary.

Let $G=(V,E)$ be a graph and $r\leq|V|$ be a non-negative integer. Let
$G^{+}_{r}$ be the graph obtained from $G$ by adding

  * •

an independent set $S$ of size $|V|-r$ to $G$,

  * •

for each vertex $v$ of $G$, a new vertex $\pi_{v}$ adjacent to $v$ only, and

  * •

all possible edges between $S$ and the set $T=\\{\pi_{v}:v\in V\\}$.

###### Proposition 1

$G^{+}_{r}$ is $1$-extendable iff $\alpha(G)=r$.

###### Proof

Let $n=|V(G)|$. First observe that $\alpha(G^{+}_{r})\geq n$, since $T$ is an
independent set. More precisely, by construction
$\alpha(G^{+}_{r})=\max\\{n,n-r+\alpha(G)\\}$.

Suppose that $G^{+}_{r}$ is $1$-extendable. By definition, every vertex of $S$
belongs to a MIS, and since all vertices of $S$ have the same neighborhood,
there must be a MIS $I$ containing all vertices of $S$. Now, since the
neighborhood of any vertex of $S$ is $T$, it follows that $G$ must contain an
independent set of size $\alpha(G^{+}_{r})-|I|\geq r$. But if $G$ contains an
independent set of size $r+1$, then $\alpha(G^{+}_{r})\geq n+1$. However, for
$v\in V(G)$, the non-neighborhood of $\pi_{v}$ is of size $n-1$, so $\pi_{v}$
cannot belong to an independent set of size $n+1$, contradicting the
$1$-extendability of $G^{+}_{r}$.

Conversely, if $\alpha(G)=r$, then necessarily $\alpha(G^{+}_{r})=n$. Let $J$
be an independent set of size $r$ in $G$. Observe that:

  * •

for each vertex $v\in V(G)$, the set $\\{v\\}\cup\\{\pi_{u}:u\in
V(G)\setminus\\{v\\}\\}$ is an independent set of size $n$;

  * •

$T$ is an independent set of size $n$;

  * •

$S\cup J$ is an independent set of size $n$.

In brief, each vertex of $G^{+}_{r}$ is contained in a MIS, which concludes
the proof.

The ETH [17] states that no algorithm can decide whether a 3SAT formula on $n$
variables is satisfiable in time $2^{o(n)}$. As 3-SAT, maximum independent set
is ETH-hard. Hence, based on Proposition 1, the same statement holds for
$1$-Extendability.

###### Corollary 1

Testing whether an $n$-vertex graph is $1$-extendable cannot be done in time
$2^{o(n)}$ unless the ETH is false.

This lower bound is matched by the trivial brute-force algorithm which
consists in enumerating all subsets of vertices, and testing whether all MISs
cover the entire vertex set.

Another question related to the previous one is whether being 1-extendable
helps finding a MIS. The next result suggests that this is unlikely, by
showing that $1$-extendability and Maximum Independent Set can sometimes
behave very differently from a computational point of view.

Let $k\geq 1$ be an integer. The $k$-Multicolored Independent Set problem,
asks, given a graph $G$ whose vertex set can be partitioned into $k$ parts
$C_{1},\dots,C_{k}$ each inducing a clique, whether $G$ contains an
independent set $I$ such that $|I\cap C_{i}|=1$ for each
$i\in\\{1,\dots,k\\}$.

###### Theorem 2.1

Maximum Independent Set remains $NP$-hard and $W[1]$-hard (parameterized by
$k$) in $1$-extendable graphs.

###### Proof

We reduce from $k$-Multicolored Independent Set which is well-known to be
$W[1]$-hard [10].

Let $G$ be an instance of $k$-Multicolored Independent Set and let
$C_{1},\dots,C_{k}$ be its $k$ cliques. We construct a 1-extendable graph $H$
from $G$ such that $G$ contains an independent set intersecting each $C_{i}$
iff $H$ contains an independent set of size $2k$.

To construct $H$, we take two copies $G_{1}$ and $G_{2}$ of $G$ and add two
new sets of vertices $P^{1}=\\{\pi_{1}^{1},\dots,\pi_{1}^{k}\\}$ and
$P^{2}=\\{\pi_{2}^{1},\dots,\pi_{2}^{k}\\}$. We then add all possible edges
between $P^{1}$ and $P^{2}$ and, for $i\in\\{1,2\\}$ and
$j\in\\{1,\dots,k\\}$, we make $\pi_{i}^{j}$ adjacent to each vertex of
$C_{i}^{j}$, where $C_{i}^{j}$ denotes the $j$th clique of $G_{i}$. This
completes the construction.

To see that $H$ is $1$-extendable, let $A_{1}$ and $A_{2}$ be maximum
independents in $G_{1}$ and $G_{2}$, respectively, and thus of size at most
$k$. Note by construction that $\alpha(H)=k+\alpha(G)$. Thus, by construction
again, we have that

  * •

for each $C_{i}^{j}$ and $x\in C_{i}^{j}$, the set
$\\{x\\}\cup\\{\pi_{i}^{j}:j\neq i\\}\cup A_{3-i}$ is independent and of size
$\alpha(H)$, and

  * •

for each $i\in\\{1,2\\}$, the set $P^{i}\cup A_{3-i}$ is independent and of
size $\alpha(H)$,

and hence $H$ is $1$-extendable as needed.

Now, suppose $G$ and thus $G_{1}$ has an independent set $S$ of size $k$. Then
$P^{2}\cup S$ is an independent set of size $2k$ in $H$, as claimed.

Conversely, suppose $H$ contains an independent set $T$ of size $2k$. Let
$F_{1}=H[V(G_{1})\cup P^{1}]$ and $F_{2}=H[V(G_{2})\cup P^{2}]$. Thus,
$H=F_{1}\cup F_{2}$. By construction, each $F_{i}$ has independence number at
most $k$, and thus $T$ intersects each $F_{i}$ on exactly $k$ vertices. Hence,
since there are all possible edges between $P^{1}$ and $P^{2}$, $T$ must
intersect either $G_{1}$ or $G_{2}$ on $k$ vertices, which in turn implies $G$
has an independent set of size $k$, as required. This completes the proof.

##  3 Generic transformations

In this subsection, we present three graph transformations. They are related
in some sense to the $1$-extendability property: the first one produces a
1-extendable graph, the second one preserves the $1$-extendability of the
input graph and the third one decreases the maximum degree of the input graph
and keeps it 1-extendable. These transformations (or similar ideas) will be
used later in some reductions.

Given any graph $G$ on $n$ vertices, the transformation $(T_{1})$ returns a
graph $G_{(1)}$ with $2n$ vertices which is not only 1-extendable but also
admits $G$ as an induced subgraph. The transformation $(T_{2})$ consists in
$2$-subdividing the edges of the graph. This operation preserves the
$1$-extendability: $G$ is 1-extendable iff $G_{(2)}$ is too. Eventually, the
transformation $(T_{3})$ produces a graph $G_{(3)}$ with maximum degree 3
which is 1-extendable if $G$ is 1-extendable (note that the converse is not
necessarily true). Transformations $(T_{2})$ and $(T_{3})$ are well-known, and
provide a useful tool to prove hardness on some restricted graph classes.
Furthermore, they preserve the planarity of the input graph.

Transformation $(T_{1})$. The graph $G_{(1)}$ is obtained from $G$ by adding a
pendant vertex $\pi_{u}$ for any $u\in V(G)$. The vertex $\pi_{u}$ has degree
one and is adjacent to $u$. The graph $G_{(1)}$ has thus $2n$ vertices and
$m+n$ edges. One of its MISs is the set of pendant vertices
$\left\\{\pi_{u}:u\in V(G)\right\\}$: we thus have
$\alpha(G_{(1)})=n=\left|V(G_{(1)})\right|/2$. This provides us with a trivial
linear-size vertex-addition scheme to obtain a 1-extendable graph.

###### Lemma 2

For any graph $G$, $G_{(1)}$ is $1$-extendable.

###### Proof

The graph $G_{(1)}$ admits a clique cover of size
$n=\left|V(G_{(1)})\right|/2$ consisting of all edges $u\pi_{u}$. As a
consequence, the size of an MIS of $G_{(1)}$ is at most $n$. Furthermore, the
set of pendant vertices form an independent set of size $n$. We prove now that
each vertex of $G_{(1)}$ belongs to an independent set of size $n$. We know it
is already the case for pendant vertices. Let $u$ be a non-pendant vertex of
$G_{(1)}$. We fix the following $n$-sized set:
$X_{u}=\left\\{u\right\\}\cup\left\\{\pi_{v}:v\neq u\right\\}$. All pendants
are pairwise non-adjacent. Moreover, the neighborhood of
$\left\\{\pi_{v}:v\neq u\right\\}$ contains exactly all non-pendant vertices,
except $u$. Hence $X_{u}$ is independent. In brief, every non-pendant vertex
$u$ also belongs to an MIS of $G_{(1)}$.

Transformation $(T_{2})$. The graph $G_{(2)}$ is obtained from $G$ by
subdividing each of its edges an even number of times, i.e. each edge becomes
an induced $P_{2\ell}$. In fact, $(T_{2})$ is a well-known graph
transformation which provides, for instance, the proof that Maximum
Independent set remains $NP$-hard on graphs forbidding a fixed graph $H$ as an
induced subgraph, for any $H$ different from a path or a subdivided claw [1,
24]. This transformation preserves in some sense all independent sets of the
input graph $G$.

######  Observation 3.1 ([1, 24])

Consider any MIS $X^{\prime}$ of $G_{(2)}$ and pick all its vertices
$X\subsetneq X^{\prime}$ which were already present in $G$, i.e. which do not
belong to the subdivided edges. Then $X$ is an MIS of the input graph $G$.
Additionally, the set $X^{\prime}\backslash X$ contains exactly half of the
vertices formed by the subdivisions.

One can see that $G_{(2)}$ is planar iff $G$ is planar (subdivisions do not
influence planar embeddings). Moreover, $(T_{2})$ also preserves the
$1$-extendability of the input graph.

###### Lemma 3

$G$ is 1-extendable iff $G_{(2)}$ is 1-extendable.

###### Proof

We begin with some notation. For every vertex $u\in V(G)$, we denote by
$\mathcal{R}[u]$ the set of vertices of $G_{(2)}$ which are (i) part of a
subdivided edge incident to $u$ and (ii) at even distance from $u$. We
consider $u\in\mathcal{R}[u]$ as it is at distance zero from itself. We claim
that $u$ belongs to an MIS of $G$ iff $\mathcal{R}[u]$ is a subset of an MIS
of $G_{(2)}$.

If $u$ is isolated, then it naturally belongs to all MISs of $G$. It stays
isolated in $G_{(2)}$ and $\mathcal{R}[u]=\left\\{u\right\\}$, so our claim
holds.

Assume that $\left|\mathcal{R}[u]\right|\geq 2$, i.e. $u$ has at least one
neighbor in $G$. On the one hand, let $X$ be an MIS of $G$ containing $u$. Let
$\mathcal{R}[X]=\bigcup_{v\in X}\mathcal{R}[v]$. As $X$ does not contain two
adjacent vertices of $G$, then no adjacency appears in $\mathcal{R}[X]$.
According to Observation 3.1, $\mathcal{R}[X]$ is an MIS of $G_{(2)}$ and
$\mathcal{R}[u]\subseteq\mathcal{R}[X]$. On the other hand, let $X^{\prime}$
be an MIS of $G_{(2)}$ such that $\mathcal{R}[u]\subseteq X^{\prime}$.
According to Observation 3.1, as $u\in\mathcal{R}[u]$, there is an MIS of $G$
containing $u$.

We can now prove that $(T_{2})$ preserves $1$-extendability. If $G$ is
1-extendable, then every set $\mathcal{R}[u]$, $u\in V(G)$, is a subset of
some MIS of $G_{(2)}$. Observe that $V(G_{(2)})=\bigcup_{u\in
V(G)}\mathcal{R}[u]$, hence $G_{(2)}$ is 1-extendable. Conversely, if
$G_{(2)}$ is 1-extendable, then every vertex of the original graph $G$ appears
within an MIS of $G_{(2)}$. By Observation 3.1, it belongs to at least one MIS
of $G$.

Transformation $(T_{3})$. The graph $G_{(3)}$ is obtained from $G$ by
replacing each of its vertices by a path in order to decrease the maximum
degree of the graph. It is a folklore transformation which also works for
other classical problems.

First, we replace each vertex $u\in V(G)$ by an induced odd path $P_{u}$ of
length $\ell=2\Delta-1$, where $\Delta$ is the maximum degree of $G$. We
denote by $u_{1},\ldots,u_{\ell}$ the vertices of $P_{u}$. The vertex set of
$G_{(3)}$ is $V(G_{(3)})=\left\\{u_{1},\ldots,u_{\ell}:u\in V(G)\right\\}$.
Second, let $Q_{u}\subseteq P_{u}$ be the set of vertices in $P_{u}$ with odd
index: $Q_{u}=\\{u_{2i+1}:0\leq i\leq\Delta-1\\}$. For any $1\leq i\leq d(u)$,
we assign arbitrarily to each vertex $u_{2i+1}$ of $Q_{u}$ a neighbor
$\rho(u_{2i+1})\in V(G)$ of $u$, so that $\rho$ is bijective. There are two
types of edges in $G_{(3)}$:

  * •

edges of induced paths $P_{u}$, $u\in V(G)$,

  * •

edges $u_{2i+1}v_{2j+1}$ when $\rho(u_{2i+1})=v$ and $\rho(v_{2j+1})=u$.

In this way, the maximum degree $G_{(3)}$ is at most $3$.

$u$

(a) An example of graph $G$

$u_{1}$$u_{3}$$u_{5}$$u_{7}$

(b) Graph $G_{(3)}$

Figure 2: Transformation $(T_{3})$ embedded in such a way that planarity
holds.

One may observe that $Q_{u}$ is an independent set of $P_{u}$ of maximum size
$\Delta$. This is the key property which allows us to show that this structure
maintains the $1$-extendability of the input graph.

###### Lemma 4

Let $n=|V(G)|$. We have $\alpha(G_{(3)})=n(\Delta-1)+\alpha(G)$. Moreover, if
$G$ is 1-extendable, then $G_{(3)}$ is 1-extendable.

###### Proof

Let $X$ be an an MIS of $G$. We construct the following set in $G_{(3)}$:

$X^{\prime}=(\bigcup_{u\in X}Q_{u})\cup(\bigcup_{u\notin X}P_{u}\backslash
Q_{u})$

On the one hand, no vertex of $\bigcup_{u\notin X}P_{u}\backslash Q_{u}$ has a
neighbor in $X^{\prime}$. On the other hand, as $X$ is an independent set, two
vertices belonging respectively to $Q_{u}$ and $Q_{v}$, $u,v\in X$, are not
adjacent. Therefore, $X^{\prime}$ is an independent set of $G_{(3)}$ of size
$n(\Delta-1)+\alpha(G)$. Now, assume that there is an independent set $X^{*}$
of size at least $n(\Delta-1)+\alpha(G)+1$ in $G_{(3)}$. There are necessarily
$\alpha(G)+1$ paths $P_{u}$ of $G_{(3)}$ which contain $\Delta$ vertices of
$X^{*}$. The vertices $u\in V(G)$ satisfying this property must be pairwise
non-adjacent, by definition of the edges $u_{2i+1}v_{2j+1}$. This yields a
contradiction as we identify an independent set of $G$ of size $\alpha(G)+1$.

We prove the second part of the statement, by proving that every vertex $w\in
G_{(3)}$ belongs to an MIS. If $w$ is isolated, it belongs trivially to all
MISs. If $w=u_{2i+1}$, $1\leq i\leq\Delta-1$, select an arbitrary MIS $X_{u}$
of $G$ containing $u$. We know that the set $X_{u}^{\prime}=(\bigcup_{v\in
X_{u}}Q_{v})\cup(\bigcup_{v\notin X_{u}}P_{v}\backslash Q_{v})$ is an MIS of
$G_{(3)}$ and $w\in X_{u}^{\prime}$. If $w=u_{2i}$ and is not isolated, then
we select an arbitrary MIS $Y_{u}$ of $G$ containing one of its neighbors. The
set $Y_{u}^{\prime}=(\bigcup_{v\in Y_{u}}Q_{v})\cup(\bigcup_{v\notin
Y_{u}}P_{v}\backslash Q_{v})$ is an MIS of $G_{(3)}$ and $w\in
Y_{u}^{\prime}$.

Assume graph $G$ is planar. One can, by defining function $\rho$ in a good way
(Fig. 2), produce a graph $G_{(3)}$ which is still planar, according to [19].
Unfortunately, one can find examples of graphs $G$ such that $G_{(3)}$ is
1-extendable while $G$ is not. In other words, unlike $(T_{2})$,
transformation $(T_{3})$ does not produce an “equivalent” graph in terms of
$1$-extendability.

##  4 Hardness of $1$-Extendability on subcubic planar graphs

The main goal of this section is to study the computational hardness of
$1$-Extendability. We show that the problem is NP-hard in subcubic planar
graphs and unit disk graphs.

###  4.1 Properties of the Garey-Johnson-Stockmeyer gadget

We now focus on restricted graph classes. Since our first motivation is the
context of wireless networks, we investigate the complexity of the problem in
graphs modeling this kind of practical situations. Unit disk graphs is a
natural graph class representing the conflict graph of wireless access points.
As it is often the case when dealing with unit disk graphs, we first tackle
the case of planar graphs of bounded degree. There exists a well-known gadget
[14] which allows, for any graph $G$, to produce a planar graph $G^{\prime}$
with $O(n)$ vertices which is equivalent to $G$ for the Maximum Independent
set problem. Concretely, $G^{\prime}$ is obtained by replacing each crossing
appearing in an embedding of $G$ in the plane by this gadget. In this article,
we call it the GJS-gadget (for Garey-Johnson-Stockmeyer) and denote it by
$H_{\mbox{\scriptsize{GJS}}}$ (see Fig. 3(a)). Unfortunately, this trick does
not work directly for $1$-Extendability. In order to make it work, our idea is
to define a first reduction producing a non-planar graph, but where the
crossings satisfy some interesting properties. Secondly, we use the previously
mentioned gadget on this intermediate graph. Lastly, we use well-known tricks
from the literature in order to reduce the maximum degree of the reduced
graph, and to obtain a unit disk graph.

$x$$x^{\prime}$$y$$y^{\prime}$$z_{x}^{y}$$a_{x}^{y}$$a_{x}^{y^{\prime}}$$z_{x}^{y^{\prime}}$$z_{x^{\prime}}^{y}$$a_{x^{\prime}}^{y}$$a_{x^{\prime}}^{y^{\prime}}$$z_{x^{\prime}}^{y^{\prime}}$

(a) A planar embedding of $H_{\mbox{\scriptsize{GJS}}}$ together with an MIS
of it (in blue)

$\begin{array}[]{|c|c|c|c|}\hline\cr&\left|S\cap X\right|=0&=1&=2\\\
\hline\cr\left|S\cap Y\right|=0&7&8&8\\\ \hline\cr\left|S\cap
Y\right|=1&8&9&9\\\ \hline\cr\left|S\cap Y\right|=2&7&8&9\\\
\hline\cr\end{array}$

(b) Largest MISs $S$ of $H_{\mbox{\scriptsize{GJS}}}$ containing a certain
subset

Figure 3: The GJS-gadget [14]

Description of the gadget. Fig. 3(a) represents $H_{\mbox{\scriptsize{GJS}}}$.
Let $X=\left\\{x,x^{\prime}\right\\}$, $Y=\left\\{y,y^{\prime}\right\\}$,
$Z=\left\\{z_{x}^{y},z_{x}^{y^{\prime}},z_{x^{\prime}}^{y},z_{x^{\prime}}^{y^{\prime}}\right\\}$,
$A=\left\\{a_{x}^{y},a_{x}^{y^{\prime}},a_{x^{\prime}}^{y},a_{x^{\prime}}^{y^{\prime}}\right\\}$.
We denote by $b_{x}^{y}$ the common neighbor of $z_{x}^{y}$ and $a_{x}^{y}$.
Vertices $b_{x}^{y^{\prime}},b_{x^{\prime}}^{y},b_{x^{\prime}}^{y^{\prime}}$
are defined similarly. We fix
$B=\left\\{b_{x}^{y},b_{x}^{y^{\prime}},b_{x^{\prime}}^{y},b_{x^{\prime}}^{y^{\prime}}\right\\}$.
The “$C_{6}$” of $H_{\mbox{\scriptsize{GJS}}}$ refers to the vertices which
are not in sets $X,Y,Z,A,$ and $B$. The size of the MIS of
$H_{\mbox{\scriptsize{GJS}}}$ is 9, according to [14]. Blue vertices give an
example of such MIS. Vertices $x$, $x^{\prime}$, $y$ and $y^{\prime}$ are
called the endpoints of $H_{\mbox{\scriptsize{GJS}}}$.

Fig. 3(b) indicates the sizes of a largest independent set $S$ we obtain if we
fix the intersection size with $X$ and $Y$. For example, a largest independent
set $S$ which contains vertices $x,y,y^{\prime}$ is of size 8: one of them is
such that it also contains $a_{x}^{y},a_{x^{\prime}}^{y}$ and 3 vertices from
the $C_{6}$. Another example: a largest independent set $S$ containing exactly
one vertex of $X$ and one vertex of $Y$ has size 9. The blue vertices of Fig.
3(a) form this kind of independent sets, with $S\cap X=\left\\{x\right\\}$ and
$S\cap Y=\left\\{y^{\prime}\right\\}$.

Consider an embedding of some graph $G$ in the plane, and a crossing
consisting of two edges $uu^{\prime}$ and $vv^{\prime}$ (as, for instance, in
Fig. 4(a), where $v_{1}v_{1}^{\prime}$ plays the role of $vv^{\prime}$). By
replacing the crossing by a gadget, we mean removing the edges $uu^{\prime}$
and $vv^{\prime}$, adding a subgraph isomorphic to
$H_{\mbox{\scriptsize{GJS}}}$, and adding the edges $vx$, $uy^{\prime}$,
$v^{\prime}x^{\prime}$, and $u^{\prime}y$. By replacing each crossing of $G$
by a gadget, we obtain a graph $G_{+}$ which is not only planar, but also
equivalent to $G$ for the Maximum Independent Set problem, in the sense that
$G$ contains an independent set of size $k$ iff $G_{+}$ contains an
independent set of size $k+9\lambda$, where $\lambda$ is the number of
crossings in $G$ [14]. Fig. 4(a) shows an example of edge $uu^{\prime}$ of
some graph $G$ which is crossed by three other edges $v_{1}v_{1}^{\prime}$,
$v_{2}v_{2}^{\prime}$, and $v_{3}v_{3}^{\prime}$. In $G_{+}$, these crossings
become graphs isomorphic to $H_{\mbox{\scriptsize{GJS}}}$: they are denoted by
$H_{1}$, $H_{2}$, and $H_{3}$ respectively (Fig. 4(b)). Observe that, in Fig.
4(b), gadgets $H_{1}$, $H_{2}$, and $H_{3}$ are oriented in the same way (to
avoid confusions), but it is not a mandatory requirement for the reduction. In
other words, turning $H_{1}$ so that the neighbor of $u$ (resp. the neighbors
of $v_{1},v_{1}^{\prime}$) has degree four (resp. two) still would work.

$u$$u^{\prime}$$v_{1}$$v_{1}^{\prime}$$v_{2}$$v_{2}^{\prime}$$v_{3}$$v_{3}^{\prime}$

(a) Edge $uu^{\prime}$ crossing
$v_{1}v_{1}^{\prime},v_{2}v_{2}^{\prime},v_{3}v_{3}^{\prime}$

$u$$u^{\prime}$$v_{1}$$v_{1}^{\prime}$$v_{2}$$v_{2}^{\prime}$$v_{3}$$v_{3}^{\prime}$$H_{1}$$H_{2}$$H_{3}$

(b) After replacing each crossing in $G_{+}$

$u$$u^{\prime}$$v_{1}$$v_{1}^{\prime}$$v_{2}$$v_{2}^{\prime}$$v_{3}$$v_{3}^{\prime}$$H_{1}$$H_{2}$$H_{3}$

(c) An of $G$ completed with 9 vertices per crossing

Figure 4: Replacing each crossing by a GJS-gadget

As said previously, the size of an MIS $G_{+}$ is $\alpha(G)+9\lambda$, where
$\lambda$ is the number of crossings in the planar embedding of $G$. The idea
behind this statement is the following: if $S$ is an independent set of $G$,
then there exists an independent set $S_{+}$ of $G_{+}$ of size
$\left|S\right|+9\lambda$ which is made up of the vertices of $S$ and 9
vertices per crossing. In Fig. 4(c), the dark blue vertices represent an
independent set $S$ of $G$ and the light blue ones are the endpoints of the
gadgets, i.e. $x,x^{\prime},y,y^{\prime}$ in Fig. 3, which belong to $S_{+}$
in $G_{+}$. As $S$ is independent, one can select, for each gadget, one vertex
of $\left\\{x,x^{\prime}\right\\}$ (and one vertex of
$\left\\{y,y^{\prime}\right\\}$) which is not adjacent to an element of $S$.
We know that a largest independent set of $H_{\mbox{\scriptsize{GJS}}}$
intersecting both $\left\\{x,x^{\prime}\right\\}$ and
$\left\\{y,y^{\prime}\right\\}$ in exactly one element has size 9, which
corresponds to the MIS size of $H_{\mbox{\scriptsize{GJS}}}$.

######  Lemma 5 (Graphs $G$ and $G_{+}$ are equivalent for Maximum Independent
Set [14])

Any MIS $S$ of $G$ can be completed into an MIS $S_{+}\supseteq S$ of $G_{+}$
which contains exactly 9 vertices per crossing gadget. Conversely, given any
MIS $S^{*}$ of $G_{+}$, the vertices of $S^{*}$ which do not belong to a
crossing gadget of $G_{+}$ form an MIS of $G$.

Preservation of $1$-extendability. Our initial idea was to use the same gadget
to transform every graph into a planar one which preserves the
$1$-extendability of $G$. Unfortunately, the property described above for
Maximum Independent Set does not hold for $1$-Extendability. Indeed, one can
find examples of graphs $G$ such that $G$ is 1-extendable and $G_{+}$ is not.
For this reason, we state a weaker characterization involving the GJS-gadget.
We will see further that this result is enough to prove that $1$-Extendability
is NP-hard on planar graphs.

###### Proposition 2

Let $G$ be a graph embedded in the plane and $uu^{\prime}\in E(G)$. Let
$v_{1}v_{1}^{\prime},v_{2}v_{2}^{\prime},\ldots,v_{\ell}v_{\ell}^{\prime}$ be
the edges of $G$ which cross $uu^{\prime}$. Assume, for any $1\leq i\leq\ell$,
the following statements:

  * •

there is an MIS $S_{u}^{(i)}$ of $G$ such that
$S_{u}^{(i)}\cap\left\\{u,u^{\prime},v_{i},v_{i}^{\prime}\right\\}=\left\\{u\right\\}$,

  * •

there is an MIS $S_{u^{\prime}}^{(i)}$ of $G$ such that
$S_{u^{\prime}}^{(i)}\cap\left\\{u,u^{\prime},v_{i},v_{i}^{\prime}\right\\}=\left\\{u^{\prime}\right\\}$,

Let $G_{+}$ be the graph obtained from $G$ by replacing each crossing
$\left\\{uu^{\prime},v_{i}v_{i}^{\prime}\right\\}$ with a GJS-gadget. Then,
$G_{+}$ is 1-extendable iff $G$ is 1-extendable.

###### Proof

One direction is trivial. If $G_{+}$ is 1-extendable, then for any vertex $u$
outside a crossing gadget, i.e. $u\in V(G)$, there is an MIS $S^{*}$ of
$G_{+}$ containing $u$. According to Lemma 5, one can obtain an MIS $S$ of $G$
containing $u$ by removing the vertices of $S$ belonging to the gadgets. In
brief, for any $u\in V(G)$, there is an MIS of $G$ containing $u$.

We suppose now that $G$ is 1-extendable. This direction is trickier. We begin
with a few notation. Let $H_{i}$ be the crossing gadget
$H_{\mbox{\scriptsize{GJS}}}$ of
$\left\\{uu^{\prime},v_{i}v_{i}^{\prime}\right\\}$ (see Fig. 4(b)), and
$x_{i},x_{i}^{\prime},y_{i},y_{i}^{\prime}$ denote the endpoints of $H_{i}$,
$1\leq i\leq\ell$. We fix $x_{i}$ as the closest one to $u$ and $y_{i}$ as the
closest one to $v_{i}$. Our objective is to prove that each vertex of gadgets
$H_{i}$ belongs to some MIS of $G_{+}$. Indeed, we already know that the
vertices of $V(G)\subseteq V(G_{+})$ are contained in an MIS of $G_{+}$,
according to Lemma 5.

We pursue with an observation on the gadget $H_{\mbox{\scriptsize{GJS}}}$. Let
$a\in\\{x,x^{\prime}\\}$ and $b\in\\{y,y^{\prime}\\}$. Observe that there is a
single MIS of $H_{\mbox{\scriptsize{GJS}}}$ whose intersection with
$\\{x,x^{\prime}\\}$ is $\\{a\\}$ and whose intersection with
$\\{y,y^{\prime}\\}$ is $\\{b\\}$. We denote by $S_{ab}$ this set (for
instance, the set $S_{xy^{\prime}}$ is depicted in Fig. 3(a)). In addition, we
have $S_{xy}\cup S_{xy^{\prime}}\cup S_{x^{\prime}y}\cup
S_{x^{\prime}y^{\prime}}=V(H_{\mbox{\scriptsize{GJS}}})$. Consequently, in
order to prove that $G_{+}$ is 1-extendable, it is sufficient to show that
there are MISs of $G_{+}$ intersecting
$\left\\{x_{i},x_{i}^{\prime},y_{i},y_{i}^{\prime}\right\\}$ exactly in
$\left\\{x_{i},y_{i}\right\\}$, $\left\\{x_{i},y_{i}^{\prime}\right\\}$,
$\left\\{x_{i}^{\prime},y_{i}\right\\}$, and
$\left\\{x_{i}^{\prime},y_{i}^{\prime}\right\\}$ respectively. The remainder
consists in using both Lemma 5 and the assumptions on the MISs of $G$ to put
in evidence MISs of $G_{+}$ which intersect exactly these pairs. Let
$S_{u}^{(i)}$ and $S_{u^{\prime}}^{(i)}$ be as in the statement. We now show
how to complete them in order to obtain these MISs.

Completion of $S_{u}^{(i)}$. According to Lemma 5, one can produce an MIS
$S_{u,+}^{(i)}$ in $G_{+}$ which contains exactly 9 vertices per crossing
gadget and $S_{u}^{(i)}\subseteq S_{u,+}^{(i)}$. All vertices
$x_{j}^{\prime}$, $1\leq j\leq\ell$ necessarily belong to $S_{u,+}^{(i)}$.
Indeed, $x_{1}$ is adjacent to $u$, so if we aim at picking up 9 vertices in
$H_{1}$, according to Fig. 3(b), $x_{1}^{\prime}\in S_{u,+}^{(i)}$. Then,
$x_{2}$ is adjacent to $x_{1}^{\prime}$, so $x_{2}^{\prime}$ must be picked
up, etc. In particular, $x_{i}^{\prime}\in S_{u,+}^{(i)}$. Then, we know that
neither $v_{i}$ nor $v_{i}^{\prime}$ are in $S_{u}^{(i)}$. Therefore,
$S_{u,+}^{(i)}$ may contain either $y_{i}$ or $y_{i}^{\prime}$ or both of
them. But, it suffices to pick up exactly one of them to have $\left|H_{i}\cap
S_{u,+}^{(i)}\right|=9$. Moreover, selecting either $y_{i}$ or
$y_{i}^{\prime}$ when we produce $S_{u,+}^{(i)}$ does not influence the
adjacency over the other crossing gadgets or the rest of the graph. Hence,
there are two MISs of $G_{+}$: one intersecting exactly
$\left\\{x_{i}^{\prime},y_{i}\right\\}$ and another intersecting exactly
$\left\\{x_{i}^{\prime},y_{i}^{\prime}\right\\}$.

Completion of $S_{u^{\prime}}^{(i)}$. The symmetrical analysis provides us
with two MISs of $G_{+}$ intersecting the endpoints of $H_{i}$ on exactly
$\left\\{x_{i},y_{i}\right\\}$ and $\left\\{x_{i},y_{i}^{\prime}\right\\}$
respectively.

In summary, for any $1\leq i\leq\ell$, there are MISs which respectively
intersect the set $\left\\{x_{i},x_{i}^{\prime},y_{i},y_{i}^{\prime}\right\\}$
in pairs $\left\\{x_{i},y_{i}\right\\}$,
$\left\\{x_{i},y_{i}^{\prime}\right\\}$,
$\left\\{x_{i}^{\prime},y_{i}\right\\}$, and
$\left\\{x_{i}^{\prime},y_{i}^{\prime}\right\\}$. Referring to our previous
observation, this ensures us that all vertices in gadgets $H_{i}$ are covered
by MISs of $G_{+}$. As a conclusion, $G_{+}$ is 1-extendable.

Observe that the assumptions concerning the MISs of $G_{+}$ are essential if
we want pairs $\left\\{x_{i},y_{i}\right\\}$,
$\left\\{x_{i},y_{i}^{\prime}\right\\}$,
$\left\\{x_{i}^{\prime},y_{i}\right\\}$, and
$\left\\{x_{i}^{\prime},y_{i}^{\prime}\right\\}$ of each gadget $H_{i}$ to be
covered by MISs. This property is not achieved by all 1-extendable graphs $G$:
take for instance an embedding of some complete bipartite graph $K_{n,n}$ with
$n\geq 3$, every MIS intersects each crossing on exactly two vertices.

###  4.2 Planar embedding

The GJS-gadget is a key tool in our proof that $1$-Extendability is NP-hard on
planar graphs. We reduce from an NP-hard variant of 3SAT called Planar
Monotone Rectilinear 3SAT, abbreviated PMR 3SAT. Given an input $\varphi$ of
PMR 3SAT, we design a graph $G_{\varphi}$ such that $\varphi$ is satisfiable
iff $G_{\varphi}$ is 1-extendable. Furthermore, $G_{\varphi}$ is planar and
its maximum degree is 3. We begin with the construction of $G_{\varphi}$ step
by step. Then, we show that the $1$-extendability of $G_{\varphi}$ depends on
the satisfiability of the formula $\varphi$.

Starting point of the reduction. We reduce from PMR 3SAT, which is NP-hard
[4]. In this variant of 3SAT, clauses and variables can be represented in the
plane in a certain way. The input is a set of variables
$X=\left\\{x_{1},\ldots,x_{n}\right\\}$ and a CNF-SAT formula $\varphi$ over
$X$ with exactly three variables per clause. The clauses $C_{1},\ldots,C_{m}$
are monotone: they contain either three positive literals or three negative
literals. Moreover, $\varphi$ admits a rectilinear representation, that we now
explain. Each variable is a point on the x-axis. The positive (resp. negative)
clauses are represented by horizontal segments above (resp. below) the x-axis.
When a variable $x_{i}$ appears in a given clause, a vertical edge must
connect the point $x_{i}$ on the x-axis with the segment of this clause (at
any point of the segment). Such a representation is rectilinear if no edge
crosses a clause segment. Fig. 5 provides an example of a formula $\varphi$,
with $m=5$, which admits a rectilinear representation.

x$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{2}\vee x_{3}\vee x_{4}$$x_{1}\vee
x_{2}\vee x_{5}$$\neg x_{1}\vee\neg x_{2}\vee\neg x_{3}$$\neg x_{3}\vee\neg
x_{4}\vee\neg x_{5}$$\neg x_{1}\vee\neg x_{3}\vee\neg x_{5}$

Figure 5: A rectilinear representation of a PMR 3SAT instance
$C_{1},\ldots,C_{5}$

Let $\varphi$ be an input of PMR 3SAT provided with its rectilinear
representation. The construction of $G_{\varphi}$ depends on the rectilinear
representation of $\varphi$. We proceed with two intermediate steps: first
graph $G_{\varphi}^{\prime\prime}$, second graph $G_{\varphi}^{\prime}$.

Construction of $G_{\varphi}^{\prime\prime}$. The first step is inspired from
Mohar’s reduction [19] for Maximum Independent Set. We replace each variable
$x_{i}$ on the x-axis by a cycle. Let $r$ be the number of appearances of
$x_{i}$ (as a literal $x_{i}$ or $\neg x_{i}$) in the clauses
$C_{1},\ldots,C_{m}$ of $\varphi$. The point representing variable $x_{i}$
becomes a cycle
$x_{i}^{1},\bar{x}_{i}^{1},x_{i}^{2},\bar{x}_{i}^{2},\ldots,x_{i}^{r},\bar{x}_{i}^{r}$
of length $2r$, drawn as an axis-parallel rectangle (see Fig. 6(a)). We denote
by $c^{*}$ the total number of vertices in the variable cycles. Each clause
$C_{j}=\ell_{j}^{1}\vee\ell_{j}^{2}\vee\ell_{j}^{3}$ is replaced by a triangle
$T_{j}$ of three vertices $v_{j}^{1},v_{j}^{2},v_{j}^{3}$. The edges of these
triangles are called $T$-edges. Each vertex of the clause is placed at the
intersection between the clause segment and vertical edges of the rectilinear
representation. In this way, vertices $v_{j}^{1}$, $v_{j}^{2}$ and $v_{j}^{3}$
are aligned horizontally and, w.l.o.g, we assume $v_{j}^{1}$ (resp.
$v_{j}^{3}$) is the leftmost (resp. rightmost) vertex of $T_{j}$ on the clause
segment. Edges $v_{j}^{1}v_{j}^{2}$ and $v_{j}^{2}v_{j}^{3}$ are drawn as
straight lines. The third one, $v_{j}^{1}v_{j}^{3}$, can be represented as an
almost flat curve, passing above (resp. below) vertex $v_{2}^{j}$ for positive
(resp. negative) clauses. If $\ell_{j}^{q}=x_{i}$ for some $1\leq j\leq m$ and
$q\in\left\\{1,2,3\right\\}$, then vertex $v_{j}^{q}$ is connected to some
cycle vertex $\bar{x}_{i}^{s}$ of the top of the rectangle. Otherwise, if
$\ell_{j}^{q}=\neg x_{i}$, then vertex $v_{j}^{q}$ is connected to some cycle
vertex $x_{i}^{s}$ of the bottom of the rectangle. For now, the described
embedding is planar. Fig. 6(a) shows the embedding of the instance of Fig. 5.
Vertices $\bar{x}_{i}^{s}$ are drawn in grey to distinguish them from vertices
$x_{i}^{s}$ (in white).

Less formally, each parity of a variable cycle represents a certain
assignation of this variable. Picking up $x_{i}^{1},x_{i}^{2},\ldots$ (resp.
$\bar{x}_{i}^{1},\bar{x}_{i}^{2},\ldots$) into an independent set will
correspond to assigning $x_{i}$ to False (resp. True).

We add a “pendant” vertex $\pi_{j}$ for any triangle $T_{j}$, $1\leq j\leq m$,
that is, $\pi_{j}$ is adjacent to all vertices of $T_{j}$. The edges created
by this operation, i.e. all $v_{j}^{q}\pi_{j}$, are called pendant edges.
Consider the following embedding. We fix two horizontal axes $\mbox{x}^{+}$
and $\mbox{x}^{-}$: the first one above the x-axis and all segments of the
positive clauses, the second one below the x-axis and all segments of the
negative clauses. The pendants issued from the positive clauses are placed on
the $\mbox{x}^{+}$-axis such that every edge $(v_{j}^{2},\pi_{j})$ is
vertical. We represent edges $(v_{j}^{1},\pi_{j})$ and $(v_{j}^{3},\pi_{j})$
as straight lines (they cannot be vertical). We proceed similarly with
pendants of the negative clauses on the $\mbox{x}^{-}$-axis. We denote by
$G_{\varphi}^{\prime\prime}$ the obtained graph. Its embedding is not planar.
Fig. 6(b) shows graph $G_{\varphi}^{\prime\prime}$ corresponding to the
instance $\varphi$ of Fig. 5. Pendant edges are drawn in red. We claim that
each vertex of $G_{\varphi}^{\prime\prime}$ belongs to an MIS. This might seem
counter-intuitive, but the equivalence between the $1$-extendability of the
output instance and the satisfaction of $\varphi$ will appear later (when we
will eventually define $G_{\varphi}$).

(a) Planar embedding in Mohar’s style

$\mbox{x}^{+}$$\mbox{x}^{-}$

(b) Embedding of $G_{\varphi}^{\prime\prime}$ (not planar)

Figure 6: Graph $G_{\varphi}^{\prime\prime}$ with and without pendant
vertices.

###### Lemma 6

Graph $G_{\varphi}^{\prime\prime}$ is 1-extendable.

###### Proof

Sets $\left\\{v_{j}^{1},v_{j}^{2},v_{j}^{3},\pi_{j}\right\\}$, for any $1\leq
j\leq m$, form an induced $K_{4}$. Hence there is a clique cover made up of
all clauses $K_{4}$ together with half of the edges of the variable cycles.
Hence an MIS of $G_{\varphi}^{\prime\prime}$ has size at most $m+c^{*}/2$.
Here is an independent set of size $m+c^{*}/2$: pick up all pendant vertices
$\pi_{j}$, $1\leq j\leq m$, and, for each variable, an MIS of the
corresponding variable cycle (each cycle, being of even length, has two MISs,
we may take any of them). This shows not only that
$\alpha(G_{\varphi}^{\prime\prime})=m+c^{*}/2$ but also that all pendant and
cycle vertices belong to some MIS. Finally, each triangle vertex $v_{j}^{q}$
also belongs to an MIS: in the variable cycle adjacent to $v_{j}^{q}$, take
the MIS not adjacent to $v_{j}^{q}$; in the other variable cycles, take any
MIS in it; finally, take the pendant vertices of the other clauses (i.e.
$\pi_{h}$ for $h\neq j$).

Construction of $G_{\varphi}^{\prime}$. The second step consists in
transforming $G_{\varphi}^{\prime\prime}$ into some equivalent graph
$G_{\varphi}^{\prime}$ which is planar and has maximum degree 3. Two types of
crossings appear in the embedding of $G_{\varphi}^{\prime\prime}$. Each of
them necessarily involve pendant edges.

  * •

Type A: a pendant edge $v_{j}^{q}\pi_{j}$ crosses a $T$-edge
$v_{j^{\prime}}^{p^{\prime}}v_{j^{\prime}}^{q^{\prime}}$ (we may have
$j=j^{\prime}$),

  * •

Type B: a pendant edge $v_{j}^{q}\pi_{j}$ crosses another pendant edge
$v_{j^{\prime}}^{q^{\prime}}\pi_{j^{\prime}}$, $j\neq j^{\prime}$.

We observe that for any of these types of crossings in the embedding of
$G_{\varphi}^{\prime\prime}$, the assumptions of Proposition 2 are fulfilled.

###### Lemma 7

Let $\left\\{uu^{\prime},vv^{\prime}\right\\}$ be a crossing of the embedding
of $G_{\varphi}^{\prime\prime}$. There exist two MISs $S_{u},S_{u^{\prime}}$
of $G_{\varphi}^{\prime\prime}$ which intersect
$\left\\{u,u^{\prime},v,v^{\prime}\right\\}$ respectively in
$\left\\{u\right\\}$ and $\left\\{u^{\prime}\right\\}$.

###### Proof

We distinguish two cases, depending on the type of crossing.

Type A. Let $uu^{\prime}=v_{j}^{q}\pi_{j}$ and
$vv^{\prime}=v_{j^{\prime}}^{p^{\prime}}v_{j^{\prime}}^{q^{\prime}}$. Let
$S_{u}$ be the MIS containing $v_{j}^{q}$ with all pendant vertices $\pi_{h}$,
$h\neq j$ of other clauses (and $c^{*}/2$ cycle vertices selected properly).
Let $S_{u^{\prime}}$ be the MIS containing all pendant vertices (plus
$c^{*}/2$ cycle vertices).

Type B. Let $uu^{\prime}=v_{j}^{q}\pi_{j}$ and
$vv^{\prime}=v_{j^{\prime}}^{q^{\prime}}\pi_{j^{\prime}}$. We fix some
$p^{\prime}\in\left\\{1,2,3\right\\}$, $p^{\prime}\neq q^{\prime}$. Let
$S_{u}$ be the MIS we finally obtain by picking up $v_{j}^{q}$,
$v_{j^{\prime}}^{p^{\prime}}$, and all pendant vertices $\pi_{h}$, $h\neq
j,j^{\prime}$. There is no assignation conflict between $v_{j}^{q}$ and
$v_{j^{\prime}}^{p^{\prime}}$ since only pendant edges involving literals of
the same sign can cross each other with the monotone rectilinear
representation. Similarly, let $S_{u^{\prime}}$ be the MIS we obtain by taking
$v_{j^{\prime}}^{p^{\prime}}$ and all pendant vertices $\pi_{h}$, $h\neq
j^{\prime}$, in particular $u^{\prime}=\pi_{j}$.

As a consequence of Lemma 7 together with Proposition 2, one can replace each
crossing of the embedding of $G_{\varphi}^{\prime\prime}$ by a gadget
$H_{\mbox{\scriptsize{GJS}}}$ without altering its $1$-extendability. The
graph obtained is thus planar and has maximum degree 6 (which is the maximum
degree of graph $H_{\mbox{\scriptsize{GJS}}}$). Then, we apply transformation
$(T_{3})$ with $\Delta=6$ to decrease its maximum degree. Finally, we obtain
graph $G_{\varphi}^{\prime}$, which is planar and has maximum degree 3.

###### Lemma 8

Graph $G_{\varphi}^{\prime}$ is 1-extendable.

###### Proof

First, apply Lemma 7 together with Proposition 2, second Lemma 4.

According to Transformation $(T_{3})$, each vertex $u$ of
$G_{\varphi}^{\prime\prime}$ is transformed into an induced path $P_{u}$ of
length 11 in $G_{\varphi}^{\prime}$. There is a natural correspondence between
the MISs of $G_{\varphi}^{\prime\prime}$ and those of $G_{\varphi}^{\prime}$.
Given an MIS $S^{\prime\prime}$ of $G_{\varphi}^{\prime\prime}$, one can
produce an MIS $S^{\prime}$ of $G_{\varphi}^{\prime}$ such that the paths
$P_{u}$ with $\left|P_{u}\cap S^{\prime}\right|=6$ represent the vertices
$u\in S^{\prime\prime}$. Conversely, let $S^{\prime}$ be some MIS of
$G^{\prime}$: picking up the vertices $u$ such that $\left|P_{u}\cap
S^{\prime}\right|=6$ produces an MIS of $G_{\varphi}^{\prime\prime}$. In the
remainder of the section, when we say that a vertex $u\in
G_{\varphi}^{\prime\prime}$ belongs to an MIS $S^{\prime}$ of
$G_{\varphi}^{\prime}$, we actually mean that $\left|P_{u}\cap
S^{\prime}\right|=6$.

Construction of $G_{\varphi}$. We are now ready to describe the final graph
$G_{\varphi}$ which consists in a small extension of $G_{\varphi}^{\prime}$.
We add a cycle $z_{1},\bar{z}_{1},\ldots,z_{m},\bar{z}_{m}$ of size $2m$ to
the graph $G_{\varphi}^{\prime}$. Let
$Z=\left\\{z_{1},z_{2},\ldots,z_{m}\right\\}$ and
$\bar{Z}=\left\\{\bar{z}_{1},\bar{z}_{2},\ldots,\bar{z}_{m}\right\\}$. We
connect $z_{j}$ to $\pi_{j}$ for every $1\leq j\leq m$ \- concretely, as
$\pi_{j}$ became an induced path via transformation $(T_{3})$, we add an edge
between $z_{j}$ and a vertex of $P_{\pi_{j}}$. The graph obtained is
$G_{\varphi}$ and its size is polynomial in $|\varphi|$. The graph
$G_{\varphi}$ is planar: consider the embedding of $G_{\varphi}^{\prime}$,
draw the cycle $Z\cup\bar{Z}$ as a rectangle surrounding it and such that all
edges $\pi_{j}z_{j}$ are vertical. Its maximum degree is 3. We are now ready
to prove our result.

###### Theorem 4.1

$1$-Extendability is NP-hard, even on planar graphs of maximum degree $3$.

###### Proof

We begin with the proof that
$\alpha(G_{\varphi})=\alpha(G_{\varphi}^{\prime})+m$. The value
$\alpha(G_{\varphi}^{\prime})+m$ is clearly an upper bound of the size of
independent sets in $G_{\varphi}$ as they cannot contain $m+1$ elements of
$Z\cup\bar{Z}$. Moreover, the union of any MIS of $G_{\varphi}^{\prime}$ with
$\bar{Z}$ is an independent set of this size. As a consequence, for all
$S\subseteq V(G_{\varphi})$, $S$ is an MIS of $G_{\varphi}$ iff $S\cap
V(G^{\prime}_{\varphi})$ is an MIS of $G^{\prime}_{\varphi}$ and
$S\cap(Z\cup\bar{Z})$ is an MIS of $G[Z\cup\bar{Z}]$. As
$G_{\varphi}^{\prime}$ is 1-extendable (Lemma 8), we know that all vertices of
$V(G_{\varphi}^{\prime})$ belong to some MIS of $G_{\varphi}$. Moreover
$G[Z\cup\bar{Z}]$ contains exactly two MIS: $Z$ and $\bar{Z}$. As said
previously, every vertex of $\bar{Z}$ is contained in an MIS of $G_{\varphi}$.
Hence, $G_{\varphi}$ is $1$-extendable iff it admits an MIS containing $Z$.

Assume $\varphi$ is satisfiable: there is an assignment $A$ of variables which
satisfies $\varphi$. We describe an MIS of $G^{\prime\prime}_{\varphi}$, which
can easily be transformed into an MIS of $G^{\prime}_{\varphi}$. If $x_{i}$’s
assignment via $A$ is True, we pick vertices
$\bar{x}_{i}^{1},\bar{x}_{i}^{2},\ldots$ of its variable cycle, otherwise we
pick the other parity $x_{i}^{1},x_{i}^{2},\ldots$. Therefore, if $x_{i}$’s
assignment is True, we cannot pick any triangle vertex representing $\neg
x_{i}$ as it is in conflict with one $\bar{x}_{i}^{s}$. This assignment $A$ is
such that at least one literal of each clause is assigned to True. So, for
each clause $C_{j}$, we select arbitrary one of its literals $\ell_{j}^{q}$
which is positively assigned with $A$ and pick the vertex $v_{j}^{q}$. The
chosen vertices form an independent set $S_{A}^{\prime\prime}$ of size
$\alpha(G_{\varphi}^{\prime\prime})$ in $G_{\varphi}^{\prime\prime}$. Observe
that $S_{A}^{\prime\prime}$ does not contain any pendant vertex. This set
$S_{A}^{\prime\prime}$ can be transformed into a corresponding MIS
$S_{A}^{\prime}$ in $G_{\varphi}^{\prime}$ which contains 6 vertices per path
$P_{u}$ if $u\in S_{A}^{\prime\prime}$. Thus, no pendant $\pi_{j}$ belongs to
$S_{A}^{\prime}$. As the neighborhood of $Z$ in $G_{\varphi}$ is made up only
of pendants $\pi_{j}$, $S_{A}^{\prime}\cup Z$ is an MIS of $G_{\varphi}$ and
the graph is 1-extendable.

Suppose now that $G_{\varphi}$ is 1-extendable. So there is an MIS $Z\cup
S^{\prime}$ of $G_{\varphi}$, with $S^{\prime}\subseteq
V(G^{\prime}_{\varphi})$. We know that, from $S^{\prime}$, we can retrieve an
MIS $S^{\prime\prime}$ of $G_{\varphi}^{\prime\prime}$ which contains vertices
$u$ such that $\left|P_{u}\cap S^{\prime}\right|=6$. The set
$S^{\prime\prime}$ cannot contain pendant vertices as they are all “adjacent”
to $Z$ in $G_{\varphi}$. We propose the following variable assignment $A$.
Half of the vertices of the variable cycles must be in $S^{\prime\prime}$,
otherwise it would not be an MIS. Consequently, if
$x_{i}^{1},x_{i}^{2},\ldots$ belong to $S^{\prime\prime}$, we assign $x_{i}$
to False, otherwise to True. Let us check that all clauses are satisfied. The
set $S^{\prime\prime}$ contains exactly one vertex per triangle representing
$C_{j}$. This vertex must be in accordance with the parity of the variable
cycle which is in $S^{\prime\prime}$: for example, if $\ell_{j}^{q}=\neg
x_{i}$ and $v_{j}^{q}\in S^{\prime\prime}$, then we have
$x_{i}^{1},x_{i}^{2},\ldots\in S^{\prime\prime}$, otherwise $S^{\prime\prime}$
would not be independent. Hence, $S^{\prime\prime}$ cannot contain two
vertices $v_{j}^{q}$ and $v_{j^{\prime}}^{q^{\prime}}$ such that
$\ell_{j}^{q}=\neg\ell_{j^{\prime}}^{q^{\prime}}$. In summary, assignment $A$
satisfies $\varphi$.

As for Maximum Independent Set, the problem $1$-Extendability is NP-hard on
subcubic planar graphs. If we put aside the degree criterion, one can see that
this proof also works if we do not use transformation $(T_{3})$. However, it
stays relatively tricky, while the NP-hardness of Maximum Independent Set for
planar graphs consists only in replacing each crossing of an arbitrary
embedding of $G$ by the GJS-gadget. Unfortunately, as mentioned in Section
4.1, such reduction does not work for $1$-Extendability. We wonder whether a
new gadget, certainly not so much different from
$H_{\mbox{\scriptsize{GJS}}}$, could be designed to make this reduction
simpler.

###  4.3 Unit disk graphs

Unit disk graphs [9] stand as a natural model for wireless networks. Indeed,
they are defined as the intersection graph of $n$ equal-sized disks in the
plane, which can represent Wi-Fi access points with the same radio range.
There exists a way to represent subdivided planar graphs with degree at most 4
as unit disk graphs, based on a result from Valiant [29].

######  Theorem 4.2 ([29])

A planar graph $G$ with maximum degree 4 can be embedded in the plane inside a
$O(|V(G)|)$-sized area in such a way that any vertex is at integer coordinates
and each edge is made up of vertical and horizontal line segments.

Consider a subcubic planar graph $G$ with such an embedding. We subdivide the
edges of $G$ such that (i) a vertex is placed at each turn of every edge (ii)
each segment (between two turns) is subdivided at least once and (iii) the
distance between two adjacent vertices is at most half of the length of the
shortest segment. The graph obtained - say $G^{\mbox{\scriptsize{UD}}}$ \- is
unit disk. Indeed, each vertex - admitting at most four neighbors, each of
them placed either in the two horizontal or vertical directions - can be
represented as a disk $\mathcal{D}$ with center $d$ such that:

  * •

it intersects a disk $\mathcal{D}_{\mbox{\scriptsize{N}}}$ (resp.
$\mathcal{D}_{\mbox{\scriptsize{S}}}$, $\mathcal{D}_{\mbox{\scriptsize{W}}}$,
$\mathcal{D}_{\mbox{\scriptsize{E}}}$) with center $d_{\mbox{\scriptsize{N}}}$
(resp. $d_{\mbox{\scriptsize{S}}}$, $d_{\mbox{\scriptsize{W}}}$,
$d_{\mbox{\scriptsize{E}}}$) where arc
$\overrightarrow{dd_{\mbox{\scriptsize{N}}}}$ (resp.
$\overrightarrow{dd_{\mbox{\scriptsize{S}}}}$,
$\overrightarrow{dd_{\mbox{\scriptsize{W}}}}$,
$\overrightarrow{dd_{\mbox{\scriptsize{E}}}}$) indicates the North direction
(resp. South, West, East)

  * •

disks $\mathcal{D}_{\mbox{\scriptsize{N}}}$,
$\mathcal{D}_{\mbox{\scriptsize{S}}}$, $\mathcal{D}_{\mbox{\scriptsize{W}}}$,
$\mathcal{D}_{\mbox{\scriptsize{E}}}$ do not intersect each other

In summary, given a subcubic planar graph $G$, one can produce in polynomial-
time a unit disk graph $G^{\mbox{\scriptsize{UD}}}$ thanks to transformation
$(T_{2})$. According to Lemma 3, $G$ is 1-extendable iff
$G^{\mbox{\scriptsize{UD}}}$ is 1-extendable.

###### Theorem 4.3

$1$-Extendability is NP-hard, even on unit disk graphs.

##  5 Parameterized algorithms

In this section we study a parameterized version of the $1$-extendability
problem:

param-$1$-Extendability Parameter: $k$ Input: A graph $G$, an integer $k$
Question: Does every vertex of $G$ belong to an independent set of size $k$?

We first show that the problem remains $W[1]$-hard by a reduction from
Multicolored Independent Set. We then investigate the existence of polynomial
kernels in restricted graph classes.

###### Theorem 5.1

param-$1$-Extendability is $W[1]$-hard.

###### Proof

We reduce from Multicolored Independent Set, where the input is a graph $G$
whose vertex set is partitioned into $k$ cliques $C_{1}$, $\dots$, $C_{k}$,
and the goal is to find an independent set of size $k$. We add, for every
$i\in[k]$, a pendant vertex $\pi_{i}$ adjacent to all vertices of $C_{i}$. We
also add a vertex $\omega$ adjacent to $\pi_{i}$, $i\in[k]$, and a vertex
$\pi_{\omega}$ adjacent to $\omega$ only. Let $G^{\prime}$ be the obtained
graph. We claim that every vertex of $G^{\prime}$ is contained in an
independent set of size $k+1$ iff $G$ contains an independent set of size $k$.
If $G$ contains an independent set $S$ of size $k$, then:

  * •

for every $i\in[k]$, every $x\in C_{i}$, then $x$ together with
$\\{\pi_{j}:j\neq i\\}\cup\\{\pi_{\omega}\\}$ is an independent set of size
$k+1$

  * •

$S$ together with $\omega$ is an independent set of size $k+1$.

  * •

the set $\\{\pi_{i}:i\in[k]\\}\cup\\{\pi_{\omega}\\}$ is an independent set of
size $k+1$.

Conversely, assume $\omega$ is in an independent set of size $k+1$. Then,
since the set of non-neighbors of $\omega$ is $G$ itself, it implies that $G$
must contain an independent set of size $k$, which concludes the proof.

By using Lemma 1, the problem is FPT in every hereditary graph class where
Maximum Independent Set is FPT. Examples of such classes are planar graphs and
triangle-free graphs (and more generally graphs excluding a clique of size $r$
as an induced subgraph, for every fixed $r\geqslant 3$) where, in addition,
Maximum Independent Set admits a kernel of polynomial size. The reduction of
Lemma 1, however, does not preserve polynomial kernels (although it naturally
gives polynomial Turing kernels). Hence, it is natural to ask whether
param-$1$-Extendability admits a polynomial kernel in these classes. We answer
positively to this question.

We say that a hereditary graph class $\mathcal{C}$ is MIS-$(c,t)$-friendly,
for two non-zero constants $c$ and $t$, if every graph of the class on $n$
vertices contains an independent set of size at least $t\cdot n^{c}$, and such
an independent set can be found in polynomial-time.

###### Theorem 5.2

Let $\mathcal{C}$ be an MIS-$(c,t)$-friendly class. param-$1$-Extendability on
$\mathcal{C}$ admits a kernel with $O(k^{\frac{1}{c}+\frac{1}{c^{2}}})$
vertices.

###### Proof

Let $G\in\mathcal{C}$, and $k\in\mathbb{N}$. Let $\mathcal{A}$ be the
algorithm which, for every graph of $\mathcal{C}$ on $n$ vertices, returns an
independent set of size $t\cdot n^{c}$. We assume
$|V(G)|\geqslant\left(\frac{k}{t}\right)^{\frac{1}{c}}$, since otherwise we
are done. We invoke $\mathcal{A}$ on $G$ in order to get an independent set
$S_{0}$, which is thus of size at least $k$. We remove $S_{0}$ and repeat the
process on the remaining vertices until $\mathcal{A}$ outputs a small
independent set. More precisely, let $R_{1}=V(G)\setminus S_{0}$, and start
with $i=1$. We run $\mathcal{A}$ on $G[R_{i}]$ which outputs an independent
set $S_{i}$. If $|S_{i}|<k$, we stop the process, and otherwise we continue
with $R_{i+1}=R_{i}\setminus S_{i}$, and increment $i$. Eventually, we end up
with a partition of $V(G)$ into $S_{0}$, $S_{1}$, $\cdots$, $S_{q}$ and
$R_{q+1}$ (we might have $q=0$). Every $S_{i}$ is an independent set of size
at least $k$ in $G$. As $G[R_{q+1}]\in\mathcal{C}$, algorithm $\mathcal{A}$
produces an independent set of size $t\left|R_{q+1}\right|^{c}<k$ on it, so
$|R_{q+1}|<\left(\frac{k}{t}\right)^{\frac{1}{c}}$.

We now describe a reduction rule which consists of a marking procedure of some
vertices of $S_{0}$, and removing those which were not marked. We then show
that if the reduction rule does not remove any vertex, then it means that the
graph has the desired number of vertices.

Marking procedure. First, mark $k$ vertices of $S_{0}$ chosen arbitrarily. For
every $x\in R_{q+1}$, let $s_{x}$ be the number of non-neighbors of $x$ in
$S_{0}$. Second, for each $x\in R_{q+1}$, mark $\min\\{k-1,s_{x}\\}$ vertices
of $S_{0}$ chosen arbitrarily. As announced, we remove all vertices of $S_{0}$
which were not marked by the previous procedure.

Safeness. Let $G^{\prime}$ be the graph obtained after the reduction rule, and
$S_{0}^{\prime}$ the vertices of $V(G^{\prime})\cap S_{0}$. Suppose every
vertex of $G^{\prime}$ belongs to an independent set of size $k$. We only need
to show that every removed vertex is in an independent set of size $k$ in $G$.
This is indeed the case, as we only removed vertices from $S_{0}$ and we kept
at least $k$ vertices from $S_{0}$. Conversely, suppose that every vertex of
$G$ is in an independent set of size $k$. Then:

  * •

since $|S_{0}^{\prime}|\geqslant k$ (as we marked $k$ vertices from $S_{0}$),
every vertex of $S_{0}^{\prime}$ belongs to an independent set of size $k$.

  * •

For every $i\in[q]$, since each $S_{i}$ is of size at least $k$, every vertex
of each $S_{i}$ is in an independent set of size at least $k$

  * •

for every $x\in R_{q+1}$, let $S$ be an independent set of size $k$ in $G$
containing $x$. Since $|S\cap S_{0}|\leqslant k-1$, we necessarily marked at
least $|S\cap S_{0}|$ non-neighbors of $x$ in $S_{0}$, hence we can always
replace the removed vertices of $S$ by other vertices of $S_{0}^{\prime}$ so
that $x$ belongs to an independent set of size $k$ in $G^{\prime}$.

#### Size of the reduced instance.

We apply the reduction rule as long as we can. Since we remove at least one
vertex if the reduction rule applies, the algorithm must end after $O(|V(G)|)$
applications of the rule. Then, if the reduction rule cannot apply, it means
we mark all vertices of $S_{0}$. But since we mark at most
$k+(k-1)\cdot\left(\frac{k}{t}\right)^{\frac{1}{c}}$ vertices of $S_{0}$, and
$S_{0}$ is of size at least $t\cdot|V(G)|^{c}$, it means that $G$ has
$O(k^{\frac{1}{c^{2}}+\frac{1}{c}})$ vertices. This concludes the proof of the
theorem.

We now apply the previous theorem to planar graphs and $K_{r}$-free graphs. By
the Four Color Theorem, every planar graph on $n$ vertices contains an
independent set of size $n/4$ which can be found in polynomial-time. Hence,
planar graphs is an MIS-$(1,1/4)$-friendly class. More generally,
$d$-degenerate graphs are MIS-$(1,\frac{1}{d+1})$-friendly. By Ramsey’s
theorem, for every $r\geqslant 3$, every $K_{r}$-free graphs on $n$ vertices
contains an independent set of size $n^{\frac{1}{r-1}}$ which can be found in
polynomial-time. Hence, $K_{r}$-free graphs is an
MIS-$\left(\frac{1}{r-1},1\right)$-friendly class.

###### Corollary 2

param-$1$-Extendability admits a kernel with $O(k^{2})$ vertices on planar
graphs and $d$-degenerate graphs for bounded $d$, and a kernel with
$O(k^{r^{2}})$ vertices on $K_{r}$-free graphs for every fixed $r\geqslant 3$.

##  6 Conclusion and further research

We investigated the computational complexity of $1$-Extendability. We showed
that in general graphs it cannot be solved in subexponential-time unless the
ETH fails, and that it remains NP-hard in subcubic planar graphs and in unit
disk graphs. Although this behavior seems to be the same as Maximum
Independent Set, we proved that Maximum Independent Set remains NP-hard (and
even W[1]-hard) in $1$-extendable graphs. It seems challenging to find a
larger class of graphs where $1$-Extendability is polynomial-time solvable
(but not trivial) while Maximum Independent Set remains NP-hard.

Another interesting subject would be to characterize $1$-extendable graphs of
graph classes where Maximum Independent Set is polynomial-time solvable: e.g.
chordal graphs, cographs, claw-free graphs. Such outcomes would extend the
result of Dean and Zito [12] which state that bipartite graphs are
1-extendable iff they admit a perfect matching.

We also studied param-$1$-Extendability, a parameterized version of
$1$-Extendability and showed that some results for Maximum Independent Set
could also be obtained for param-$1$-Extendability (although not being as
direct). It would be interesting to determine whether this is also the case
for other results about Maximum Independent Set [6, 7, 11], for instance: is
param-$1$-Extendability W[1]-hard in $C_{4}$-free graphs and in $K_{1,4}$-free
graphs? Does it admit a polynomial kernel in diamond-free graphs?

Finally, because of its applications in network design, finding an efficient
algorithm which works well in practice is of high importance. Toward this, a
first step would be to determine in which cases a vertex addition (or
deletion) preserves the property of being $1$-extendable. We note that such
results have already been obtained for the related property of being well-
covered [13].

## References

  * [1] Alekseev, V.: The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-Algebraic Methods in Applied Mathematics pp. 3–13 (1982)
  * [2] Angaleeswari, K., Sumathi, P., Swaminathan, V.: $k$-extendability in graphs. International Journal of Pure and Applied Math. 101(5), 801–809 (2015)
  * [3] Angaleeswari, K., Sumathi, P., Swaminathan, V.: Weakly $k$-extendable graphs. International Journal of Pure and Applied Math. 109(6), 35–40 (2016)
  * [4] de Berg, M., Khosravi, A.: Optimal binary space partitions in the plane. In: Proc. of COCOON. vol. 6196, pp. 216–225 (2010)
  * [5] Berge, C.: Some common properties for regularizable graphs, edge-critical graphs and B-graphs. Graph Theory and Algorithms, Lecture Notes in Computer Science 108, 108–123 (1981)
  * [6] Bonnet, É., Bousquet, N., Charbit, P., Thomassé, S., Watrigant, R.: Parameterized complexity of independent set in $H$-free graphs. Algorithmica 82(8), 2360–2394 (2020)
  * [7] Bonnet, É., Bousquet, N., Thomassé, S., Watrigant, R.: When maximum stable set can be solved in FPT time. In: Proc. of ISAAC. vol. 149, pp. 49:1–49:22 (2019)
  * [8] Chvátal, V., Slater, P.J.: A note on well-covered graphs. In: Quo Vadis, Graph Theory?, Annals of Discrete Mathematics, vol. 55, pp. 179–181. Elsevier (1993)
  * [9] Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discret. Math. 86(1-3), 165–177 (1990)
  * [10] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)
  * [11] Dabrowski, K.K., Lozin, V.V., Müller, H., Rautenbach, D.: Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. J. Discrete Algorithms 14, 207–213 (2012)
  * [12] Dean, N., Zito, J.S.: Well-covered graphs and extendability. Discret. Math. 126(1-3), 67–80 (1994)
  * [13] Finbow, A.S., Whitehead, C.A.: Constructions for well-covered graphs. Australasian Journal of Combinatorics 72(2), 273–289 (2018)
  * [14] Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976)
  * [15] Grzesik, A., Klimosová, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on $P_{6}$-free graphs. In: Proc. of SODA. pp. 1257–1271. SIAM (2019)
  * [16] Hackfeld, J., Koster, A.: The matching extension problem in general graphs is co-NP-complete. J. Comb. Optim. 35(3), 853–859 (2018)
  * [17] Impagliazzo, R., Paturi, R.: On the complexity of $k$-SAT. J. Comput. Syst. Sci. 62(2), 367–375 (2001)
  * [18] Liew, S.C., Kai, C.H., Leung, H.C., Wong, P.: Back-of-the-envelope computation of throughput distributions in CSMA wireless networks. IEEE Transactions on Mobile Computing 9(9), 1319–1331 (2010)
  * [19] Mohar, B.: Face covers and the genus problem for apex graphs. J. Comb. Theory, Ser. B 82(1), 102–117 (2001)
  * [20] The Network Simulator ns-3. https://www.nsnam.org/, accessed: 2021-09-30
  * [21] Plummer, M.D.: Some covering concepts in graphs. Journal of Combinatorial Theory 8(1), 91–98 (1970)
  * [22] Plummer, M.D.: On $n$-extendable graphs. Discrete Math. 31, 201–210 (1980)
  * [23] Plummer, M.D.: Extending matchings in graphs: A survey. Discret. Math. 127(1-3), 277–292 (1994)
  * [24] Poljak, S.: A note on stable sets and colorings in graphs. Commentationes Mathematicae Universitatis Carolinae pp. 307–309 (1974)
  * [25] Ravindra, G.: B-graphs. In: Proc. Symp. Graph Theory, ISI Lecture Notes Calcutta. vol. 4, pp. 268–280 (1976)
  * [26] Ravindra, G.: Well covered graphs. J. Combin. Inform. System Sci. 2, 20–21 (1977)
  * [27] Sankaranarayana, R.S., Stewart, L.K.: Complexity results for well-covered graphs. Networks 22(3), 247–262 (1992)
  * [28] Tankus, D., Tarsi, M.: Well-covered claw-free graphs. Journal of Combinatorial Theory, Series B 66(2), 293–302 (1996)
  * [29] Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Computers 30(2), 135–140 (1981)


#  Non-isomorphic graphs with common degree sequences

Rikio Ichishima  Department of Sport and Physical Education, Faculty of
Physical Education, Kokushikan University, 7-3-1 Nagayama, Tama-shi, Tokyo
206-8515, Japan<EMAIL_ADDRESS>and  Francesc A. Muntaner-Batle
Graph Theory and Applications Research Group, School of Electrical Engineering
and Computer Science, Faculty of Engineering and Built Environment, The
University of Newcastle, NSW 2308 Australia<EMAIL_ADDRESS>In memory of
Susana Clara López Masip

(Date: March 12, 2023)

###### Abstract.

For all positive even integers $n$, graphs of order $n$ with degree sequence

$S_{n}:1,2,\dots,n/2,n/2,n/2+1,n/2+2,\dots,n-1$

naturally arose in the study of a labeling problem in [2]. This fact motivated
the authors of the aforementioned paper to study these sequences and as a
result of this study they proved that there is a unique graph of order $n$
realizing $S_{n}$ for every even integer $n$. The main goal of this paper is
to generalize this result.

###### Key words and phrases:

vertex degree, degree sequence, isomorphism problems in graph theory, graph
operation

###### 1991 Mathematics Subject Classification:

Primary 05C07; Secondary 05C60, 05C76

##  1\. Introduction

Unless stated otherwise, the graph-theoretical notation and terminology used
here will follow Chartrand and Lesniak [1]. In particular, we assume that
graphs considered in this paper are simple, that is, without loops or multiple
edges. To indicate that a graph has _vertex set_ $V$ and _edge set_ $E$, we
write $G=\left(V,E\right)$. To emphasize that $V$ and $E$ are the vertex set
and edge set of a graph $G$, we will write $V$ as $V\left(G\right)$ and $E$ as
$E\left(G\right)$.

The _removal of a vertex_ $v$ from a graph $G$ results in that subgraph $G-v$
of $G$ consisting of all vertices of $G$ except $v$ and all edges not incident
with $v$. Thus, $G-v$ is the maximal subgraph of $G$ not containing $v$. On
the other hand, if $v$ is not adjacent in $G$, _the addition of vertex_ $v$
results in the smallest supergraph $G+v$ of $G$ containing the vertex $v$ and
all edges incident with $v$. The _union_ $G\cong G_{1}\cup G_{2}$ has
$V\left(G\right)=V\left(G_{1}\right)\cup V\left(G_{2}\right)$ and
$E\left(G\right)=E\left(G_{1}\right)\cup E\left(G_{2}\right)$.

The _degree_ of a vertex $v$ in a graph $G$ denoted by $\deg_{G}v$ is the
number of edges incident with $v$. A sequence $s:d_{1},d_{2},\dots,d_{n}$ of
nonnegative integers is called a _degree sequence_ of a graph $G$ of order $n$
if the vertices of $G$ can be labeled $v_{1},v_{2},\dots,v_{n}$ so that $\deg
v_{i}=d_{i}$ for $1\leq i\leq n$. Throughout this paper, we write the degree
sequence of a graph as an increasing sequence. A finite sequence $s$ of
nonnegative integers is _graphical_ if there exists some graph that realizes
$s$, that is, $s$ is a degree sequence of some graph.

The concepts of graph isomorphism and isomorphic graphs are also crucial for
the development of this paper, and although they are very basic in graph
theory, we introduce them as a matter of completeness. Let
$G_{1}=\left(V_{1},E_{1}\right)$ and $G_{2}=\left(V_{2},E_{2}\right)$ be two
graphs. They are _isomorphic_ (written $G_{1}\cong G_{2}$) if there exists a
bijective function $\phi:V_{1}\rightarrow V_{2}$ such that $xy\in E_{1}$ if
and only if $\phi\left(x\right)\phi\left(y\right)\in E_{2}$. In this case, the
function $\phi$ is called an _isomorphism_ from $G_{1}$ to $G_{2}$.

The following two lemmas regarding isomorphism of graphs are very elementary
and fundamental, but nevertheless, necessary for the proof of our main result
of this paper. Hence, we state and prove them next.

######  Lemma 1.1.

Let $G_{1}=\left(V_{1},E_{1}\right)$ and $G_{2}=\left(V_{2},E_{2}\right)$ be
two graphs of order $n$ for which there exist unique vertices $v_{1}\in V_{1}$
and $v_{2}\in V_{2}$ such that

$\deg_{G_{1}}v_{1}=\deg_{G_{2}}v_{2}=n-1\text{.}$

Then $G_{1}\cong G_{2}$ if and only if $G_{1}-v_{1}\cong G_{2}-v_{2}$.

###### Proof.

First, assume that $G_{1}\cong G_{2}$. Then there exists an isomorphism
$\phi:V_{1}\rightarrow V_{2}$. Since $v_{i}$ ($i=1,2$) are the only vertices
of $V_{i}$ with degree $n-1$ and each isomorphism preserves degrees, it
follows that $\phi\left(v_{1}\right)=v_{2}$. Thus, if we consider
$G_{1}-v_{1}$ and $G_{2}-v_{2}$, it follows that the function
$\phi^{\prime}:V_{1}\backslash\\{v_{1}\\}\rightarrow
V_{2}\backslash\\{v_{2}\\}$ defined by
$\phi^{\prime}\left(a\right)=\phi\left(a\right)$ for all $a\in
V_{1}\backslash\\{v_{1}\\}$ is well defined and bijective. Furthermore, $ab\in
E\backslash\\{v_{1}x\mid x\in V_{1}\backslash\\{v_{1}\\}\\}$ if and only if
$\phi^{\prime}\left(a\right)\phi^{\prime}\left(b\right)\in
E\backslash\\{v_{2}x\mid x\in V_{2}\backslash\\{v_{2}\\}\\}$. This implies
that $\phi^{\prime}:V_{1}\backslash\\{v_{1}\\}\rightarrow
V_{2}\backslash\\{v_{2}\\}$ is an isomorphism and hence $G_{1}\cong G_{2}$.

Next, assume that $H_{1}=\left(V_{1}^{\prime},E_{1}^{\prime}\right)$ and
$H_{2}=\left(V_{2}^{\prime},E_{2}^{\prime}\right)$ are two isomorphic graphs
with an isomorphism $\phi:V_{1}^{\prime}\rightarrow V_{2}^{\prime}$. Also, let
$v_{1}$ and $v_{2}$ be two new vertices and consider two graphs $H_{1}+v_{1}$
and $H_{2}+v_{2}$. We show that $H_{1}+v_{1}\cong H_{2}+v_{2}$. To do this,
consider the function $\phi^{\prime}:V\left(H_{1}+v_{1}\right)\rightarrow
V\left(H_{2}+v_{2}\right)$ defined by

$\phi^{\prime}\left(v\right)=\left\\{\begin{tabular}[]{ll}$\phi\left(v\right)$&if
$v\in V_{1}^{\prime}$\\\ $v_{2}$&if $v=v_{1}$.\end{tabular}\right.$

We will show that $\phi^{\prime}$ is an isomorphism from $H_{1}+v_{1}$ to
$H_{2}+v_{2}$. Since $\phi$ is an isomorphism from $H_{1}$ to $H_{2}$, it
follows that $ab\in E\left(H_{1}+v_{1}\right)$ and
$\\{a,b\\}\cap\\{v_{1}\\}=\emptyset$ if and only if
$\phi^{\prime}\left(a\right)\phi^{\prime}\left(b\right)\in
E\left(H_{2}+v_{2}\right)$. On the other hand, if $av_{1}\in
E\left(H_{1}+v_{1}\right)$ for all $a\in V_{1}^{\prime}$ and $bv_{2}\in
E\left(H_{2}+v_{2}\right)$ for all $b\in V_{2}^{\prime}$, then
$\phi^{\prime}\left(a\right)\phi^{\prime}\left(v_{1}\right)=\phi\left(a\right)v_{2}\in
E\left(H_{2}+v_{2}\right)$. This implies that $\phi^{\prime}$ is an
isomorphism from $H_{1}+v_{1}$ to $H_{2}+v_{2}$ so that $H_{1}+v_{1}\cong
H_{2}+v_{2}$. ∎

######  Lemma 1.2.

Let $G_{1}=\left(V_{1},E_{1}\right)$ and $G_{2}=\left(V_{2},E_{2}\right)$ be
two graphs. If $v_{1}$ and $v_{2}$ are two new vertices, then $G_{1}\cong
G_{2}$ if and only if $G_{1}\cup v_{1}\cong G_{2}\cup v_{2}$.

###### Proof.

First, assume that $G_{1}\cong G_{2}$. Then there exists an isomorphism
$\phi:V_{1}\rightarrow V_{2}$. Now, consider the function
$\phi^{\prime}:V_{1}\cup\\{v_{1}\\}\rightarrow V_{2}\cup\\{v_{1}\\}$ defined
by

$\phi^{\prime}\left(v\right)=\left\\{\begin{tabular}[]{ll}$\phi\left(v\right)$&if
$v\in V_{1}$\\\ $v_{2}$&if $v=v_{1}$.\end{tabular}\right.$

Since no edge of the form $av_{1}$ exists in $G_{1}\cup v_{1}$ and no edge of
the form $bv_{2}$ exists in $G_{2}\cup v_{2}$, it follows that $\phi^{\prime}$
is an isomorphism from $G_{1}\cup v_{1}$ to $G_{2}\cup v_{2}$ and hence
$G_{1}\cup v_{1}\cong G_{2}\cup v_{2}$.

Next, assume that $G_{1}\cup v_{1}\cong G_{2}\cup v_{2}$. Then there exists an
isomorphism $\phi:V_{1}\rightarrow V_{2}$. Since the image under $\phi$ of any
isolated vertex is an isolated vertex, we may assume, without loss of
generality, that $\phi\left(v_{1}\right)=v_{2}$. This implies that the
function $\phi^{\prime}:V_{1}\rightarrow V_{2}$ defined by
$\phi\left(v\right)=v$ for all $v\in V_{1}$ is clearly well defined, bijective
and an isomorphism from $G_{1}$ to $G_{2}$. Therefore, $G_{1}\cong G_{2}$. ∎

##  2\. Main results

With the information provided in the introduction, we are ready to present our
main results.

Let $S_{0}:0\leqq a_{1}\leqq a_{2}\leqq\cdots\leqq a_{n-1}\leqq a_{n}$ be a
graphical sequence. If we assume that there exist exactly $k$ ($k\geq 1$)
graphs that realize $S_{0}$, then we have the following result.

######  Theorem 2.1.

The sequences

$S_{0}^{\left(1\right)}:1,a_{1}+1,a_{2}+1,\dots,a_{n}+1,n+1;$

$S_{0}^{\left(2\right)}:1,2,a_{1}+2,a_{2}+2,\dots,a_{n}+2,n+2,n+3;$

$S_{0}^{\left(3\right)}:1,2,3,a_{1}+3,a_{2}+3,\dots,a_{n}+3,n+3,n+4,n+5;$

$\vdots$

$S_{0}^{\left(i\right)}:1,2,3,\dots,i,a_{1}+i,a_{2}+i,\dots,a_{n}+i,n+i,n+i+1,\dots,n+2i-1$

$\vdots$

are all graphical. Furthermore, there exist exactly $k$, $k\geq 1$, connected
non-isomorphic graphs that realize each one of the sequences
$S_{0}^{\left(1\right)},S_{0}^{\left(2\right)},\dots,S_{0}^{\left(i\right)},\dots$.

###### Proof.

We start by showing that each sequence $S_{0}^{\left(i\right)}$ is graphical
for any positive integer $i$. To do this, we only need to take a graph that
realizes $S_{0}$, introduce two new vertices and join one of these two new
vertices with all remaining vertices. Hence, $S_{0}^{\left(1\right)}$ is
graphical. To obtain a graph that realizes $S_{0}^{\left(2\right)}$, we just
need to take a graph that realizes $S_{0}^{\left(1\right)}$ and once again
introduce two new vertices joining one of these new two vertices with all
remaining vertices. If we continue this process inductively, we obtain a graph
that realizes $S_{0}^{\left(i\right)}$ for any positive integer $i$.

Now, observe that since each graph realizing $S_{0}^{\left(i\right)}$ ($i\geq
1$) has a vertex which is adjacent to all the other vertices, it follows that
all these graphs are connected. Thus, it remains to show that each one of
these sequences realizes exactly $k$ ($k\geq 1$) graphs. To see this, let
$S_{0}=S_{0}^{\left(0\right)}$ and proceed by induction on the super subscript
$i$ of $S_{0}^{\left(i\right)}$ for $i\geq 0$. First, observe that
$S_{0}^{\left(0\right)}$ has the property that there exist exactly $k$ ($k\geq
1$) non-isomorphic graphs that realizes $S_{0}^{\left(0\right)}$ by
assumption.

Next, let $i=l$ ($l\geq 0)$ and assume that there exist exactly $k$ ($k\geq
1$) non-isomorphic graphs realizing $S_{0}^{\left(l\right)}$. Consider the
sequence

$S_{0}^{\left(l+1\right)}:1,2,\dots,l,l+1,a_{1}+l+1,a_{2}+l+1,\dots,a_{n}+l+1,n+l+1,n+l+2,\dots,n+2l+1\text{.}$

and let $G_{0}^{\left(l+1\right)}$ be any graph that realizes
$S_{0}^{\left(l+1\right)}$. It is now clear that the vertex of degree $n+2l+1$
is adjacent to all other vertices of $V\left(G_{0}^{\left(l+1\right)}\right)$.
It is also true that if we eliminate this vertex, then we obtain a new graph
with degree sequence $0,S_{0}^{\left(l\right)}$. By inductive hypothesis,
there exist exactly $k$ ($k\geq 1$) non-isomorphic graphs with degree sequence
$S_{0}^{\left(l\right)}$. Then Lemma 1.2 yields that there are exactly $k$
($k\geq 1$) non-isomorphic graphs with degree sequence
$0,S_{0}^{\left(l\right)}$, and Lemma 1.1 implies that there are exactly $k$
($k\geq 1$) non-isomorphic graphs realizing $S_{0}^{\left(l+1\right)}$.
Therefore, the result follows. ∎

To conclude this section, notice that it is clear that the only graph that
realizes the sequence $s:1,1$ is the complete graph $K_{2}$ of order $2$. From
this observation together with Theorem 2.1, the next result found in [2]
follows as an immediate corollary.

######  Corollary 2.1.

For all positive integers $n$, there exists a unique graph of order $n$ that
realizes the sequence $S_{n}:1,2,\dots,n/2.n/2,n/2+1,n/2+2,\dots,n-1$.

In summary, what we have proved in this paper is that if a degree sequence is
realized by exactly $k$ ($k\geq 1$) non-isomorphic graphs of order $n$, then
there exist infinitely many sequences that realize exactly $k$ ($k\geq 1$)
non-isomorphic graphs of order $n$ each. Furthermore, all these graphs have
the additional property that they are all connected.

### Acknowledgment

The authors would like to dedicate this paper to Susana Clara López Masip who
passed away on December 26, 2022 after a life dedicated to graph theory.

The authors are also gratefully indebted to Yukio Takahashi for his technical
assistance.

## References

  * [1] Chartrand, G., & Lesniak, L . (1996). Graphs & Digraphs 3th ed. CRC Press, Boca Raton.
  * [2] Ichishima. R., Muntaner-Batle, F. A., & Oshima. A. (2022). Minimum degree conditions for the strength and bandwidth of graphs, Discrete. Appl. Math, 340, 191–198, https://doi.org/10.1016/j.dam.2022.05.005.