# Strong cocomparability graphs and Slash-free orderings of matrices

Pavol Hell, Jing Huang and Jephian C.-H. Lin School of Computing Science,
Simon Fraser University, Burnaby, B.C., Canada V5A 1S6<EMAIL_ADDRESS>of Mathematics and Statistics, University of Victoria, Victoria, B.C., Canada
V8W 2Y2<EMAIL_ADDRESS>of Applied Mathematics, National Sun Yat-sen
University, Kaohsiung 80424, Taiwan<EMAIL_ADDRESS>
(August 27, 2024)

###### Abstract

We introduce the class of strong cocomparability graphs, as the class of
reflexive graphs whose adjacency matrix can be rearranged by a simultaneous
row and column permutation to avoid the submatrix with rows $01,10$, which we
call Slash.

We provide an ordering characterization, a forbidden structure
characterization, and a polynomial-time recognition algorithm, for the class.
These results complete the picture in which in addition to, or instead of, the
$Slash$ matrix one forbids the $\Gamma$ matrix (which has rows $11,10$). It is
well known that in these two cases one obtains the class of interval graphs,
and the class of strongly chordal graphs, respectively.

By complementation, we obtain the class of strong comparability graphs, whose
adjacency matrix can be rearranged by a simultaneous row and column
permutation to avoid the two-by-two identity submatrix. Thus our results give
characterizations and algorithms for this class of irreflexive graphs as well.
In other words, our results may be interpreted as solving the following
problem: given a symmetric $0,1$-matrix with $0$-diagonal, can the rows and
columns of be simultaneously permuted to avoid the two-by-two identity
submatrix?

Key words: Forbidden submatrix, strong cocomparability graph, strong
comparability graph, characterization, vertex ordering, forbidden
substructure, recognition

##  1 Introduction

The problem of deciding whether a given $0,1$-matrix $M$ can have its rows and
columns independently permuted to avoid containing a fixed submatrix $F$ (or a
fixed family $\mathcal{F}$ of such submatrices) has been much studied in the
literature, see for instance [2, 7, 12, 14, 16, 20, 21, 22, 24, 27, 28, 29,
32].

Specifically, we say that a matrix $M$ is $F$-free, or avoids $F$, if it does
not include a copy of $F$ as a submatrix. An $F$-free ordering of a matrix $M$
is an ordering of its rows and an ordering of its columns such that the
resulting permuted matrix is $F$-free. The research mentioned above is
concerned with deciding whether a given $M$ admits an $F$-free ordering. Often
these problems have interesting interpretations for graphs, and especially for
bipartite graphs (i.e., bigraphs). Indeed, any $0,1$-matrix is associated with
a bigraph as follows. The biadjacency matrix of a bigraph $G$ with parts $I,J$
is a $0,1,$-matrix $M$ whose rows are indexed by vertices of $I$ and columns
by vertices of $J$ and $M(i,j)=1$ if and only if $i\in I$ is adjacent to $j\in
J$.

In the most widely known special case the matrix $F$ is the so-called $\Gamma$
matrix $\left[\begin{matrix}1&1\\\ 1&0\end{matrix}\right]$. It is known that a
matrix $M$ admits a $\Gamma$-free ordering if and only if it is totally
balanced (i.e., does not contain a cycle submatrix) [1, 22, 28]), and
efficient algorithms are known to determine whether or not this is the case
[28, 29]. Totally balanced matrices have important applications in location
theory [22]. They also have a natural graph interpretation. We say that a
bigraph is chordal if it does not contain an induced cycle of length at least
six.

######  Theorem 1.

[1, 19, 28] A matrix admits a $\Gamma$-free ordering if and only if it is the
biadjacency matrix of a chordal bigraph. ∎

This gives a forbidden structure characterization (in terms of the induced
cycles of length at least six in the associated bigraph) of matrices that
admit a $\Gamma$-free ordering.

We next review the situation when $F$ is the so-called Slash matrix
$\left[\begin{matrix}0&1\\\ 1&0\end{matrix}\right]$.

This matrix turns out to be important from the graph theoretic point of view,
but we also point out that exchanging $0$’s and $1$’s translates this problem
into one seeking $I_{2}$-free orderings, where $I_{2}$ is the two-by-two
identity matrix. This problem has attracted attention in the Russian
literature because it yields efficiently solvable cases of a certain plant
location problem [24]. It is known that $M$ admits an $I_{2}$-free ordering if
and only if it is connected (i.e., the sequence of differences between the
corresponding entries of any two rows changes sign at most once), and
efficient recognition algorithms have been reported in the Russian sources
[2].

For the $Slash$ matrix, we have the following graph-theoretic interpretation.
An edge-asteroid is a set of edges $x_{0}y_{0},x_{1}y_{1},\dots,x_{2k}y_{2k}$
such that for each $i=0,1,\dots,2k$, there is a walk that begins with the edge
$x_{i+k}y_{i+k}$ and ends with the edge $x_{i+k+1}y_{i+k+1}$ such that neither
$x_{i}$ nor $y_{i}$ is adjacent to a vertex in the walk. We call a bigraph a
cocomparability bigraph if it contains no edge-asteroid [14]. This is
motivated by an analogous definition and result of Gallai [10], stating that a
graph is a comparability graph – i.e., admits a transitive orientation – if
and only if its complement contains no asteroid. Here an asteroid is a vertex-
focused analogue of an edge-asteroid.; see [14] for details.

######  Theorem 2.

[14] A matrix admits a $Slash$-free ordering if and only if it is the
biadjacency matrix of a cocomparability bigraph. ∎

This result also gives a forbidden structure characterization of matrices that
admit a $Slash$-free ordering (in terms of the edge-asteroids of the
associated bigraph). It implies a robust polynomial-time recognition
algorithm, which can also be applied to recognizing matrices that admit
$I_{2}$-free orderings. The need for such algorithms is discussed in [31],
Section 10.3.

Finally, we review the situation for the family
$\mathcal{F}=\\{\Gamma,Slash\\}$, i.e., when both $\Gamma$ and $Slash$ are
forbidden. (When the order of rows is reversed, the resulting two matrices
form a subset of $0,1$-Monge matrices, as discussed in [24], Sections 2.7 and
4.3.) There are several equivalent descriptions of the class of matrices
admitting $\mathcal{F}$-free orderings, in terms of bigraphs: as complements
or circular arc graphs [7], as two-dimensional orthogonal ray graphs [30], or
as interval containment bigraphs [15, 20, 21], cf. also [16]. We may state the
theorem using already defined terms as follows [7, 20].

######  Theorem 3.

[15, 21] A matrix admits a $(\Gamma,Slash)$-free ordering if and only if it is
the biadjacency matrix of a chordal bigraph without edge-asteroids. ∎

Other results give polynomial-time algorithms and characterizations in terms
of bigraphs when similar sets of $2\times 2$ matrices are forbidden [24, 32].

All the results summarized above, translate to facts about classes of
bigraphs. There is a more natural matrix candidate as far as correspondence to
graphs is concerned, namely instead of the biadjacency matrix one can consider
the usual adjacency matrix of an arbitrary graph. This is the focus of our
paper.

For technical reasons, we need to deal with reflexive graphs (graphs in which
ever vertex has a loop). In matrix terms, this means we have a symmetric
$0,1$-matrix with $1$’s on the main diagonal. In the literature this is often
presented without considering loops, but instead of the usual adjacency matrix
one takes the augmented adjacency matrix, which is just the usual adjacency
matrix augmented with $1$’s on the main diagonal. Note that re-ordering the
vertices of a graph corresponds to a simultaneous row and column permutation
of its adjacency matrix.

It is also possible, of course, to consider an arbitrary square matrix to be
the adjacency matrix of a digraph, and ask similar questions about avoiding
given submatrices for simultaneous row and column permutations, see for
instance [13]. However, in this paper we focus purely on undirected graphs.

Thus from now on $M$ is a square symmetric $0,1$-matrix with $1$’s on the main
diagonal. We now examine the situation for the same matrices $\Gamma$ and
$Slash$.

A symmetric ordering of a symmetric matrix $M$ is a matrix obtained from $M$
by simultaneously permuting the rows and columns of $M$. Clearly, a symmetric
ordering of a symmetric matrix is again symmetric.

We first describe the situation when the $\Gamma$ matrix is forbidden.

A trampoline is a complete graph on $k$ vertices $u_{1},u_{2},\dots,u_{k}$
with $k\geq 3$, together with an independent set of $k$ vertices
$v_{1},v_{2},\dots,v_{k}$ such that each $v_{i}$ is adjacent to $u_{i}$ and
$u_{i+1}$ (and to no other vertices). A graph is strongly chordal if it does
not contain, as an induced subgraph, a cycle of length $\geq 4$ or a
trampoline [5].

######  Theorem 4.

[5] A matrix admits a symmetric $\Gamma$-free ordering if and only if it is
the adjacency matrix of a strongly chordal graph. ∎

This result provides a graph description of the class of matrices, but also a
forbidden structure characterization, and a polynomial-time recognition
algorithm.

For the family $\mathcal{F}=\\{\Gamma,Slash\\}$, the symmetric matrices that
admit a $\mathcal{F}$-free ordering also have an elegant graph description,
which results in a well-known forbidden structure characterization and
polynomial-time recognition.

A graph $G$ is an interval graph if there is a family of intervals $I_{v},v\in
V(G)$ such that for all $u,v\in V(G)$, $uv\in E(G)$ if and only if $I_{u}\cap
I_{v}\neq\emptyset$.

######  Theorem 5.

[8, 15] A matrix admits a symmetric $(\Gamma,Slash)$-free ordering if and only
if it is the adjacency matrix of an interval graph. ∎

The purpose of our paper is to complete the picture by introducing the “last
piece of the puzzle”, that is, the class of reflexive graphs whose adjacency
matrices have symmetric $Slash$-free orderings. We call such graphs strong
cocomparability graphs. We provide a natural ordering characterization of
strong cocomparability graphs, as well as a characterization by forbidden
substructures that is analogous to similar characterizations of interval
graphs and other graph and digraph classes. This latter characterization
implies a polynomial-time algorithm for the recognition of strong
cocomparability graphs.

We apply our results to prove that the class of interval graphs is the
intersection of the classes of strongly chordal graphs and strong
cocomparability graphs, enhancing a well known theorem of Gilmore and Hoffman
[11].

These results can be applied by complementation to the class of strong
comparability graphs, which correspond to adjacency matrices that have a
symmetric $I_{2}$-free ordering. We ask if the domination problem, NP-complete
for comparability graphs, can be solved in polynomial time for strong
comparability graphs, in analogy to the situation for chordal versus strongly
chordal graphs.

Unfortunately, we do not have a forbidden subgraph characterization of strong
cocomparability graphs, although such characterizations are known for interval
graphs, cocomparability graphs, chordal graphs, and strongly chordal graphs.
We do, however, provide a simple description of the class of bipartite strong
cocomparability graphs, and relate it to the class of cocomparability bigraphs
and to the class of bipartite permutation graphs.

##  2 Symmetric $Slash$-free orderings

Let $\prec$ be a vertex ordering of a reflexive graph $G$ and $M$ be the
adjacency matrix of $G$ whose rows and columns are ordered according to
$\prec$. Then $M$ contains the $Slash$ matrix as a submatrix if and only if
$\prec$ contains, as ordered induced subgraphs, a pattern in Figure 1. This
can be easily seen by considering the possible relative positions of the row
numbers and the column numbers of the occurrence of $Slash$.

Figure 1: Forbidden patterns for strong cocomparability orderings.

Thus we have the following ordering characterization of strong cocomparability
graphs.

######  Proposition 6.

A reflexive graph is a strong cocomparability graph if and only if it admits a
vertex ordering that does not contain any of the four patterns in Figure 1. ∎

We call such a vertex ordering of $G$ a strong cocomparability ordering. It
follows by comparison with the cocomparability ordering mentioned in [4] that
a strong cocomparability graph is also a cocomparability graph.

We now proceed to give a structural characterization of strong cocomparability
graphs. Our result parallels other structural characterizations of various
classes of graphs and digraphs [3, 8, 9, 16, 17, 18], as it is given in terms
of absence of so-called invertible pairs, defined below. We point out that,
for example, interval graphs have a very similar structural characterization
[8]. To prove that the absence of invertible pairs implies the existence of a
strong cocomparability ordering, we use the method of “complementary circuits”
pioneered in [8], and also used in [3, 17, 18].

In particular, our characterization will imply a polynomial-time recognition
algorithm.

We first introduce a useful “forcing” relation $\Lambda$.

Let $G$ be a reflexive graph with vertex $V(G)$ and edge set $E(G)$. Note that
$E(G)$ includes all loops $vv$, $v\in V(G)$. Denote by $Z(G)$ the set of
ordered pairs $(u,v)$ of distinct vertices of $G$. For
$(u,v),(u^{\prime},v^{\prime})\in Z(G)$, we say that $(u,v)$ forces
$(u^{\prime},v^{\prime})$, denoted by $(u,v)\Lambda(u^{\prime},v^{\prime})$,
if $u=u^{\prime}$ and $v=v^{\prime}$ or $uu^{\prime},vv^{\prime}\in E(G)$ and
$uv^{\prime},vu^{\prime}\notin E(G)$. Clearly,
$(u,v)\Lambda(u^{\prime},v^{\prime})$ if and only if
$(v,u)\Lambda(v^{\prime},u^{\prime})$. We also say that $(u,v)$ implies
$(u^{\prime},v^{\prime})$, denoted by $(u,v)\sim(u^{\prime},v^{\prime})$, if
there exist walks $u_{1}u_{2}\dots u_{k}$ and $v_{1}v_{2}\dots v_{k}$ in $G$
where $(u_{1},v_{1})=(u,v)$ and $(u_{k},v_{k})=(u^{\prime},v^{\prime})$ such
that $(u_{i},v_{i})\Lambda(u_{i+1},v_{i+1})$ for each $i=1,2,\dots,k-1$. It is
easy to verify that $\sim$ is an equivalence relation on $Z(G)$. An
equivalence class of $\sim$ will be called an implication class. We shall use
$[(u,v)]$ to denote the implication class of $(u,v)$ and call $[(u,v)]$ non-
trivial if $(u,v)$ is not the only pair in $[(u,v)]$.

The next proposition follows immediately from the definitions of strong
cocomparability orderings and the relation $\Lambda$.

######  Proposition 7.

Let $G$ be a reflexive graph. Then the following statements hold.

  1. 1.

If $abc$ is an induced $P_{3}$ in $\overline{G}$, then $(a,b)\Lambda(c,b)$.

  2. 2.

If $abcd$ is an induced $P_{4}$ in $G$, then
$(a,c)\Lambda(a,d)\Lambda(b,d)\Lambda(a,d)\Lambda(b,c)$.

  3. 3.

If $abcd$ is an induced $C_{4}$ in $G$, then $(a,d)\Lambda(b,c)$. ∎

Each vertex ordering $\prec$ of $G$ gives rise to the set $\\{(u,v):\ u\prec
v\\}$ which we denote by $U_{\prec}$. The set $U_{\prec}$ contains either
$(u,v)$ or $(v,u)$ for all distinct vertices $u,v$ of $G$. Suppose that
$\prec$ is a strong cocomparability ordering. Then for all
$(u,v)\Lambda(u^{\prime},v^{\prime})$, $U_{\prec}$ either contains both
$(u,v)$ and $(u^{\prime},v^{\prime})$ or both $(v,u)$ and
$(v^{\prime},u^{\prime})$. Hence $U_{\prec}$ contains either $[(u,v)]$ or
$[(v,u)]$ for all distinct vertices $u,v$ of $G$ and in particular, it is a
union of implication classes. Conversely, if $U_{\prec}$ is a union of
implication classes then $\prec$ is a strong cocomparability ordering of $G$.

######  Proposition 8.

Let $\prec$ be a vertex ordering of a reflexive graph $G$ and let
$U_{\prec}=\\{(u,v)\in Z(G):\ u\prec v\\}$. The following statements are
equivalent:

  1. 1.

$\prec$ is a strong cocomparability ordering;

  2. 2.

for all $(u,v)\sim(u^{\prime},v^{\prime})$, $u\prec v$ if and only if
$u^{\prime}\prec v^{\prime}$;

  3. 3.

$U_{\prec}$ is a union of implication classes. ∎

An invertible pair in $G$ is a pair of distinct vertices $u,v$ such that
$(u,v)\sim(v,u)$. Clearly, if $u,v$ are an invertible pair then
$[(u,v)]=[(v,u)]$ and for any $(x,y)\in[(u,v)]$, $x,y$ are an invertible pair.
Invertible pairs are absent in a strong cocomparability graph.

######  Proposition 9.

A strong cocomparability graph cannot contain an invertible pair.

Proof: If $G$ is a strong cocomparability graph which contains an invertible
pair $u,v$, then by Proposition 8 any strong cocomparability ordering $\prec$
of $G$ would have $u\prec v$ and $v\prec u$, a contradiction. ∎

An invertible pair in a reflexive graph $G$ (if exists) can be easily
discovered via an auxiliary graph of $G$ defined next.

Define the auxiliary graph $G^{+}$ of reflexive graph $G$ as follows. The
vertex set of $G^{+}$ is the set $Z(G)$. Two vertices $(u,v)$ and
$(v^{\prime},u^{\prime})$ are adjacent in $G^{+}$ if and only if
$(u,v)\Lambda(u^{\prime},v^{\prime})$, that is, $u=u^{\prime}$ and
$v=v^{\prime}$, or $uu^{\prime},vv^{\prime}\in E(G)$ and
$uv^{\prime},vu^{\prime}\notin E(G)$.

######  Proposition 10.

A reflexive graph $G$ has an invertible pair if and only if its auxiliary
graph $G^{+}$ is not bipartite.

Proof: Suppose that $u_{1},v_{1}$ are an invertible pair in $G$. Then there
exist walks $u_{1}u_{2}\dots u_{k-1}u_{k}$ and $v_{1}v_{2}\dots v_{k-1}v_{k}$
where $u_{k}=v_{1}$ and $v_{k}=u_{1}$ such that
$(u_{i},v_{i})\Lambda(u_{i+1},v_{i+1})$ for each $i=1,2,\dots,k-1$. Hence

$(u_{1},v_{1})(v_{1},u_{1})(u_{2},v_{2})(v_{2},u_{2})\cdots(u_{k-1},v_{k-1})(v_{k-1},u_{k-1})(u_{k},v_{k})$

is a closed walk of odd length in $G^{+}$, showing that $G^{+}$ is not
bipartite.

Conversely, suppose that $G^{+}$ is not bipartite. Let
$(u_{1},v_{1})(u_{2},v_{2})\cdots(u_{2k+1},v_{2k+1})$ be a cycle of odd length
in $G^{+}$. Then

$(u_{1},v_{1})\Lambda(u_{3},v_{3})\Lambda\cdots\Lambda(u_{2k+1},v_{2k+1})\Lambda(v_{1},u_{1})$

showing that $u_{1},v_{1}$ are an invertible pair in $G$. ∎

In the next section we prove that the absence of invertible pairs in a
reflexive graph in fact ensures that the graph is a strong cocomparability
graph.

##  3 The main result

Let $G$ be a reflexive graph. For each implication class $I$ of $G$, denote by
$I^{-1}$ the inverse class of $I$, that is,

$I^{-1}=\\{(u,v):\ (v,u)\in I\\}.$

A circuit of length $\ell$ is a sequence of pairs

$(u_{1},u_{2}),(u_{2},u_{3}),\dots,(u_{\ell-1},u_{\ell}),(u_{\ell},u_{1}).$

Note that if $G$ has no invertible pair then, for any implication class $I$ of
$G$, $I\cap I^{-1}=\emptyset$. Also note that having an invertible pair is
equivalent to having a circuit of length two, and hence if $G$ has no
invertible pair then, for any implication class $I$ of $G$ neither $I$ nor
$I^{-1}$ contains a circuit of length two.

######  Theorem 11.

If a reflexive graph $G$ does not contain an invertible pair, then it is a
strong cocomparability graph.

Before proving the theorem, we give an overview of the proof. To show that $G$
is a strong cocomparability graph we prove that it has a strong
cocomparability ordering $\prec$ by constructing the set $U_{\prec}$. The set
$U_{\prec}$ is constructed by adding for each implication class $I$ either $I$
or $I^{-1}$. A necessary property for $U_{\prec}$ to have is that it does not
contain a circuit. We will show that it is always possible to add either $I$
or $I^{-1}$ for each implication class $I$ without creating a circuit. For the
sake of contradiction, suppose that circuits are created for the first time
when adding an implication class $I$ or its inverse $I^{-1}$. By considering a
shortest circuit and two cases depending on the implication classes of the
pairs in the circuit we will show that the circuit has either one or two pairs
from the newly added implication class. This will allow us to deduce that a
circuit already exists even before adding either of $I$ and $I^{-1}$, which is
a contradiction.

Proof: Suppose that $G$ contains no invertible pair. In view of Proposition 8,
it suffices to show that there exists a set $U$ of pairs of distinct vertices
of $G$ which satisfies the following two properties:

  * •

$U$ contains either $I$ or $I^{-1}$ for all implication classes $I$;

  * •

$U$ contains no circuit.

In fact, we will show such a set $U$ can be constructed by adding implication
classes one at a time, in no particular order except priority will be given to
non-trivial implication classes. Initially, $U=\emptyset$. At each step, we
consider an implication $I$ and its inverse class $I^{-1}$, no pairs of which
have been added to $U$. We will add all pairs of $I$ to $U$ (that is, replace
$U$ by $U\cup I$) if $U\cup I$ contains no circuit, otherwise we add all pairs
of $I^{-1}$ to $U$. It remains to show that if $U$ does not contain a circuit,
then at least one of $U\cup I$ and $U\cup I^{-1}$ does not contain a circuit.

Suppose that $U\cup I$ contains circuits. Let $C$ be a shortest circuit
contained in $U\cup I$. Suppose that $I$ is trivial, i.e., $I=\\{(u,v)\\}$ for
some pair $(u,v)$. Since there is no circuit in $U$, $(u,v)$ is in $C$. Since
$C$ is a shortest circuit in $U\cup I$, $(u,v)$ occurs exactly once in $C$.
Similarly, if $U\cup I^{-1}$ also contains a circuit, then it has a circuit
$C^{\prime}$ in which $(v,u)$ occurs exactly once in $C^{\prime}$. Hence
$(C\cup C^{\prime})\setminus\\{(u,v),(v,u)\\}$ is a circuit in $U$,
contradicting the assumption that $U$ has no circuit. Hence $I$ is non-
trivial. This implies that, prior to considering $I$ and $I^{-1}$, no pair in
$U$ forms an trivial implication class. It follows that for each $(u,v)\in
U\cup I$ there exists a pair $(u^{\prime},v^{\prime})\in U\cup I$ such that
$(u^{\prime},v^{\prime})\neq(u,v)$ and $(u^{\prime},v^{\prime})\Lambda(u,v)$;
in particular, $u^{\prime}$ is adjacent to $u$ but not to $v$ and $v^{\prime}$
is adjacent to $v$ but not to $u$.

Denote $C:\ (x_{1},x_{2}),(x_{2},x_{3}),\dots,(x_{a-1},x_{a}),(x_{a},x_{1})$.
Note that $a\geq 3$ because $G$ contains no invertible pair. Since $C$ is a
shortest circuit in $U\cup I$, for all $i,j\in\\{1,2,\dots,a\\}$,
$(x_{i},x_{j})\in U\cup I$ if and only if $j=i+1$ (here and in the rest of
proof the subscripts of $x$’s are taken modulo $a$). This implies in
particular that the pairs on $C$ are pairwise distinct. We know from the above
that for each $i$ there is a vertex adjacent to $x_{i}$ but not to $x_{i-1}$
and there is also a vertex adjacent to $x_{i}$ but not to $x_{i+1}$. Below we
distinguish two cases depending on whether such vertices can be chosen to be
the same one for some $i$.

Case 1. For some $i$, there is a vertex adjacent to $x_{i}$ but not to either
of $x_{i-1}$ and $x_{i+1}$. By symmetry we may assume that $i=1$ and
$x^{\prime}_{1}$ is such a vertex (i.e., adjacent to $x_{1}$ but not to
$x_{a}$ or $x_{2}$).

Claim 1.1. For each $i=2,\dots,a$, let $x^{\prime}_{i}$ be a vertex adjacent
to $x_{i}$ but not to $x_{i-1}$. Let $z^{\prime}$ be a vertex adjacent to
$x_{a}$ but not to $x_{1}$. Then, for each $i=1,2,\dots,a$, $x^{\prime}_{i}$
is not adjacent to any of $x_{a},x_{1},\dots,x_{i-1}$ and $x_{i}$ is not
adjacent to any of
$z^{\prime},x^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{i-1}$ for each
$i=1,2,\dots,a$, except when $i=a$ in which case $x_{a}$ is adjacent both
$x^{\prime}_{a}$ and $z^{\prime}$ by definition. Moreover,

$C^{\prime}:\
(x^{\prime}_{1},x^{\prime}_{2}),(x^{\prime}_{2},x^{\prime}_{3}),\dots,(x^{\prime}_{a-1},x^{\prime}_{a}),(x^{\prime}_{a},x^{\prime}_{1})$

is a shortest circuit in $U\cup I$.

Proof of Claim 1.1. The statement is clearly true for $i=1$. By definition
$x^{\prime}_{2}$ is not adjacent to $x_{1}$ and by assumption $x_{2}$ is not
adjacent to $x^{\prime}_{1}$. If $x^{\prime}_{2}$ is adjacent to $x_{a}$ then
$(x_{1},x_{2})\Lambda(x^{\prime}_{1},x^{\prime}_{2})\Lambda(x_{1},x_{a})$,
which implies $(x_{1},x_{a})\in U\cup I$, a contradiction to the observation
above. So $x^{\prime}_{2}$ is not adjacent to $x_{a}$. If $x_{2}$ is adjacent
to $z^{\prime}$ then
$(x_{1},x_{2})\Lambda(x^{\prime}_{1},z^{\prime})\Lambda(x_{1},x_{a})$, a
contradiction to the observation above. So $x_{2}$ is not adjacent to
$z^{\prime}$. Hence the statement is also true for $i=2$. Assume that $2\leq
k<a$ and the statement is true for $i=1,2,\dots,k$. Suppose that $x_{k+1}$ is
adjacent to $x^{\prime}_{k}$. The vertex $x_{k+1}$ must be adjacent to
$x^{\prime}_{k-1}$ as otherwise
$(x_{k-1},x_{k})\Lambda(x^{\prime}_{k-1},x^{\prime}_{k})\Lambda(x_{k-1},x_{k+1})$,
which implies $(x_{k-1},x_{k+1})\in U\cup I$, a contradiction. Similarly,
$x_{k+1}$ must be adjacent to $x^{\prime}_{k-2}$ as otherwise
$(x_{k-2},x_{k-1})\Lambda(x^{\prime}_{k-2},x^{\prime}_{k-1})\Lambda(x_{k-2},x_{k+1})$,
which implies $(x_{k-2},x_{k+1})\in U\cup I$, a contradiction. Continuing this
way we have that $x_{k+1}$ is adjacent to all of
$z^{\prime},x^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{k}$. Let
$x^{\prime}$ be a vertex adjacent to $x_{k}$ but not to $x_{k+1}$. We know
from above such a vertex $x^{\prime}$ exists. Then $x^{\prime}$ must be
adjacent to $x_{k-1}$ as otherwise
$(x_{k-1},x_{k})\Lambda(x^{\prime}_{k-1},x^{\prime})\Lambda(x_{k+1},x_{k})$,
which implies $(x_{k+1},x_{k})\in U\cup I$, a contradiction. Similarly,
$x^{\prime}$ must be adjacent to $x_{k-2}$ as otherwise
$(x_{k-2},x_{k-1})\Lambda(x^{\prime}_{k-2},x^{\prime})\Lambda(x_{k+1},x_{k-1})$,
which implies $(x_{k+1},x_{k-1})\in U\cup I$, a contradiction. Continuing this
way we have $x^{\prime}$ is adjacent to all of
$x_{a},x_{1},x_{2},\dots,x_{k}$. But then
$(x_{k},x_{k+1})\Lambda(x^{\prime},z^{\prime})\Lambda(x_{1},x_{k+1})$, which
implies $(x_{1},x_{k+1})\in U\cup I$, a contradiction. Hence $x_{k+1}$ is not
adjacent to $x^{\prime}_{k}$. It cannot be adjacent to $x^{\prime}_{k-1}$ as
otherwise
$(x_{k},x_{k-1})\Lambda(x^{\prime}_{k},x^{\prime}_{k-1})\Lambda(x_{k},x_{k-1})$,
which implies $(x_{k},x_{k-1})\in U\cup I$, a contradiction. Similarly, it
cannot be adjacent to $x^{\prime}_{k-2}$ as otherwise
$(x_{k},x_{k+1})\Lambda(x^{\prime}_{k},x^{\prime}_{k-2})\Lambda(x_{k},x_{k-2})$,
which implies $(x_{k},x_{k-2})\in U\cup I$, a contradiction. Continuing this
way we have that $x_{k+1}$ is not adjacent to any of
$z^{\prime},x^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{k}$, except when
$k+1=a$ in which case $x_{a}$ is by definition adjacent to $z^{\prime}$.

If $x^{\prime}_{k+1}$ is adjacent to $x_{k-1}$, then
$(x_{k-1},x_{k})\Lambda(x^{\prime}_{k+1},x^{\prime}_{k})\Lambda(x_{k+1},x_{k})$,
implying $(x_{k+1},x_{k})\in U\cup I$, a contradiction. So $x^{\prime}_{k+1}$
is not adjacent to $x_{k-1}$. If $x^{\prime}_{k+1}$ is adjacent to $x_{k-2}$,
then
$(x_{k-2},x_{k-1})\Lambda(x^{\prime}_{k+1},x^{\prime}_{k-1})\Lambda(x_{k+1},x_{k-1})$,
which implies $(x_{k+1},x_{k-1})\in U\cup I$, a contradiction. So
$x^{\prime}_{k+1}$ is not adjacent to $x_{k-2}$. Continuing this way we see
that $x^{\prime}_{k+1}$ is not adjacent to any of $x_{a},x_{1},\dots,x_{k}$,
except when $k+1=a$ in which case $x^{\prime}_{a}$ is by definition adjacent
to $x_{a}$.

Since $x_{i}$ is adjacent to $x^{\prime}_{i}$ but not to $x^{\prime}_{i+1}$
and $x_{i+1}$ is adjacent to $x^{\prime}_{i+1}$ but not to $x^{\prime}_{i}$,
$(x_{i},x_{i+1})\Lambda(x^{\prime}_{i},x^{\prime}_{i+1})$ for each
$i=1,2,\dots,a$. Therefore $C^{\prime}$ is a circuit in $U\cup I$. Since
$C^{\prime}$ has the same length as $C$, it is a shortest circuit in $U\cup
I$. ∎

It follows from Claim 1.1 that the edges $x_{i}x^{\prime}_{i}$ form an
independent set of edges in $G$, that is, $x_{i}$ is not adjacent to
$x^{\prime}_{j}$ for all $i\neq j$.

Claim 1.2. For any vertex $x^{\prime}$ that is adjacent to $x_{i}$ but not to
$x_{i+1}$, $x^{\prime}$ is not adjacent to any of
$x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{a}$. Moreover,

$(x^{\prime}_{1},x^{\prime}_{2}),\dots,(x^{\prime}_{i-2},x^{\prime}_{i-1}),(x^{\prime}_{i-1},x^{\prime}),(x^{\prime},x_{i+1}),\dots,(x^{\prime}_{a-1},x^{\prime}_{a}),(x^{\prime}_{a},x^{\prime}_{1})$

is a shortest circuit in $U\cup I$.

Proof of Claim 1.2. If $x^{\prime}$ is adjacent to $x_{i-1}$, then
$(x_{i},x_{i+1})\Lambda(x^{\prime},x^{\prime}_{i+1})\Lambda(x_{i-1},x_{i+1})$,
which implies $(x_{i-1},x_{i+1})\in U\cup I$, a contradiction. So $x^{\prime}$
is adjacent to $x_{i}$ but not to $x_{i-1}$ or $x_{i+1}$. By Claim 1.1,
$x^{\prime}$ is not adjacent to any of
$x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{a}$. Since
$(x_{i-1},x_{i})\Lambda(x^{\prime}_{i-1},x^{\prime})$,
$(x_{i},x_{i+1})\Lambda(x^{\prime},x^{\prime}_{i+1})$ and
$(x_{j},x_{j+1})\Lambda(x^{\prime}_{j},x^{\prime}_{j+1})$ for all $j\neq i-1$
or $i$,
$(x^{\prime}_{1},x^{\prime}_{2}),\dots,(x^{\prime}_{i-2},x^{\prime}_{i-1}),(x^{\prime}_{i-1},x^{\prime}),(x^{\prime},x_{i+1}),\dots,(x^{\prime}_{a-1},x^{\prime}_{a}),(x^{\prime}_{a},x^{\prime}_{1})$
is a shortest circuit in $U\cup I$.. ∎

Claim 1.3. For any vertex $x$ that is adjacent to $x^{\prime}_{i}$ but not to
$x^{\prime}_{i+1}$, $x$ is not adjacent to any of
$x^{\prime}_{1},\dots,x^{\prime}_{i-1},x^{\prime}_{i+1},\dots,x^{\prime}_{a}$.
Moreover,

$(x_{1},x_{2}),\dots,(x_{i-2},x_{i-1}),(x_{i-1},x),(x,x_{i+1}),\dots,(x_{a-1},x_{a}),(x_{a},x_{1})$

is a shortest circuit in $U\cup I$.

Proof of Claim 1.3. The proof is the same as for Claim 1.2 when the roles of
$x_{i}$ and $x^{\prime}_{i}$ are switched for each $i$. ∎

Claim 1.4. The circuit $C$ contains a unique pair from $I$.

Proof of Claim 1.4. Since $U$ contains no circuit, there is at least one pair
on $C$ which is from $I$. Without loss of generality assume $(x_{a},x_{1})\in
I$. Suppose that $(x_{j},x_{j+1})\in I$ for some $j\neq a$. Then there is a
sequence

$(u_{1},v_{1})\Lambda(u_{2},v_{2})\Lambda\cdots\Lambda(u_{k},v_{k})$

of pairs in $I$ such that $(u_{1},v_{1})=(x_{a},x_{1})$ and
$(u_{k},v_{k})=(x_{j},x_{j+1})$. Moreover, we assume that
$(u_{i},v_{i})\neq(u_{i+1},v_{i+1})$ for each $i$. This guarantees that
$u_{i+1}$ is adjacent to $u_{i}$ but not to $v_{i}$ and $v_{i+1}$ is adjacent
to $v_{i}$ but not to $u_{i}$. It follows from Claims 1.3 and 1.4, for each
even $i$ with $1\leq i\leq k$,
$(u_{i},v_{i}),(v_{i},x^{\prime}_{2}),(x^{\prime}_{2},x^{\prime}_{3}),\dots,(x^{\prime}_{a-2},x^{\prime}_{a-1}),(x^{\prime}_{a-1},u_{i})$
is a shortest circuit in $U\cup I$. Moreover, $u_{i}$ is not adjacent to any
of $x_{1},x_{2},\dots,x_{a-1}$. In particular, when $k$ is even, $u_{k}$ is
not adjacent to $x_{j}=u_{k}$, which is a contradiction. So $k$ is odd. By
Claims 1.3 and 1.4,
$(u_{k},v_{k}),(v_{k},x_{2}),(x_{2},x_{3}),\dots,(x_{a-2},x_{a-1}),(x_{a-1},u_{k})$
is a shortest circuit in $U\cup I$. This is a contradiction because
$u_{k}=x_{j}$ and
$(u_{k},v_{k}),(v_{k},x_{2}),(x_{2},x_{3}),\dots,(x_{j-1},x_{j})$ is a shorter
circuit in $U\cup I$. ∎

Claim 1.5. For each pair $(u,v)\in I$, $U\cup I$ contains a circuit in which
$(u,v)$ is the only pair from $I$.

Proof of Claim 1.5. By Claim 1.4, we may again assume that $(x_{a},x_{1})$ is
the only pair in $C$ that is from $I$. Since $(x_{a},x_{1})$ and $(u,v)$ are
both from $I$, there is a sequence

$(u_{1},v_{1})\Lambda(u_{2},v_{2})\Lambda\cdots\Lambda(u_{k},v_{k})$

of pairs in $I$ such that $(u_{1},v_{1})=(x_{a},x_{1})$,
$(u_{k},v_{k})=(u,v)$, and $(u_{i},v_{i})\neq(u_{i+1},v_{i+1})$ for each $i$.
The proof of Claim 1.4 also shows that if $k$ is even then substituting
$(u,v)$ for the pair $(x^{\prime}_{a},x^{\prime}_{1})$ in $C^{\prime}$ we
obtain a circuit in which $(u,v)$ is the only pair from $I$. Similarly, if $k$
is odd then substituting $(u,v)$ for the pair $(x_{a},x_{1})$ in $C$ we obtain
a circuit in which $(u,v)$ is the only pair from $I$. ∎

Case 2. For each $i$, any vertex adjacent to $x_{i}$ must be adjacent to at
least one of $x_{i-1}$ and $x_{i+1}$.

Claim 2.1. For each $i=1,2,\dots,a$, let $x^{\prime}_{i}$ be a vertex adjacent
to $x_{i}$ but not to $x_{i-1}$ and $x^{\prime\prime}_{i}$ be a vertex
adjacent to $x_{i}$ but not to $x_{i+1}$. Then

  * •

$x^{\prime}_{i}$ is adjacent to all of $x_{a},x_{1},x_{2},\dots,x_{i-2}$,
except when $i=1$ in which case it is not adjacent to $x_{a}$.

  * •

$x^{\prime\prime}_{i}$ is adjacent to all of $x_{a},x_{1},\dots,x_{i}$, except
when $i=a-1$ in which case it is not adjacent to $x_{a}$ and when $i=a$ in
which case it is not adjacent to $x_{1}$.

  * •

$x_{i}$ is adjacent to all of
$x^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{i-1},x^{\prime\prime}_{a},x^{\prime\prime}_{1},x^{\prime\prime}_{2},\dots,x^{\prime\prime}_{i-2}$,
except when $i=1$ in which case it is not adjacent to $x^{\prime}_{2}$ or
$x^{\prime\prime}_{a}$.

Proof of Claim 2.1. By definition, $x^{\prime}_{1}$ is not adjacent to $x_{a}$
and $x_{1}$ is not adjacent to $x^{\prime}_{2}$ or $x^{\prime\prime}_{a}$. The
vertex $x^{\prime\prime}_{1}$ is adjacent to $x_{1}$ but not to $x_{2}$ so it
is adjacent to $x_{a}$ by assumption. Thus the statement holds for $i=1$. The
vertex $x^{\prime}_{2}$ must be adjacent to $x_{a}$ as otherwise
$(x_{1},x_{2})\Lambda(x^{\prime\prime}_{1},x^{\prime}_{2})\Lambda(x_{a},x_{2})$,
which implies $(x_{a},x_{2})\in U\cup I$, a contradiction to the choice of
$C$. By assumption $x_{2}$ is adjacent to $x^{\prime}_{1}$. If $x_{2}$ is not
adjacent to $x^{\prime\prime}_{a}$ then
$(x_{a},x_{1})\Lambda(x^{\prime\prime}_{a},x^{\prime}_{1})\Lambda(x_{a},x_{2})$,
a contradiction. So $x_{2}$ is adjacent to both $x^{\prime}_{1}$ and
$x^{\prime\prime}_{a}$. Note that $x^{\prime}_{2}$ is adjacent to $x_{2}$ but
not to $x_{1}$ so it must be adjacent to $x_{3}$ by assumption. Now consider
$x^{\prime\prime}_{2}$. It is adjacent to $x_{2}$ by definition. It must be
adjacent to $x_{a}$ as otherwise
$(x_{a},x_{1})\Lambda(x^{\prime}_{2},x^{\prime\prime}_{2})\Lambda(x_{3},x_{1})$,
a contradiction. Hence the statement holds also for $i=2$. Assume that $k\geq
2$ and the statement holds for each $i=1,2,\dots,k$. We show that it holds for
$i=k+1$. Consider first the vertex $x^{\prime}_{k+1}$. It must be adjacent to
$x_{k-1}$ as otherwise
$(x_{k},x_{k+1})\Lambda(x^{\prime\prime}_{k},x^{\prime}_{k+1})\Lambda(x_{k-1},x_{k+1})$,
a contradiction. It must also be adjacent to $x_{k-2}$ as otherwise
$(x_{k},x_{k+1})\Lambda(x^{\prime\prime}_{k},x^{\prime}_{k+1})\Lambda(x_{k-2},x_{k+1})$,
a contradiction. Continuing this way, we see that $x^{\prime}_{k+1}$ is
adjacent to all of $x_{a},x_{1},x_{2},\dots,x_{k-1}$. Now consider $x_{k+1}$.
It must be adjacent to $x^{\prime}_{1}$ as otherwise
$(x_{k},x_{k+1})\Lambda(x^{\prime}_{1},x^{\prime}_{k+1})\Lambda(x_{k},x_{a})$,
a contradiction. It must also be adjacent to $x^{\prime}_{2}$ as otherwise
$(x_{k},x_{k+1})\Lambda(x^{\prime}_{2},x^{\prime}_{k+1})\Lambda(x_{k},x_{1})$,
a contradiction. Continuing this way we see that $x_{k+1}$ is adjacent to all
of $x^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{k}$. A similar proof shows
that $x_{k+1}$ is adjacent to all of
$x^{\prime\prime}_{a},x^{\prime\prime}_{1},x^{\prime\prime}_{2},\dots,x^{\prime\prime}_{k-1}$.
Note that $x^{\prime}_{k+1}$ is adjacent to $x_{k+1}$ but not to $x_{k}$ so it
must be adjacent to $x_{k+2}$ by assumption. The vertex $x_{k+2}$ must also be
adjacent to $x^{\prime}_{k}$ as otherwise
$(x_{k-1},x_{k})\Lambda(x^{\prime}_{k+1},x^{\prime}_{k})\Lambda(x_{k+2},x_{k})$,
a contradiction. Continuing this way we see that $x_{k+2}$ is adjacent to all
of $x^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{k+1}$. Finally we consider
$x^{\prime\prime}_{k+1}$. It is adjacent to $x_{k+1}$ by definition. It must
be adjacent to $x_{k-1}$ as otherwise
$(x_{k-1},x_{k})\Lambda(x^{\prime}_{k+1},x^{\prime\prime}_{k+1})\Lambda(x_{k},x_{k+2})$,
a contradiction. It must be adjacent to $x_{k-2}$ as otherwise
$(x_{k-2},x_{k-1})\Lambda(x^{\prime}_{k},x^{\prime\prime}_{k+1})\Lambda(x_{k-1},x_{k+2})$.
Continuing this manner we see that $x^{\prime\prime}_{k+1}$ is adjacent to all
of $x_{a},x_{1},\dots,x_{k+1}$. ∎

Note that for each $i=1,2,\dots,a$, $x_{i}x^{\prime}_{i+1}$ and
$x_{i}x^{\prime\prime}_{i-1}$ are edges in the complement $\overline{G}$ of
$G$. It follows from Claim 2.1 that in $\overline{G}$, the edges
$x_{i}x^{\prime}_{i+1}$ form an independent set of edges, that is, $x_{i}$ is
not adjacent to $x^{\prime}_{j}$ for all $i\neq j-1$; similarly, the edges
$x_{i}x^{\prime\prime}_{i-1}$ form an independent set of edges, that is,
$x_{i}$ is not adjacent to $x^{\prime\prime}_{j}$ for all $i\neq j+1$.

Claim 2.2. For each $i=1,2,\dots,a$, let $x^{\prime}_{i}$ be a vertex adjacent
to $x_{i}$ but not to $x_{i-1}$ and $x^{\prime\prime}_{i}$ be a vertex
adjacent to $x_{i}$ but not to $x_{i+1}$. Then

$C^{\prime\prime}:\
(x^{\prime}_{a},x^{\prime}_{a-1}),(x^{\prime}_{a-1},x^{\prime}_{a-2}),\dots,(x^{\prime}_{2},x^{\prime}_{1}),(x^{\prime}_{1},x^{\prime}_{a})$

is a shortest circuit in $U\cup I$.

Proof of Claim 2.2. By Claim 2.1, each $x_{i}$ is adjacent to
$x^{\prime}_{i+2}$ and $x_{i+1}$ is adjacent to $x^{\prime}_{i+1}$. So
$(x_{i},x_{i+1})\Lambda(x^{\prime}_{i+2},x^{\prime}_{i+1})$ for each $i$.
Hence $C^{\prime\prime}$ is a circuit in $U\cup I$. It is the shortest because
it has the same length as $C$. ∎

Claim 2.3. Let $i$ be fixed. If $(x_{i},x_{i+1})\Lambda(u,v)$ for some
$(u,v)\neq(x_{i},x_{i+1})$, then substituting $(u,v)$ for
$(x^{\prime}_{i+2},x^{\prime}_{i+1})$ in $C^{\prime\prime}$ results in a
shortest circuit in $U\cup I$. Similarly, if
$(x^{\prime}_{i+2},x^{\prime}_{i+1})\Lambda(u^{\prime},v^{\prime})$ for some
$(u^{\prime},v^{\prime})\neq(x^{\prime}_{i+2},x^{\prime}_{i+1})$, then
substituting $(u^{\prime},v^{\prime})$ for $(x_{i},x_{i+1})$ in $C$ results in
a circuit in $U\cup I$.

Proof of Claim 2.3. If $(x_{i},x_{i+1})\Lambda(u,v)$, then $u$ can play the
role of $x^{\prime}_{i+2}$ and $v$ can play role of $x^{\prime}_{i+1}$ in
Claim 2.1. Hence by Claim 2.2 substituting $(u,v)$ for
$(x^{\prime}_{i+2},x^{\prime}_{i+1})$ in $C^{\prime\prime}$ results in a
circuit in $U\cup I$. The new circuit is a shortest one in $U\cup I$ because
it has the same length as $C$. The proof of the second part is the same when
the roles of $C$ and $C^{\prime\prime}$ are switched in both Claims 2.1 and
2.2. ∎

Claim 2.4. $C$ contains one or two pairs from $I$.

Proof of Claim 2.4. Since there is no circuit in $U$, $C$ must contain at
least one pair from $I$. Suppose that $(x_{r},x_{r+1}),(x_{s},x_{s+1})\in I$
for some $r\neq s$. Since both $(x_{r},x_{r+1}),(x_{s},x_{s+1})$ are from $I$,
there is a sequence

$(u_{1},v_{1})\Lambda(u_{2},v_{2})\Lambda\cdots\Lambda(u_{k},v_{k})$

of pairs in $I$ such that $(u_{1},v_{1})=(x_{r},x_{r+1})$,
$(u_{k},v_{k})=(x_{s},x_{s+1})$, and $(u_{i},v_{i})\neq(u_{i+1},v_{i+1})$ for
each $i$. If $k$ is odd, then it follows from Claim 2.3 substituting
$(x_{s},x_{s+1})$ for $(x_{r},x_{r+1})$ in $C$ results in a shortest circuit
in $U\cup I$. But the new circuit has equal vertices $x_{s}$ (and $x_{s+1}$)
so it is not the shortest, a contradiction. Hence $k$ must be even. Therefore
any two pairs in $C$ which are from $I$ can only be connected by such a
sequence consisting of an even number of pairs. Suppose that $C$ contains
three pairs from $I$. Then there is a sequence as above consisting of an even
number of pairs connecting the first and the second pairs, and there is a
sequence consisting consisting of an even number of pairs connecting the
second and the third pairs. By concatenating the two sequences we obtain a
sequence consisting of an odd number of pairs connecting the first and the
third pairs, which contradicts the above fact. ∎

Claim 2.5. If $C$ contains exactly one pair from $I$, then for any $(u,v)\in
I$, $U\cup I$ contains a circuit in which $(u,v)$ is the only pair from $I$.
If $C$ contains exactly two pairs from $I$, then for any two pairs
$(u_{1},v_{1}),(u_{k},v_{k})\in I$ connected by a sequence

$(u_{1},v_{1})\Lambda(u_{2},v_{2})\Lambda\cdots\Lambda(u_{k},v_{k})$

where $(u_{i},v_{i})\neq(u_{i+1},v_{i+1})$ and $k$ is odd, $U\cup I$ contains
a circuit in which $(u_{1},v_{1}),(u_{k},v_{k})$ are the only pairs from $I$.

Proof of Claim 2.5. If $C$ contains exactly one pair from $I$, then
$C^{\prime\prime}$ also contains exactly one pair from $I$. By Claim 2.3,
substituting $(u,v)$ for the pair in $C$ or the pair in $C^{\prime\prime}$
results in a circuit in which $(u,v)$ is the only pair from $I$. Similarly, if
$C$ contains exactly two pairs from $I$, then $C^{\prime\prime}$ also contains
exactly two pairs from $I$. By Claim 2.3, substituting
$(u_{1},v_{1}),(u_{k},v_{k})$ for the two pairs in $C$ or the two pairs in
$C^{\prime\prime}$ results in a circuit in which $(u_{1},v_{1}),(u_{k},v_{k})$
are the only two pairs from $I$. ∎

We know from above that if $U\cup I$ contains a circuit then Case 1 or Case 2
occurs for any shortest circuit in $U\cup I$. In any case, either $U\cup I$
has a circuit which contains exactly one pair from $I$ or a circuit which
contains exactly two pairs from $I$. The same is true for $U\cup I^{-1}$.
Suppose that both $U\cup I$ and $U\cup I^{-1}$ contain circuits. We show that
$U$ has circuits, which contradicts our assumption. Let
$(u,v),(u^{\prime},v^{\prime})\in I$ be connected by the sequence

$(u,v)=(u_{1},v_{1})\Lambda(u_{2},v_{2})\Lambda\cdots\Lambda(u_{k},v_{k})=(u^{\prime},v^{\prime})$

where $(u_{i},v_{i})\neq(u_{i+1},v_{i+1})$ and $k$ is odd. When each of $U\cup
I$ and $U\cup I^{-1}$ has a circuit which contains exactly one pair from $I$,
by Claim 1.5 $U\cup I$ has a circuit $C$ in which $(u,v)$ is the only pair
from $I$ and $U\cup I^{-1}$ has a circuit $C^{\prime}$ in which $(v,u)$ is the
only pair from $I^{-1}$. Then $(C\cup C^{\prime})\setminus\\{(u,v),(v,u)\\}$
is a circuit in $U$. When each of $U\cup I$ and $U\cup I^{-1}$ has a circuit
which contains exactly two pairs from $I$, by Claim 2.5 $U\cup I$ has a
circuit $C$ in which $(u,v),(u^{\prime},v^{\prime})$ are the only pairs from
$I$ and $U\cup I^{-1}$ has a circuit $C^{\prime}$ in which
$(v,u),(v^{\prime},u^{\prime})$ are the only pairs from $I^{-1}$. Then $(C\cup
C^{\prime})\setminus\\{(u,v),(u^{\prime},v^{\prime}),(v,u),(v^{\prime},u^{\prime})\\}$
is a union of two circuits in $U$. Suppose that one of $U\cup I$ and $U\cup
I^{-1}$ has a circuit which contains exactly one pair from $I$ and the other
has a circuit $C^{\prime\prime}$ which contains exactly two pairs from $I$.
Without loss of generality assume that $U\cup I$ has a circuit which contains
exactly one pair from $I$. By Claims 1.5 and 2.5, $U\cup I$ has a circuit $C$
in which $(u,v)$ is the only pair from $I$ and a circuit $C^{\prime}$ in which
$(u^{\prime},v^{\prime})$ is the only pair from $I$, and $U\cup I^{-1}$ has a
circuit $C^{\prime\prime}$ in which $(v,u),(v^{\prime},u^{\prime})$ are the
only pairs from $I$. Then $(C\cup C^{\prime}\cup
C^{\prime\prime})\setminus\\{(u,v),(u^{\prime},v^{\prime}),(v,u),(v^{\prime},u^{\prime})\\}$
is a circuit in $U$. Therefore at least one of $U\cup I$ and $U\cup I^{-1}$
does not contain a circuit. This completes the proof. ∎

Combining Propositions 9, 10, and Theorem 11, we have the following:

######  Theorem 12.

The following statements are equivalent for a reflexive graph $G$:

(i) $G$ is a strong cocomparability graph;

(ii) $G$ contains no invertible pairs;

(iii) $G^{+}$ is bipartite. ∎

Given a reflexive graph $G$, in polynomial time one can construct $G^{+}$ and
test whether it is bipartite. Thus we have the following:

######  Corollary 13.

There is a polynomial-time algorithm to decide whether a reflexive graph is a
strong cocomparability graph. ∎

##  4 Concluding remarks and open problems

Strong cocomparability graphs form a proper subclass of cocomparability
graphs. Gilmore and Hoffman [11] proved that a reflexive graph is an interval
graph if and only if it is both a chordal graph and a cocomparability graph.
The following may be viewed as a strengthening of the theorem of Gilmore and
Hoffman.

######  Theorem 14.

A reflexive graph $G$ is an interval graph if and only if it is both a
strongly chordal graph and a strong cocomparability graph.

Proof: Suppose that $G$ is an interval graph. Then by Theorems 4 and 5 it is
strongly chordal. Since $G$ is an interval graph, it has an interval ordering,
which is a vertex ordering $\prec$ such that for all $x\prec y\prec z$, $xz\in
E(G)$ implies $xy\in E(G)$. It is easy to check that $\prec$ is a strong
cocomparability ordering. Hence $G$ is also a strong cocomparability graph.

On the other hand, suppose that $G$ is not an interval graph. Then according
to [26] it contains an induced cycle of length $\geq 4$ or an asteroidal
triple (i.e., a set of three vertices such that any two of them are joined by
a path which contains no neighbour of the third vertex). If it contains an
induced cycle of length $\geq 4$ then it is not strongly chordal. Suppose that
$u,v,w$ form an asteroidal triple in $G$. Then there is a path $P$ joining
$u,v$ which contains no neighbour of $w$. For each edge $xy$ on $P$, $xwy$ is
an induced $P_{3}$ in $\overline{G}$. By Proposition 7, $(x,w)\Lambda(y,w)$.
It follows that $(u,w)\sim(v,w)$. Similarly, $(u,v)\sim(w,v)$ and
$(w,u)\sim(v,u)$. Hence

$(u,v)\sim(w,v)\sim(w,u)\sim(v,u)$

which shows that $u,v$ are an invertible pair in $G$ and, by Theorem 12, $G$
is not a strong cocomparability graph. ∎

A forbidden induced subgraph characterization of cocomparability graphs has
been given by Gallai [10]. It would be very interesting to find a forbidden
induced subgraph characterization for strong cocomparability graphs.

######  Problem 15.

Characterize strong cocomparability graphs by forbidden subgraphs.

Gallai’s forbidden induced subgraph characterization of cocomparability graphs
has 7 infinite families (including for example cycles with at least five
vertices) and 10 of other subgraphs, each on seven vertices. In addition to
these, we have found by a computer search that there are many other minimal
graphs that are not strong cocomparability graphs (but are cocomparability
graphs) – 5 on six vertices, 5 on seven vertices, 12 on eight vertices, and 30
on nine vertices.

Thus the above problem seems difficult at the moment. On the other hand, there
is a simple forbidden subgraph characterization for strong cocomparability
graphs that are bipartite.

A reflexive graph is bipartite if the graph obtained from it by deleting all
loops is bipartite in the traditional sense. We use other terminology on
bigraphs and bipartite graphs in the same sense, by applying them to the graph
with loops removed; notably this is how we define the class of chordal
bigraphs for the reflexive case.

Figure 2 depicts the forbidden subgraphs $S$ and $T$ for bipartite strong
cocomparability graphs.

Figure 2: The two minimal forbidden subgraphs, $S$ on the left and $T$ on the
right.

######  Theorem 16.

A bipartite graph is a strong cocomparability graph if and only is it is a
chordal bigraph that does not contain $S$ or $T$ as a subgraph.

Note that the characterization is stated for forbidden (not necessarily
induced) subgraphs. It can of course be translated to a forbidden induced
subgraph characterization, by forbidding all bipartite supergraphs of $S$ and
$T$.

A caterpillar is a tree $G$ such that after the deletion of all its leaves
(vertices of degree one) $G$ becomes a path, called the spine of $G$. If a
vertex $v$ on the spine of a caterpillar $G$ has degree two in $G$, we say we
replicate it if we add to $G$ additional vertices
$v^{\prime},v^{\prime\prime},\dots,v^{*}$ of degree two, with exactly the same
neighbours as $v$; we call $v$ the shadow of all the replicated vertices.
Consider a complete bipartite subgraph $K_{2,s}$ (for any $s\geq 2$) of a
graph $G$, with the bipartition $A\cup B$, where $|A|=2,|B|=s\geq 2$. If all
$s$ vertices in $B$ have degree two in $G$, we call the subgraph a square in
$G$ and the two vertices in $A$ its connectors.

Proof: It follows from [10] that $T$ or any cycle with at least six vertices
is not a cocomparability (and hence not a strong cocomparability) graph.
Moreover, any spanning bipartite supergraph of $T$ contains a bipartite
supergraph of $S$. Finally, all bipartite supergraphs of $S$ fail to be strong
cocomparability graphs; this can be seen by a simple but tedious argument.
Therefore, each bipartite strong cocomparability graph is a chordal bigraph
that does not contain $S$ or $T$ as a subgraph.

To prove the converse, let $G$ be a connected chordal bigraph that does not
contain $S$ or $T$ as a subgraph. If $G$ is a tree, then the absence of $T$
implies that $G$ is a caterpillar, with spine $v_{1},v_{2},\dots,v_{k}$. We
construct a strong cocomparability ordering of any caterpillar $G$ as
$v_{1}\prec S_{1}\prec v_{2}\prec S_{2}\prec\dots\prec v_{k}\prec S_{k}$,
where $S_{i}$ is the set of leaves adjacent to $v_{i}$, listed in arbitrary
order.

If $G$ is not a tree, then it must contain a four-cycle. Moreover, each four-
cycle must have two opposite vertices of degree two, else we have a copy of
$S$. Suppose $abcda$ is a four-cycle with $a,c$ of degree two. Then any vertex
$x$ adjacent to both $b$ and $d$ must also be of degree two, and by adjoining
all such vertices $x$ we obtain a square in $G$. This applies even in the case
the square is just a four-cycle, as in the above example, where $b,d$ are the
connectors. (Note that in such a case, the connectors can also be of degree
two.) Two squares can meet in at most one vertex, which must be a connector in
both squares, otherwise $G$ had a copy of $S$. Now consider the graph $G^{*}$
obtained from $G$ by deleting all but one of the degree two vertices that are
not connectors in any square. We can view the removed vertices as being the
results of replication, and hence the remaining vertex is their shadow. Since
the graph is connected and chordal, $G^{*}$ is a tree, and hence a
caterpillar. Moreover, each shadow vertex is on the spine, and has no
children. The strong cocomparability ordering of the caterpillar $G^{*}$, as
described above, can now be modified to a strong cocomparability ordering of
$G$ by inserting each of the replicated vertices next to their shadow vertex
from its square. Because the shadow vertices have no children off the spine,
this is indeed a strong cocomparability ordering. ∎

We observe that the proof gives an implicit description of all bipartite
strong cocomparability graphs – they are obtained from caterpillars by
replicating an arbitrary set of non-consecutive degree two vertices. This is
illustrated in Figure 3.

Figure 3: A typical example of a bipartite strong cocomparability graph.

Since bipartite strong cocomparability graphs do not contain asteroidal
triples, they are bipartite permutation graphs [32]. On the other hand if a
bipartite permutation graph does not contain $S$ as a subgraph then it does
not contain $T$ as a subgraph and hence by Theorem 16 it is a strong
cocomparability graph.

######  Corollary 17.

A bipartite graph is a strong cocomparability graph if and only if it is a
bipartite permutation graph which does not contain $S$ as a subgraph. ∎

We also want point out a relationship between bipartite strong cocomparability
graphs and cocomparability bigraphs. Clearly, if a cocomparability bigraph is
a strong cocomparability graph then it is a bipartite strong cocomparability
graph. Suppose that $G$ is a bipartite strong cocomparability graph. Then by
definition the adjacency matrix of $G$ has a symmetric $Slash$-free ordering,
which implies that the biadjacency matrix of $G$ has a $Slash$-free ordering
and hence $G$ is a cocomparability bigraph. Therefore bipartite strong
cocomparability graphs are precisely those strong cocomparability graphs which
are also cocomparability bigraphs.

On a final note, we observe that by complementation we can introduce the class
of strong comparability graphs. We define $G$ to be a strong comparability
graph, if its complement $\overline{G}$ is a strong cocomparability graph. The
complementation includes the loops, thus strong comparability graphs are
irreflexive, and their adjacency matrices have $0$-diagonal. A square
symmetric $0,1$ matrix with $0$-diagonal has a symmetric $I_{2}$-free ordering
if and only if it is the adjacency matrix of a strong comparability graph. The
class of strong comparability graphs has an ordering characterization, a
forbidden structure characterization, and a polynomial recognition algorithm,
all via the our corresponding results for their complements, i.e., the strong
cocomparability graphs.

To further motivate these concepts, we recall from [14] the definition of a
principal $\Gamma$ (respectively, $Slash$) submatrix of a symmetric matrix
with $1$-diagonal: it is a $\Gamma$ (respectively, $Slash$) submatrix with one
of its $1$’s lying on the main diagonal. Then

  * •

a reflexive graph is chordal if and only if its adjacency matrix admits a
symmetric ordering without a principal $\Gamma$ submatrix; and is strongly
chordal if and only if its adjacency matrix admits a symmetric ordering
without any $\Gamma$ submatrix, and

  * •

a reflexive graph is a cocomparability graph if and only if its adjacency
matrix admits a symmetric ordering without a principal $Slash$ submatrix; and
is a strong cocomparability graph if and only if its adjacency matrix admits a
symmetric ordering without any $Slash$ submatrix.

Similarly, we define a principal $I_{2}$ submatrix in a symmetric matrix with
$0$-diagonal: this is an $I_{2}$ submatrix with either of the $0$’s lying on
the main diagonal. Then

  * •

an irreflexive graph $G$ is a comparability graph if and only if its adjacency
matrix admits a symmetric ordering without a principal $I_{2}$ submatrix, and
is a strong comparability graph if and only if its adjacency matrix admits a
symmetric ordering without any $I_{2}$ submatrix.

These analogies suggest that these concepts are natural and may lead to
interesting questions. As a first example, consider the domination problem,
which is known to be NP-complete for chordal graphs but polynomial-time
solvable for strongly chordal graphs [6]. The domination problem is also NP-
complete for comparability graphs [23], so we wonder about strong
comparability graphs.

######  Problem 18.

Determine the complexity of the domination problem for strong comparability
graphs.

We note that for cocomparability graphs the domination problem is polynomial-
time solvable [25].

## References

  * [1] R.P. Anstee and M. Farber, Characterizations of totally balanced matrices, J. Algorithms 5 (1984) 215 - 230.
  * [2] V.L. Beresnev and A.I. Davydov, On matrices with the connectedness property, Upravlyaemye sistemy 19 (1979) 3-13 [in Russian].
  * [3] J. Bok, R. Brewster, P. Hell, N. Jedličková, and A. Rafiey, Min orderings and list homomorphism dichotomies for signed and unsigned graphs, arXiv:2206.01068 [math.CO].
  * [4] P. Damaschke, Forbidden ordered subgraphs, Topics in Combinatorics and Graph Theory (1990) 219 - 229.
  * [5] M. Farber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173 - 189.
  * [6] M. Farber, Domination, independent domination, and duality in strongly chordal graphs, Discrete Appl. Math. 7 (1984) 115 - 130.
  * [7] T. Feder, P. Hell, and J. Huang, List homomorphisms and circular arc graphs, Combinatorica 19 (1999) 487 - 505.
  * [8] T. Feder, P. Hell, J. Huang, and A. Rafiey, Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms, Discrete Appl. Math. 160 (2012) 697 - 707.
  * [9] M. Francis, P. Hell, and J. Stacho, Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm, SODA 2015.
  * [10] T. Gallai, Transitiv orientierbare graphen, Acta Mathematica Academiae Scientiarum Hungarica 18 (1967) 25 - 66.
  * [11] P.C. Gilmore and A.J. Hoffman, A characterization of comparability graphs and interval graphs, Canad. J. Math. 16 (1962) 539 - 548.
  * [12] M.C. Golumbic and C.F. Goss, Perfect elimination and chordal bipartite graphs. J. Graph Theory 2 (1978) 155 - 163.
  * [13] P. Hell, C. Hernández-Cruz, J. Huang, and J. C.-H. Lin, Strong chordality of graphs with possible loops, SIAM Journal on Discrete Math. 35 (2021) 362 - 375.
  * [14] P. Hell, J. Huang, J.C.-H. Lin, and R.M. McConnell, Bipartite analogues of comparability and cocomparability graphs, SIAM J. Discrete Math. 34 (2020) 1969 - 1983.
  * [15] P. Hell, J. Huang, R.M. McConnell, and A. Rafiey, Min-orderable digraphs, SIAM J. Discrete Math. 34 (2020) 1910 - 1724.
  * [16] P. Hell, M. Mastrolilli, M.M. Nevisi, and A. Rafiey, Approximation of minimum cost homomorphisms, ESA, 2012, pp. 587 - 598.
  * [17] P. Hell, B. Mohar, and A. Rafiey, Ordering without forbidden patterns, ESA 2014, LNCS 8737 (2014) 554 - 565.
  * [18] P. Hell and A. Rafiey, Monotone proper interval digraphs and min-max orderings, SIAM J. Discrete Math. 26 (2012) 1576 - 1596.
  * [19] A.J. Hoffman, M. Sakarovich, and A. Kolen, Totally balanced and greedy matrices, SIAM J. Algebraic Discrete Methods 6 (1985) 721 - 730.
  * [20] J. Huang, Representation characterizations of chordal bipartite graphs, J. Combinatorial Theory B 96 (2006) 673 - 683.
  * [21] J. Huang, Non-edge orientation and vertex ordering characterizations of some classes of bigraphs, Discrete Applied Math. 245 (2018) 190 - 193.
  * [22] A.J. Hoffman, A.W.. Kolen, and M. Sakarovitch, Totally-balanced and greedy matrices, SIAM J. Algebraic and Discrete Methods 6 (1985) 721 - 730.
  * [23] D.S. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 6 (1985) 145 - 159, 291 - 305, 434 - 451.
  * [24] B. Klinz, R. Rudolf, and G.J. Woeginger, Permuting matrices to avoid forbidden submatrices, Discrete Applied Math. 60 (1995) 223 - 248.
  * [25] D. Kratsch and L. Stewart, Domination on cocomparability graphs, SIAM J. Discrete Math. 6 (1993) 400 - 417.
  * [26] C.G. Lekkerkerker and J.Ch. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962) 45 - 64.
  * [27] A. Lubiw, $\Gamma$-free matrices, Master’s thesis, University of Waterloo, 1982.
  * [28] A. Lubiw, Doubly lexical orderings of matrices, SIAM J. Comput. 16 (1987) 854 - 879.
  * [29] R. Paige and R.E. Tarjan, Three partition refinement algorithms, SIAM .I. Comput. 16 (1987) 973 - 989.
  * [30] A.M. Shresta, S. Tayu, and S. Ueno, On two-directional orthogonal ray graphs, in Proceedings of the 2010 IEEE International Symposium on Circuits and Systems, IEEE, pp. 1807 - 1810.
  * [31] J.P. Spinrad, Efficient Graph Representations, Fields Inst. Monogr. 19, AMS, Providence, RI, 2003.
  * [32] J.P. Spinrad, A. Brandstädt and L. Stewart, Bipartite permutation graphs, Discrete Appl. Math. 18 (1987) 279 - 292.