Conditional Fractional Matching Preclusion for Burnt Pancake Graphs and Pancake-Like Graphs (Extended Abstract)

Abstract

The conditional fractional strong matching preclusion number of a graph G is the minimum size of F such that $F \subset V(G) \cup E(G)$ and $G-F$ has neither a fractional perfect matching nor an isolated vertex. In this paper, we obtain the conditional fractional strong matching preclusion number for burnt pancake graphs and a subset of the class of pancake-like graphs.

1 Introduction

Parallel computing is an important area of computer science and engineering. The underlying topology of such a parallel machine or a computer network is the interconnection network. Computing nodes are processors where the resulting system is a multiprocessor supercomputer, or they can be computers in which the resulting system is a computer network. It is unclear where the computing future is headed. It may lead to more research in multiprocessor supercomputers, physical networks or networks in the cloud. Nevertheless, the analysis of such networks will always be important. One important aspect of network analysis is fault analysis, that is, the study of how faulty processors/links will affect the structural properties of the underlying interconnection networks, or simply graphs.

All graphs considered in this paper are undirected, finite and simple. We refer to the book [3] for graph theoretical notation and terminology not described here. For a graph G, let V(G), E(G), and (u, v) (uv for short) denote the set of vertices, the set of edges, and the edge whose end vertices are u and v, respectively. For any subset X of V(G) or E(G), let G[X] denote the subgraph induced by X. We use $G - F$ to denote the subgraph of G obtained by removing all the vertices and (or) the edges of F. Some portions of this paper containing definitions are reused unchanged from [19].

1.1 Matchings

A perfect matching in a graph is a set of edges such that each vertex is incident to exactly one of them, and an almost perfect matching is a set of edges such that each vertex but one is incident to exactly one edge in the set, and the remaining vertex is incident to none. We can define a perfect matching as an indicator function as follows: let S be a set of edges in G. Then $f^S$ is the indicator function of S, with $f^S : E(G)\rightarrow \{0,1\}$ such that $f^S(e)=1$ iff $e\in S$. Let $\delta '(v)$ be the set of edges for which one end is v. Then M is a perfect matching of G if $\sum _{e\in \delta '(v)} f^M(e)=1$ for each vertex $v\in G$

A standard relaxation from an integer setting to a continuous setting is to extend the codomain of the indicator function from $\{0,1\}$ to [0, 1]. Let $f : E(G)\rightarrow [0,1]$. Then f is a fractional perfect matching if $\sum _{e\in \delta '(v)} f(e)=1$ for each vertex $v\in G$. We note that the specification that such a matching be “perfect” is somewhat redundant, as unlike a perfect matching, a fractional perfect matching can exist on odd graphs; the concept of fractional almost perfect matchings is not really necessary to consider or study.

Proposition 1

[23] The graph G has a fractional perfect matching if and only if there is a partition $\{V_1, V_2,\ldots ,V_n\}$ of the vertex set of V(G) such that, for each i, the graph $G[V_i]$ is either $K_2$ or a Hamiltonian graph on odd number of vertices.

Any graph with such a decomposition can be trivially assigned a fractional perfect matching by assigning each $K_2$ of the decomposition a weight of 1 and each edge in an odd cycle a weight of $\frac{1}{2}$, then replacing all removed edges. We call such a fractional perfect matching nice. For notational convenience, we assume that if a graph G has a fractional perfect matching f, then f is nice. Furthermore, if a nice fractional perfect matching contains an edge with weight 1, we refer to it as a complete edge, and if it contains an edge with weight $\frac{1}{2}$, we refer to it as a half edge. Finally, if we claim that any vertex u or edge vw is in an odd cycle in a fractional perfect matching, then we mean u is in a half edge with each of two other vertices, and that vw is a half edge.

1.2 Matching Preclusion

In [1], Brigham et al. first introduced the concept of matching preclusion. A set of edges F of G is called a matching preclusion set if $G - F$ has neither perfect matchings nor almost-perfect matchings, and it is called an optimal matching preclusion set if |F| is minimal. Then if $F_1$ is an optimal matching preclusion set, any set $F_2$ for which $|F_2|< |F_1|$ is not a matching preclusion set. The matching preclusion number of G, denoted by mp(G), is the cardinality of an optimal matching preclusion set. A set F of edges and vertices of G is a strong matching preclusion set (SMP set for short) if $G - F$ has neither perfect matchings nor almost-perfect matchings, and it is called an optimal strong matching preclusion set if F is one with the smallest size. The strong matching preclusion number (SMP number for short) of G, denoted by smp(G), is the cardinality of an optimal SMP set. An optimal SMP set is trivial if $G - F$ is even and there is a vertex v such that every vertex in F is a neighbour of v and every edge in F is incident to v. The concept of strong matching preclusion was proposed by Park and Ihm in 2011. We refer the readers to [4, 7,8,9, 16, 20, 22] for further details and additional references.

Recently, Liu and Liu in [18] introduced generalizations of the above concepts. An edge subset F of G is a fractional matching preclusion set (FMP set for short) if $G - F$ has no fractional perfect matchings. The fractional matching preclusion number (FMP number for short) of G, denoted by fmp(G), is the minimum size of FMP sets of G, that is, $fmp(G) = \min \{|F| : F$ is an FMP set$\}$. A set F of edges and vertices of G is a fractional strong matching preclusion set (FSMP set for short) if $G-F$ has no fractional perfect matchings. The fractional strong matching preclusion number (FSMP number for short) of G, denoted by fsmp(G), is the minimum size of FSMP sets of G, that is, $fsmp(G) = \min \{|F| : F$ is an FSMP set$\}$. A FMP (FSMP) set of minimal cardinality is called optimal, and an optimal FMP (FSMP) set F is trivial if $G-F$ contains an isolated vertex v ($\delta (v)=0$). If F is a trivial FMP (FSMP) set, every element in F is adjacent or incident to some v which is isolated in $G-F$. A graph G is fractional strongly super matched if every optimal FSMP set is trivial.

We can further constrain the conditions for FSMP by requiring that $G-F$ has no isolated vertices. An edge and vertex subset F of G is a conditional fractional strong matching preclusion set (CFSMP set for short) if $G-F$ has neither a fractional perfect matching, nor an isolated vertex. The conditional fractional strong matching preclusion number (CFSMP number for short) of G is the minimum size of a CFSMP set of G, that is, $cfsmp(G) = \min {\{|F| : F \text{ is } \text{ a } \text{ CFSMP } \text{ set }\}}$. A CFSMP set of minimal cardinality is called optimal, and a CFSMP set F is trivial if the graph $G-F$ contains some vertices u, v, w for which $\delta (u)=1, \delta (v)=1$, and $uw, vw \in E(G-F)$. A graph G is conditionally fractional strongly super matched if every optimal CFSMP set is trivial.

The pancake graphs and burnt pancake graphs, introduced in [11], are two well-studied interconnection networks. Although these graphs have nice structures, it seems that some problems in them are difficult and are still open, such as optimal routing problem. However, researchers have found that they are excellent candidates as interconnection networks. Some papers on the pancake graphs include [2, 6, 10, 14, 17, 21, 24] and papers on the burnt pancake graphs include [5, 6, 12, 13, 15]. In particular, in [12], the burnt pancake graphs are used for genome analysis. In [19], the FSMP number of general pancake and burnt pancake graphs was found (using the same inductive proof strategy we use here).

The pancake-like graphs are a broad class of graphs which contain the pancake graphs and burnt pancake graphs. Although the main result of this paper applies to burnt pancake graphs, the result also extends to a subset of pancake-like graphs.

In this paper, we study the conditional fractional strong matching preclusion problems for the pancake graphs and obtain the following main result.

Theorem 1

Let $n\ge 3$ be an integer, and let $B_n$ be the burnt pancake graph of dimension n. Then $cfsmp(B_n)=2n-2$, and $B_n$ is conditionally fractional strongly super matched.

Theorem 2

Let L be an arbitrary pancake-like graph composed of $n\ge 3$ subgraphs, such that every subgraph is $k-1$-regular with $k\ge 4$ and has girth at least 5. If every subgraph is fractional strongly super matched and conditionally fractional strongly super matched, then L must be fractional strongly super matched and conditionally fractional strongly super matched.

The rest of this paper is organized as follows. In Sect. 2, we provide some definitions and known results regarding the pancake graphs and burnt pancake graphs, followed by the pancake-like graph class. In Sect. 3, we note the conditional fractional strong matching preclusion of $B_3$, to serve as a base case. In Sect. 4, we discuss the proof technique.

2 Preliminaries

We first review the construction of pancake and burnt pancake graphs, as stated in [19], and present some related results.

The pancake graph of dimension n, denoted by $P_n$, has as its vertex set the set of all n! permutations on $\{1, 2, 3,\ldots ,n\}$. Two vertices $[a_1, a_2, a_3,\ldots ,a_n]$ and $[b_1, b_2, b_3,\ldots ,b_n]$ are adjacent if there exists an integer k with $2 \le k \le n$ such that $a_i = b_{k+1-i}$ for every i with $1 \le i \le n$, and $a_i = b_i$ for $k + 1 \le i \le n$; in other words, we take the “substring” $a_1, a_2, a_3,\ldots ,a_n$ and reverse the order. The edge generated by such an adjacency is called a k-edge. It follows directly from the definition that $P_n$ is $(n - 1)$-regular. Although $P_n$ is vertex-transitive, it is not edge-transitive except for $n = 3$. (However, it is not difficult to determine the edge-transitive classes.) Indeed, let $H_i$ be the subgraph of $P_n$ induced by the vertices with i in the nth position, which is isomorphic to $P_{n-1}$. We call $H_i$ to be a copy of $P_n$. We remark that $P_n$ can be decomposed into n copies, i.e., $P^1_{n-1}, P^2_{n-1},\ldots ,P ^n_{n-1}$. We note that $P_2$ is a complete graph with two vertices, $P_3$ is the cycle with six vertices and $P_4$ is given in Fig. 1. The edges between different copies are n-edges, which form a perfect matching in $P_n$. To highlight this property, we will refer to these edges as cross edges, and if uv is a cross edge, we call it the cross edge of u, and call v the cross neighbour of u. It is easy to see from the definition that if u is a vertex in $H_i$, then it has $n-2$ neighbours in $H_i$ (the set of these neighbours is denoted by $N_{H_i} (u))$, and the $n - 1$ cross neighbours of the vertices in $\{u\}\cup N_{H_i} (u)$ are in different $H_j$ ’s (one in each). It is also easy to see that there are exactly $(n - 2)!$ independent cross edges between two different $H_i$’s. Hence by an inductive argument we get that for each k, the set of k-edges forms a perfect matching in $P_n$. So the edges of $P_n$ can be partitioned into $n - 1$ edge-disjoint perfect matchings. See Fig. 1 for $P_4$, the pancake graph of dimension 4.

The definition of the burnt pancake graphs is related to the definition of the pancake graphs. Let $n \ge 3$. The burnt pancake graph of dimension n, denoted by $B_n$, is defined similarly to the pancake graphs. We say the list $[a_1, a_2,\ldots ,a_n]$ is a signed permutation on $\{1, 2, 3,\ldots ,n\}$ if $[|a_1|, |a_2|,\ldots , |a_n|]$ is a permutation on $\{1, 2, 3,\ldots ,n\}$. For notational simplicity, which is customary for this class of graphs, we use the notation $\bar{a}$ instead of $-a$. The burnt pancake graph $B_n$ has the set of signed permutations on $\{1, 2, 3,\ldots ,n\}$ as its vertex set. Two vertices $[a_1, a_2,\ldots ,a_n]$ and $[b_1, b_2,\ldots ,b_n]$ are adjacent if there exists a k with $1 \le k \le n$ such that $a_i = b_{k+1-i}$ for every i with $1 \le i \le k$, and $a_i = b_i$ for $k + 1 \le i \le n$. The edge generated by such an adjacency is again called a k-edge. It follows directly from the definition that $B_n$ is n-regular with $n!2^n$ vertices. We remark that $B_n$ is vertex transitive but not edge transitive. Indeed, let $H_a$ be the subgraph of Bn induced by the vertices with a in the nth position where $a \in \{1, 2, 3,\ldots ,n\}\cup \{ \bar{1}, \bar{2}, \bar{3},\ldots , \bar{n}\}$, which is isomorphic to $B_{n-1}$. We call $H_a$ to be a copy of $B_n$. Like $P_n$, $B_n$ is recursive in structure and can be decomposed into 2n copies, i.e., $B^1_{n-1}, B^2_{n-1},\ldots ,B^n_{n-1}, B^{\bar{1}}_{n-1}, B^{\bar{2}}_{n-1}, \ldots , B^{\bar{n}}_{n-1}$ We note that $B_1$ is a complete graph with two vertices, $B_2$ is the cycle with eight vertices and $B_3$ is given in Fig. 2. The n-edges are the edges between different $H_a$’s, and they form a perfect matching in $B_n$. Again we will refer to the n-edges as cross edges, and if uv is a cross edge, we call it the cross edge of u, and call v the cross neighbour of u. It is easy to see from the definition that if $u = [a_1, a_2,\ldots ,a_n]$ is a vertex in $H_{a_n}$, then it has $n-1$ neighbours in $H_{a_n}$ , and the cross neighbours of the vertices in $\{u\} \cup N_{a_n}(u)$ are in different $H_j$ ’s. Indeed, the cross neighbour of u is in $H_{a_1}$, and the cross neighbours of the neighbours of u are in $H_{a_1}, H_{a_2}, \ldots ,H_{a_{n-1}}$. It is easy to see that there are exactly $(n - 2)!2^{n-2}$ independent cross edges between $H_a$ and $H_b$ if $a = b$, and there are no edges between $H_a$ and $H_{\bar{a}}$. We note that for each k, the set of k- edges forms a perfect matching in $B_n$. So the edges of $B_n$ can be partitioned into n-edge-disjoint perfect matchings. See Fig. 2 for $B_3$, the burnt pancake graph of dimension 3.

Fig. 1.

The pancake graph of dimension 4.

Fig. 2.

The burnt pancake graph of dimension 3.

From the definition of $P_n$ and $B_n$, the following observations are immediate.

Proposition 2

For $n \ge 4$, the cross neighbours of two adjacent vertices in a copy of $P_n$ are in different copies.

Proposition 3

For $n \ge 3$, the cross neighbours of two adjacent vertices in a copy of $B_n$ are in different copies.

From [19], we have the following results on the FSMP numbers of pancake and burnt pancake graphs:

Theorem 3

[19] Let $n \ge 4$ be an integer, and let $P_n$ be the pancake graph of dimension n. Then $fsmp(P_n) = n-1$, and every optimal FSMP set of $P_n$ is trivial when $n \ge 5$.

Directly, for integer $n\ge 5$, $P_n$ is fractional strongly super matched.

Theorem 4

[19] Let $n \ge 3$ be an integer, and let $B_n$ be the burnt pancake graph of dimension n. Then $fsmp(B_n) = n$, and every optimal FSMP set of $B_n$ is trivial.

Directly, for integer $n\ge 3$, $B_n$ is fractional strongly super matched.

A pancake-like graph is any graph G which exhibits the property that it has a partition $\{V_1, V_2,\ldots ,V_n\}$ of the vertex set of V(G) such that, for each i, the graph $G[V_i]$ satisfies the following two properties: (i) each vertex is incident to exactly one cross edge, and (ii) the cross neighbours of two adjacent vertices are not in the same vertex subset in the partition, where a cross edge is any edge in the set $E(G)-E(G[V_1])-E(G[V_2])-\ldots -E(G[V_n])$ and cross neighbors are any two vertices a, b for which ab is a cross edge. We further define each $G[V_i]$ as a subgraph of G. Clearly, this definition aims to replicate the top-level structure of pancake and burnt pancake graphs.

3 Results for $B_3$

The following results are important in our analysis.

Lemma 1

[19] Let G be a fractional strongly super matched graph with $\delta (G)\ge 2$. If F is a trivial FSMP set of G and $G-F$ has an isolated vertex v, then $G-F-v$ has a fractional perfect matching.

We also prove an analogous result for conditionally fractional strongly super matched graphs.

Lemma 2

Let a conditionally fractional strongly super matched and fractional strongly super matched graph G with girth at least 5 and $\delta (G) = k$ have a trivial CFSMP set F such that $G-F$ contains some vertices u, v, w for which $\delta (u)=1, \delta (v)=1$, and $uw, vw \in E(G-F)$. Then $G-F-u$ and $G-F-v$ have fractional perfect matchings.

Proof

Since u and v are transitive, we prove for $G-F-u$. Let F contain at least one vertex x adjacent to u. The graph $G-(F-x)$ must either contain an isolated vertex or contain a fractional perfect matching. If $G-(F-x)$ contains an isolated vertex, since $G-F$ does not contain an isolated vertex, the isolated vertex must be x, which is adjacent to u. Then $G-(F-x)$ must contain a fractional perfect matching f. Since $\delta (v)=1$, then $f(vw)=1$, so $f(ux)=1$. Then $G-(F-x)-u-x=G-F-u$ has a fractional perfect matching.

If F does not contain at least one vertex adjacent to u, then we let $F_{u}$ be the set of edges in F adjacent to u. Then $G-F_{u}-u=G-u$ which must have a fractional perfect matching, so we consider $G-u-(F-F_{u})$. Because $|u \cup (F-F_u)|=k-1$, we have that $G-u-(F-F_{u})$ must have either a fractional perfect matching or an isolated vertex, but since v is adjacent to w, there are no isolated vertices. Then $G-u-(F-F_{u})=G-F-u$ must have a fractional perfect matching.

We use the following result to find that fractionally strongly conditionally super matched graphs with isolated vertices removed must have a fractional perfect matching.

Lemma 3

Let a fractionally strongly conditionally super matched graph G of degree $k\ge 3$ have a fault set $F\subset V(G) \cup E(G)$ with $|F|\le 2k-2$. If $G-F$ does not have an isolated vertex or three vertices u, v, w for which $\delta (u)=1, \delta (v)=1$, and $uw, vw \in E(G-F)$, then it must have a fractional perfect matching.

Proof

The proof follows from the definition of fractionally strongly conditionally super matched. For such a graph, every optimal CFSMP set of size $2k-2$ must be trivial, so the set F must either be a trivial CFSMP set, a non-CFSMP set which fails to be a CFSMP set by isolating a vertex, or a non-CFSMP set which fails to be a CFSMP set by leaving a fractional perfect matching.

We use the next result to show that graphs must effectively “concentrate” faults towards one of two categories in order to preclude a fractional perfect matching; if faults are allocated towards isolating a vertex, there are not enough faults left over to create the 3-vertex precluding structure.

Lemma 4

Let a conditionally fractional strongly super matched k-regular graph G of girth at least 5 have a fault set $F\subseteq V(G)\cup E(G)$ with $|F|=2k-2$. Then if $G-F$ contains an isolated vertex e, the graph $G-(F-\{e\})$ must contain a fractional perfect matching.

Proof

There are two cases.

Case 1. $G-F$ contains two isolated vertices, e and g. Then e and g are either adjacent or they share at most one common neighbor. If they are adjacent, then there are k faults adjacent or incident to each of e and g with at most one of those faults shared (the edge eg). Since $2k-1 > 2k-2$, this can not occur. If they share a common neighbor, the minimum fault set size required is the same. If they do not share a common neighbor, then $|F|\ge 2k$. Thus $G-F$ contains at most one isolated vertex.

Case 2. $G-F-\{e\}$ contains three vertices u, v, w for which $\delta (u)=1, \delta (v)=1$, and $uw, vw \in E(G-F-\{e\})$. There are $k-1$ faults adjacent to u and another disjoint $k-1$ faults adjacent to v in G. The vertex e can be adjacent or incident to at most two of the faults adjacent or incident to either u or v, so an additional $k-2$ faults are adjacent or incident to e. Then $|F|\ge 3k-4$, and $3k-4 > 2k-2$ for $k\ge 3$, so this construction can not be made.

Finally, we prove the base case result on $B_3$ using a computer check.

Lemma 5

$cfsmp(B_3)=4$. Moreover, every optimal CFSMP set of $B_3$ is trivial, that is, $B_3$ is fractional strongly super matched.

Proof

This was verified by computer check. Due to the relatively small size of the minimum CFSMP set and the graph $B_3$, this was checked in about 1 day on a conventional computer. The program was written in Python and used the NetworkX package for graph analysis and the SciPy package for a linear program solver to check for fractional perfect matchings. The verification was completed by looping through all possible fault sets on $B_3$ of size 4. After optimizing for vertex transitivity, there are 1, 302, 609 such fault sets.

We remark that a similar result for $P_5$ likely exists; however, due to the size of the graph, the linear optimization problem requires much longer to compute for each fault set case, and there are more cases for fault sets. This may be feasible by using a computer cluster.

4 The Main Results

First we note the following result.

Theorem 5

[19] Let H be a ($k-1$)-regular graph with $k\ge 4$. Let G be a k-regular graph constructed from at least three copies of H by adding edges between the copies, such that G satisfies the following properties: (i) each vertex is incident to exactly one cross edge, and (ii) the cross neighbours of two adjacent vertices in a copy of H are in different copies. Then if H is fractional strongly super matched, G is fractional strongly super matched.

Although this theorem states that G must be composed of copies of H, the proof of this theorem does not actually require every subgraph to be isomorphic. Thus, we restate the theorem as follows.

Theorem 6

Let $H_1, H_2, \ldots , H_n$ be a set of ($k-1$)-regular graphs with $k\ge 4$ and $n\ge 3$. Let G be a k-regular graph constructed from all $H_i$ with $1\le i \le n$ by adding edges between the subgraphs, such that G satisfies the following properties: (i) each vertex is incident to exactly one cross edge, and (ii) the cross neighbours of two adjacent vertices in any $H_i$ are in different copies for $1\le i \le n$. Then if every $H_1, H_2, \ldots , H_n$ is fractional strongly super matched, G is fractional strongly super matched.

This modified theorem allows us to extend our main result from burnt pancake graphs to pancake-like graphs.

In this section, we use the same notation as in the previous sections, but in a more general context. Suppose G is a graph constructed from disjoint copies of a graph H by adding edges between the copies. If uv is an edge joining two vertices from different copies of H, we call it a cross edge, and say u and v are cross neighbours.

Theorem 7

Let $H_1, H_2, \ldots , H_n$ be a set of ($k-1$)-regular graphs with $k\ge 4$ and $n\ge 3$, and girth at least 5. Let G be a k-regular graph constructed from all $H_i$ with $1\le i \le n$ by adding edges between the subgraphs, such that G satisfies the following properties: (i) each vertex is incident to exactly one cross edge, and (ii) the cross neighbours of two adjacent vertices in a copy of H are in different copies. Then if every $H_1, H_2, \ldots , H_n$ is fractional strongly super matched and conditionally fractional strongly super matched, G is fractional strongly super matched and conditionally fractional strongly super matched.

We omit the proof in this extended abstract due to a space constraint. The proof is long and technical, involving a careful case analysis based on the distribution of faults in the substructures based on the recursive properties and other properties that we have developed here.

5 Conclusion

We apply Theorem 7 inductively to $B_n$, given Proposition 3 and Theorem 4 along with the base case Lemma 5 to complete the proof of Theorem 1.

We also note that Theorem 2 is a direct restatement of Theorem 7, and is thus proven.

Because the conditional fractional matching preclusion number must be greater than or equal to the conditional fractional strong matching preclusion number, it is not necessary to separately consider this problem for the burnt pancake graph or the subset of pancake-like graphs we described.