A note on PM-compact $K_4$-free bricks

1.   Introduction

Graphs considered in this paper are simple graphs. We will use generally Bondy and Murty ^[1] for the notation and terminology not defined here.

A connected graph is called matching covered if it has at least one edge and each of its edges is contained in some perfect matching. For the terminology that is specific to matching covered graphs, we will generally follow Lovász and Plummer ^[9]. Edmonds et al. ^[6] (also see Lovász ^[8], Szigeti ^[11] and Carvalho et al. ^[4]) showed that a graph $G$ is a brick if and only if $G$ is $3$-connected and $G-x-y$ has a perfect matching for any two distinct vertices $x, y\in V(G)$.

Let $G$ be a matching covered graph, and let $M_1$ and $M_2$ be two perfect matchings of $G$. We denote by $PM(G)$ the perfect-matching graph of $G$, which is the graph whose vertices are the perfect matchings of $G$, with two vertices $M_1$ and $M_2$ are adjacent in $PM(G)$ if $M_1\oplus M_2$ is a cycle, where $\oplus$ denotes the symmetric difference operation. We say that $G$ is PM-compact if $PM(G)$ is complete. Clearly, each conformal subgraph of a PM-compact graph is also PM-compact. Since an even cycle contains two perfect matchings, the following simple observation is an immediate consequence.

Lemma 1. A matching covered graph $G$ is $PM$-compact if and only iffor any two vertex-disjoint even cycles $C_1$ and $C_2$ of$G$, $G-V (C_1\cup C_2)$ has no perfect matchings.

Moreover, Wang et al. ^[12] characterized PM-compact bipartite and near-bipartite graphs. Wang et al. ^[13] characterized all claw-free PM-compact cubic graphs. Wang et al. ^[14] characterized all Hamiltonian PM-compact bipartite graphs.

A bisubdivision of a graph $H$ is a graph obtained from $H$ by inserting an even number of vertices to some of its edges. A matching covered graph $H$ is a conformal minor of a matching covered graph $G$ if there exists a bisubdivision $J$ of $H$ which is a subgraph of $G$ such that $G-V(J)$ has a perfect matching. A matching covered graph is $K_4$-free if it contains no $K_4$ as a conformal minor, otherwise it is $K_4$-based. $\overline{C}_6$-free and $\overline{C}_6$-based graphs are analogously defined ($\overline{C}_6$ is the complement graph of the cycle with six vertices). Recently, Carvalho et al. ^[2] characterised the PM-compact $\overline{C}_6$-free bricks. In this note, we characterize the PM-compact $K_4$-free bricks as follows.

Theorem 2. Let $G$ be a $K_4$-free brick. If $G$ is PM-compact, then $G$ is isomorphic to $\overline{C}_6$, up tomultiple edges.

The proof of Theorem 2 will be given in Section 3 following some properties concerning matching covered graphs given in Section 2.

2.   Preliminaries

In this section, we present some properties of matching covered graphs which will be used in the proof of the main result. We start with some basic definitions. Let $G$ be a matching covered graph, $v$ a vertex of degree two of $G$. The bicontraction of $v$ is the operation of contracting the two edges incident with $v$. The retract of $G$ is the graph obtained by bicontracting all its vertices of degree two. An edge $e$ in a brick $G$ is thin if the retract of $G-e$ is also a brick. A thin edge $e$ of a simple brick $G$ is strictly thin if the retract of $G-e$ is a simple brick. Carvalho, Lucchesi, and Murty ^[3] proved that every brick distinct from $K_4, \overline{C}_6$ and the Petersen graph has a thin edge. We say that a brick is a Norine-Thomas brick if it is the Petersen graph or it belongs to any of the following described five well-defined infinite families of graphs:

Odd Wheel $W_{2k+1}$. For each integer $k\ge 1$, $W_{2k+1}$ is defined to be the join graph of an odd cycle $C_{2k+1}$ and a new vertex. See Figure 1 (a).

Truncated biwheel $T_{2k+2}$. For each integer $k\ge 2$, let $P = v_1v_2\cdots v_{2k}$ be an odd path, $u$ and $v$ be two new vertices. Let $T_{2k+2}$ be obtained from $P\cup u\cup v$ by adding edges $uv_i$ and $vv_j$ for $i = 1, 2k$ and all even $i\in \{1, 2, \ldots, 2k\}$ and $j = 1, 2k$ and all odd $j\in \{1, 2, \ldots, 2k\}$. See Figure 1 (b).

Möbius ladder $M_{4k}$. For each integer $k\ge 1$, let $P_1 = u_1u_2\cdots u_{2k}$ and $P_2 = v_1v_2\cdots v_{2k}$ be two odd paths. Let $M_{4k}$ be obtained from $P_1\cup P_2$ by adding edges $u_iv_i$ for $i = 1, 2, \ldots, 2k$ and $u_1v_{2k}$ and $v_1u_{2k}$. See Figure 1 (c).

Prism $Pr_{4k+2}$. For each integer $k\ge 1$, let $P_1 = u_1u_2\cdots u_{2k+1}$ and $P_2 = v_1v_2\cdots v_{2k+1}$ be two odd paths. Let $Pr_{4k+2}$ be obtained from $P_1\cup P_2$ by adding edges $u_iv_i$ for $i = 1, 2, \ldots, 2k+1$ and $u_1u_{2k+1}$ and $v_1v_{2k+1}$. See Figure 1 (d).

Staircase $St_{2k+2}$. For each integer $k\ge 2$, let $P_1 = u_1u_2\cdots u_k$ and $P_2 = v_1v_2\cdots v_k$ be two paths, $u$ and $v$ be two new vertices. Let $St_{2k+2}$ be obtained from $P_1\cup P_2\cup u\cup v$ by adding edges $u_iv_i$ for $i = 1, 2, \ldots, k$ and $uu_1, uv_1, vu_k, vv_k$ and $uv$. See Figure 1 (e).

Norine and Thomas ^[10] showed that every simple brick distinct from the Norine-Thomas bricks has a strictly thin edge. This implies the following result.

Theorem 3. ^[5,10] Given any brick $G$, there exists a sequence$G_1, G_2, \ldots, G_r$ of simple bricks such that (i) $G_1$ is aNorine-Thomas brick; (ii) $G_r : = G$; and (iii) for$2\le i \le r$, there exists a strictly thin edge $e_i$ of$G_i$ such that $G_{i-1}$ is the retract of $G_i-e_i$.

Since a matching covered graph is PM-compact if and only if its retract is PM-compact ^[2], the following consequence holds immediately.

Corollary 4. Let $e$ be a thin edge of a brick $G$ and let $H$ be theretract of $G-e$. If $G$ is PM-compact, then $H$ is alsoPM-compact.

Recently, Kothari and Murty ^[7] proved that, for any thin edge $e$ of a brick $G$ and any cubic brick $J$, the retract of $G-e$ is $J$-free if $G$ is $J$-free. This implies the following simple observation immediately.

Lemma 5. ^[7] Let $e$ be a thin edge of a brick $G$ and let $H$ be theretract of $G-e$. If $G$ is $K_4$-free, then $H$ is also $K_4$-free.

3.   Proof of Theorem 2

Suppose, to the contrary, that there exists a $K_4$-free PM-compact brick that is not isomorphic to $\overline{C}_6$, up to multiple edges. Among all such bricks, we choose a brick $G$ containing minimum number of edges. If $G$ contains multiple edges, then the underlying simple graph of $G$ is also a counterexample to Theorem 2. Thus, we may assume that $G$ is a simple brick. By Theorem 3, there exists a sequence $G_1, G_2, \ldots, G_r$ of simple bricks such that (i) $G_1$ is a Norine-Thomas brick; (ii) $G_r : = G$; and (iii) for $2\le i \le r$, there exists a strictly thin edge $e_i$ of $G_i$ such that $G_{i-1}$ is the retract of $G_i-e_i$. Since $G$ is PM-compact, each brick $G_i$ in the above sequence is PM-compact as well by Corollary 4. In particular, the base brick $G_1$ is PM-compact. Now, we will shall that $G_1$ is $\overline{C}_6$, namely, $G_1$ is the prism or the stair case or the truncated biwheel, with order 6. Since each odd wheel, the staircase $R_8$ with order 8 and the Petersen graph $P$ are $K_4$-based, it suffices to consider the four possible alternatives separately, by Lemma 5, as follows.

If $G_1$ is a truncated biwheel $T_{2k+2}$ with $k\ge 3$, then $C_1 = vv_1v_2v_3v$ and $C_2 = uv_4v_5v_6u$. Clearly, $C_1$ and $C_2$ are two disjoint even cycles of $G_1$ and $G_1-V(C_1\cup C_2)$ has a perfect matching $\{v_{2i-1}v_{2i}|4\le i\le k\}$ (see Figure 1 (b)). Thus, $G_1$ is not PM-compact by Lemma 1.

If $G_1$ is a Möbius ladder $M_{4k}$ with $k\ge 2$, then let $C_1 = u_1v_1v_2u_2u_1$ and $C_2 = u_3v_3v_4u_4u_3$. Clearly, $C_1$ and $C_2$ are two disjoint even cycles of $G_1$ and $G_1-V(C_1\cup C_2)$ has a perfect matching $\{u_iv_i|5\le i\le 2k\}$ (see Figure 1 (c)). Thus, $G_1$ is not PM-compact by Lemma 1.

If $G_1$ is a prism $Pr_{4k+2}$ with $k\ge 2$, then let $C_1 = u_1v_1v_2u_2u_1$ and $C_2 = u_3v_3v_4u_4u_3$. Clearly, $C_1$ and $C_2$ are two disjoint even cycles of $G_1$ and $G_1-V(C_1\cup C_2)$ has a perfect matching $\{u_iv_i|5\le i\le 2k+1\}$ (see Figure 1 (d)). Thus, $G_1$ is not PM-compact by Lemma 1.

If $G_1$ is a staircase $St_{2k+2}$ with $k\ge 4$, then let $C_1 = u_1v_1v_2u_2u_1$ and $C_2 = u_3v_3v_4u_4u_3$. Clearly, $C_1$ and $C_2$ are two disjoint even cycles of $G_1$ and $G_1-V(C_1\cup C_2)$ has a perfect matching $\{uv, u_iv_i|5\le i\le 2k\}$ (see Figure 1 (e)). Thus, $G_1$ is not PM-compact by Lemma 1.

Finally, we claim that $G$ is $\overline{C}_6$. Otherwise, the length $r$ of the brick sequence greater than one. Since $G_1$ is cubic (i.e., 3-regular), $G_2$ must be obtained from $G_1$ by adding an edge. Hence, $G_2$ is $K_4$-based. It is a contradiction by Lemma 5. Thus, $G = G_1$. This completes the proof.

4.   Concluding remarks

In this work, we obtained a characterization of PM-compact $K_4$-free bricks. Various similar or analogous problems may also be of interest and worthy of study. We propose two problems as follows.

Problem 1. Characterize PM-compact $K_4$-based bricks.

Problem 2. Characterize PM-compact $K_4$-free matching covered graphs.

Acknowledgments

The authors would like to thank the anonymous referees and the academic editor for their careful reading and valuable suggestions. The research is supported by National Natural Science Foundation of China (Grant No. 12001250), the Program of Qingjiang Excellent Young Talents, Jiangxi University of Science and Technology, the Foundation of Jiangxi Provincial Education Department of China (No. GJJ190490) and the Doctoral Fund Project of Doctoral Fund Project of Jiangxi University of Science and Technology (No. jxxjbs18063).

Conflict of interest

The authors declare no conflicts of interest in this paper.