The Strong Spectral Property of Graphs: Graph Operations and Barbell Partitions

Abstract

The utility of a matrix satisfying the Strong Spectral Property has been well established particularly in connection with the inverse eigenvalue problem for graphs. More recently the class of graphs in which all associated symmetric matrices possess the Strong Spectral Property (denoted ${\mathcal {G}}^\textrm{SSP}$) were studied, and along these lines we aim to study properties of graphs that exhibit a so-called barbell partition. Such a partition is a known impediment to membership in the class ${\mathcal {G}}^\textrm{SSP}$. In particular we consider the existence of barbell partitions under various standard and useful graph operations. We do so by considering both the preservation of an already present barbell partition after performing said graph operations as well as barbell partitions which are introduced under certain graph operations. The specific graph operations we consider are the addition and removal of vertices and edges, the duplication of vertices, as well as the Cartesian products, tensor products, strong products, corona products, joins, and vertex sums of two graphs. We also identify a correspondence between barbell partitions and graph substructures called forts, using this correspondence to further connect the study of zero forcing and the Strong Spectral Property.

1 Introduction

The inverse eigenvalue problem of a graph (IEPG) refers to determining all possible spectra of real symmetric matrices whose pattern of nonzero off-diagonal entries is described by the edges of a given graph (see [5, 7, 8, 10]).

Studies on the IEPG have focused on topics such as: determining the maximum eigenvalue multiplicity, or equivalently, maximum nullity, or equivalently again, minimum rank of matrices described by the graph. Computing the maximum multiplicity in general remains unresolved and an active area of research (see [7, 8] for extensive bibliographies). More recently, there has been progress on the related question of determining the minimum number of distinct eigenvalues of matrices described by a given graph [1, 4].

Maximum nullity, minimum number of distinct eigenvalues, and other related notions help to resolve instances of the inverse eigenvalue problem for a specific graph or family of graphs, but a general solution is far from known. Recently, new developments building upon a known matrix property called the Strong Arnold Property (see [3, 13, 14]), known as the Strong Spectral Property (SSP) and the Strong Multiplicity Property (SMP), have been used in connection with the IEPG [4, 5] and seem to be promising tools for working on the IEPG in more general terms.

All matrices are real and symmetric; O and I denote zero and identity matrices of appropriate size, respectively. A symmetric matrix A has the Strong Arnold Property (or A has the SAP for short) if the only symmetric matrix X satisfying $A\circ X=O$, $I\circ X=O$ and $AX=O$ is $X=O$ (recall that product $\circ$ is the entry-wise matrix product). An $n \times n$ symmetric matrix A satisfies the Strong Multiplicity Property (or A has the SMP) provided the only symmetric matrix X satisfying $A\circ X=O$, $I\circ X=O$, $[A,X]=O$, and ${{\,\textrm{tr}\,}}(A^iX)=0$ for $i=2,\ldots , n-1$ is $X=O$ [4, Definition 18 and Remark 19]. A symmetric matrix A has the Strong Spectral Property (or A has the SSP) if the only symmetric matrix X satisfying $A\circ X=O$, $I\circ X=O$ and $[A,X]=O$ is $X=O$ [4, Definition 8]. It follows from the definitions above that the SSP implies the SMP, and the SMP implies $A+\lambda I$ has the SAP for every real number $\lambda$ (see [4, 5]).

The graph ${\mathcal {G}}(A)$ of a real symmetric $n\times n$ matrix $A=[a_{ij}]$ is the (simple, undirected, finite) graph with vertices $\{1,\ldots ,n\}$ and edges ij such that $i\ne j$ and $a_{ij} \ne 0$. For a graph $G=(V,E)$ with vertex set $V=\{1,\ldots ,n\}$ and edge set E, the set of symmetric matrices described by G, ${\mathcal {S}}(G)$, is the set of all real symmetric $n \times n$ matrices $A=[a_{ij}]$ such that ${\mathcal {G}}(A)=G$. The IEPG for G asks for the determination of all possible spectra of matrices in ${\mathcal {S}}(G)$. The number of distinct eigenvalues of A is denoted by q(A), and $q(G) = \min \{q(A)\; \text{: }\; A \in {\mathcal {S}}(G)\}$.

Given a graph $G=(V,E)$, and $S\subset V$, we let $N_{G}(S)$ denote the set of all vertices adjacent to some vertex in S. In particular, if v is a vertex of a graph G, the neighborhood of v is the set of vertices adjacent to v, and is denoted by $N_G(v)$. Likewise, the closed neighborhood of v and the closed neighborhood of S, denoted $N_G [v]$ and $N_G [S]$ respectively, are the sets of vertices $N_G (v)\cup \{v\}$ and $N_G (S)\cup S$. Further, the degree of v, denoted by $\deg (v)$, is equal to $\big |N_G(v)\big |$. If $S \subseteq V$, then we let G[S] denote the subgraph of G induced by the vertices in G (sometimes referred to as the vertex induced subgraph of G). An edge e in G with end points u and v is denoted by $e=\{u,v\}$ of for brevity we may just write $uv\in E(G)$. We let $G \pm e$ denote the graph obtained from G by adding a new edge e or by removing the existing edge e from G. Similarly, if $S\subseteq V$, we let $G-S$ denote the induced subgraph of G obtained by removing S from V. If $S=\{v\}$, we use abbreviation $G-v$ to denote the graph obtained from G by removing the vertex v. If G and H are two graphs, then the join of G and H, denoted by $G \vee H$, is the graph obtained from the disjoint union of G and H and adding all possible edges between the vertices in G and the vertices in H. Finally, as is standard, we let $K_n$ and $P_n$, $n\ge 1$, and $C_n$, $n\ge 3$, denote the complete graph, the path graph, and the cycle on n vertices, respectively.

Suppose G is a given graph and v is a fixed vertex in G. The notion of duplicating (or cloning) a vertex is a natural graph operation and has interesting implications on the inverse eigenvalue problem for graphs (see [2, 11]). There are two versions of duplicating a vertex, namely with an edge or without an edge. The graph jdup(G, v) (dup(G, v)) is the graph obtained from G by adding a new vertex u and connecting u to all the vertices in $N_{G}(v)$ and v (connecting u to all the vertices in $N_{G}(v)$).

The main focus of this work is to study when the SSP is preserved under certain standard graph operations. One inherent flaw with this approach is that the SSP is a matrix property and not necessarily a graph property. As such, we are very interested in the graphs G for which the SSP holds for all $A \in {\mathcal {S}}(G)$. This class is denoted by ${\mathcal {G}}^\textrm{SSP}$ and was introduced in [12]. The analogous classes for SAP and SMP are respectively denoted ${\mathcal {G}}^\textrm{SAP}$ and ${\mathcal {G}}^\textrm{SMP}$. In [12], the concept of a barbell partition was noted and a connection to the complement of the class ${\mathcal {G}}^\textrm{SSP}$ was established. In this paper, we work with barbell partitions extensively and work out numerous relationships regarding barbell partitions and standard graph operations. Such analysis leads to a better understanding of graphs that do not belong to the set ${\mathcal {G}}^\textrm{SSP}$. In Sect. 2 of this work we recall the definition of barbell partitions and verify classes of graphs that exhibit barbell partitions. In the remaining sections (Sects. 3–5) we discuss the preservation of barbell partitions under various graph operations and graph products.

Concerning graphs G and the class ${\mathcal {G}}^\textrm{SSP}$, it is known that the cycle on 4 or more vertices does not belong to the class ${\mathcal {G}}^\textrm{SSP}$. On the other hand it is also known (see [6]) that for the 4-cycle any realizable multiplicity list can be realized by a matrix with the SSP. However, for any n-cycle it is still not clear if every realizable multiplicity list can be realized by a matrix with the SSP. As a matter of pushing the narrative a bit further we end the introduction with an example of a class of matrices in $S(C_n)$ with n even that possess the SSP.

Proposition 1.1

For $A \in {\mathcal {S}}(C_n)$, if n is even and $0 \ne \lambda = a_{11} = \cdots = a_{\frac{n}{2}\frac{n}{2}}$, $0 \ne -\lambda = a_{\frac{n}{2}+1 \frac{n}{2}+1} = \cdots = a_{nn}$, and all other entries in A are a common value $b \ne 0$, then A has the SSP.

Proof

Suppose $A \in S(C_n)$ such that n is even and

$$\begin{aligned} A = \begin{bmatrix} \lambda &{} b &{} 0 &{} 0 &{} 0 &{} \cdots &{} 0 &{} \cdots &{} 0 &{} b\\ b &{} \lambda &{} b &{} 0 &{} 0 &{} \cdots &{} 0 &{} \cdots &{} 0 &{} 0\\ 0 &{} b &{} \lambda &{} b &{} 0 &{} \cdots &{} 0 &{} \cdots &{} 0 &{} 0\\ \vdots &{} \ddots &{} \ddots &{} \ddots &{} \ddots &{} \cdots &{} \vdots &{} \cdots &{} \vdots &{} \vdots \\ 0 &{} 0 &{} \cdots &{} b &{} \lambda &{} b &{} 0 &{} \cdots &{} 0 &{} 0\\ 0 &{} 0 &{} \cdots &{} 0 &{} b &{} -\lambda &{} b &{} \cdots &{} 0 &{} 0\\ \vdots &{} \vdots &{} \cdots &{} \vdots &{} \ddots &{} \ddots &{} \ddots &{} \ddots &{} \vdots &{} \vdots \\ 0 &{} \cdots &{} \cdots &{} \cdots &{} \cdots &{} 0 &{} b &{} -\lambda &{} b &{} 0\\ 0 &{} \cdots &{} \cdots &{} \cdots &{} \cdots &{} \cdots &{} 0 &{} b &{} -\lambda &{} b\\ b &{} \cdots &{} \cdots &{} \cdots &{} \cdots &{} \cdots &{} \cdots &{} 0 &{} b &{} -\lambda \\ \end{bmatrix} \end{aligned}$$

such that $\lambda$ and b are real numbers such that $\lambda , b \ne 0$. Consider an $n \times n$ real symmetric matrix $X=[x_{ij}]$ such that: (1) $A \circ X = O$, (2) $X \circ I = O$, and (3) $AX = XA$. Then $XA = AX$, yields the equations $bx_{13} = \cdots = bx_{kk+2} = bx_{k+1 k -1} = \cdots = bx_{n2}$ along the super and sub diagonals and in the entry in the (1, n) and (n, 1) positions. Since $b \ne 0$, this yields that $x_{13} = \cdots = x_{k k+2} = x_{k+1 k - 1} = \cdots = x_{n2}$. Considering the next two diagonals and entries in positions $(1,n-1)$, (2, n), $(n-1,1)$, and (n, 2) yields the equations $0 = x_{13} = \cdots = x_{k k+2} = x_{k+1 k -1} = \cdots = x_{n2}$. Continuing the argument in this manner will show that $X=0$ and hence A has the SSP. $\square$

2 Barbell Partitions

We now turn our attention to the interesting class of graphs that do not belong to ${\mathcal {G}}^\textrm{SSP}$. In connection with the class of graphs that do not belong to ${\mathcal {G}}^\textrm{SSP}$ (see [12]), we consider the notion of a barbell partition of the vertex set. For our purposes, given a set U we will consider a partition of U to be a collection of pairwise disjoint subsets of U such that their union is U. The subsets can be empty. The concept of barbell partition is defined in [12].

Definition 2.1

A barbell partition of a graph G is a partition of V(G) into three disjoint parts $\{R,W_1,W_2\}$ such that:

• 1. R is allowed to be an empty set, but $W_i \ne \emptyset$ for $i \in \{1,2\}$

• 2. there are no edges between vertices in $W_1$ and vertices in $W_2$

• 3. for each $v \in R$, $\big | N_G(v) \cap W_i \big | \ne 1$ for $i \in \{1,2\}$.

It was then shown that if a graph G has a barbell partition, then $G \not \in {\mathcal {G}}^\textrm{SSP}$.

Lemma 2.2

[12] Let G be a graph with a barbell partition. Then there is a matrix $M \in {\mathcal {S}}(G)$ such that M does not have the SAP (and the SSP).

It thus follows that any graph with a barbell partition is not a member of ${\mathcal {G}}^\textrm{SSP}$, ${\mathcal {G}}^\textrm{SAP}$, or ${\mathcal {G}}^\textrm{SMP}$. Our results concerning barbell partitions will often conclude that a graph is not a member of ${\mathcal {G}}^\textrm{SSP}$. However, in each such case, it can also be said that the graph in question is neither a member of ${\mathcal {G}}^\textrm{SAP}$ nor of ${\mathcal {G}}^\textrm{SMP}$. We observe, for completeness, that the converse to the previous lemma need not hold in general. Consider the cycle on 4 vertices with two additional pendant vertices adjacent to non-adjacent vertices on this 4-cycle. This graph is not in ${\mathcal {G}}^\textrm{SSP}$ and does not have a barbell partition (see also [12]).

As a result, it becomes natural to discuss barbell partitions when considering SSP. To this end, the remaining sections will focus on classes of graphs which have barbell partitions and graph operations which preserve the presence of barbell partitions or in some cases introduce barbell partitions. Furthermore, in [9] the concept of a fort was introduced and defined to be a subset of a graph’s vertices such that no vertex not in the fort is adjacent to exactly one vertex in the fort. For the purposes of this paper, we will follow the convention that every nontrivial graph G has a fort, specifically V(G), with the criterion in the definition being understood to be vacuously true in this case. The following theorem establishing the connection between forts and zero forcing (see [8] for more details about zero forcing) follows from [9, Thm. 3].

Theorem 2.3

[9] Let G be a graph and $S \subseteq V(G)$. Then $V(G) - S$ is a zero forcing set of G if and only if S does not contain a fort.

The definition and results concerning forts are worth noting because while the original definition of barbell partitions does not mention forts, one can define barbell partitions utilizing the concept of forts thus creating a connection between the two areas of study. With this in mind, we first introduce the concept of a pair of separated forts and then identify that this concept can provide an equivalent definition for barbell partitions.

Definition 2.4

Let G be a graph. If $W_1$ and $W_2$ are disjoint nonempty forts in G and no vertex in $W_1$ is adjacent to a vertex in $W_2$, then we say that $\{W_1,W_2\}$ is a pair of separated forts.

Observation 2.5

Let G be a graph. Then $\{V(G) {\setminus } (W_1 \cup W_2),W_1,W_2\}$ is a barbell partition of G if and only if $\{W_1,W_2\}$ is a pair of separated forts of G.

We begin our discussion of barbell partitions by providing a list of small observations which will prove useful later on.

Observation 2.6

If a graph G is disconnected, then one can construct a barbell partition $\{R,W_1,W_2\}$ of G by letting H be a component of G and setting $W_1=V(H)$, $W_2=V(G){\setminus } V(H)$, and $R=\emptyset$.

Proof

By construction $W_1$ and $W_2$ are nonempty, and since $W_1$ and $W_2$ form a partition of the connected components of G, there are no edges between vertices in $W_1$ and $W_2$. Finally, since R is empty, that for each $v \in R$, $\big | N_G(v) \cap W_i \big | \ne 1$ for $i \in \{1,2\}$ follows vacuously. $\square$

Observation 2.7

If G is a graph such that

• S is a vertex cut of G

• ${\mathcal {H}}$ is the collection of components of $G-S$ and

• for $H \in {\mathcal {H}}$,

  $$\begin{aligned} v \in N_G\left( V(H)\right) \cap S \Longrightarrow \big | N_G(v) \cap V(H) \big | \ge 2, \end{aligned}$$

then G has a barbell partition with $R=S$, $W_1=V(H')$ for some $H' \in {\mathcal {H}}$, and $W_2=\left( \bigcup _{H \in {\mathcal {H}}}V(H)\right) {\setminus } V(H')$, and thus must not be in ${\mathcal {G}}^\textrm{SSP}$.

In an effort to develop a catalog of graphs that are excluded from the class ${\mathcal {G}}^\textrm{SSP}$, we are interested in graphs that admit a barbell partition. On the other hand, we have the following graph structural result regarding the nonexistence of a barbell partition.

Lemma 2.8

Let G be a connected graph with diameter 2 and maximum degree 3. Then G does not admit a barbell partition.

Proof

Let $W_1,W_2 \subseteq V(G)$ be arbitrary nonempty sets of vertices such that no vertex in $W_1$ is adjacent to a vertex in $W_2$. Let $R=V(G) {\setminus }(W_1 \cup W_2)$. Since G is connected, R is nonempty. We will show that there exists a vertex $r \in R$ such that for some $i \in \{1,2\}$, $\big |N_G(r) \cap W_i\big |=1$.

Let $w_1 \in W_1$ and $w_2 \in W_2$. Since G is connected and of diameter 2 there exists a $w_1w_2$-path of length 2. However, since there are no edges between vertices in $W_1$ and vertices in $W_2$ and this path is of length 2, the middle vertex in this $w_1w_2$-path must be a member of R, call it r. Since r is neighbors with $w_1$ and $w_2$, but G has maximum degree 3, r has at most one other neighbor. Thus, for some $i \in \{1,2\}$, $\big |N_G(r)\cap W_i\big |=1$. $\square$

Corollary 2.9

The Petersen graph, P,  does not admit a barbell partition.

Proof

P is 3-regular and has diameter 2, so by Lemma 2.8, P does not admit a barbell partition. $\square$

It is necessary that the graph in Lemma 2.8 has all three properties, that is be connected, maximum degree 3, and have diameter 2. As stated in a previous theorem, every disconnected graph admits a barbell partition, and in the diagram below we provide an example of a graph of diameter 2 and a 3-regular graph which each admit barbell partitions (Fig. 1).

Fig. 1

A 3-regular graph and a graph of diameter 2 each of which are connected but admit a barbell partition. The colors green, red, and blue represent $R, W_1$, and $W_2$, respectively (color figure online)

3 Barbell Partitions and the Removal or Addition of Edges or Vertices

Having identified some classes of graphs admitting barbell partitions, we now consider the effect basic graph operations such as adding or removing vertices or edges have on the presence of barbell partitions. We first consider the effect of adding or removing an edge.

Observation 3.1

Let G be a graph and $R,W_1,W_2$ be a partition of the vertices of G with $W_1, W_2 \ne \emptyset$ such that no vertex in $W_1$ is adjacent to a vertex in $W_2$. Let $e=\{u,v\} \in E(G)$ with $u,v \in W_i$ for some $i \in \{1,2\}$ or $u,v \in R$. Then $\{R,W_1,W_2\}$ is a barbell partition of G if and only if $\{R,W_1,W_2\}$ is a barbell partition of $G-e$.

Since the pair of vertices u and v are in the same element of the partition, the presence or lack of the edge $e=\{u,v\}$ has no effect on any of the three criteria determining whether $\{R,W_1,W_2\}$ is a barbell partition or not.

Observation 3.2

Let G be a graph admitting a barbell partition $\{R,W_1,W_2\}$, let $u \in R$, let $v \in W_{i}$ for some $i \in \{1,2\}$, and let $e=\{u,v\} \in E(G)$. Then $G-e$ admits a barbell partition provided $\big | N_G(u) \cap W_{i} \big |>2$.

In this second case, the removal of e only effects the number of neighbors $u \in R$ has in $W_{i}$, and since $\big | N_G(u) \cap W_{i} \big |>2$, $\{R, W_1, W_2\}$ is still a barbell partition of $G-e$. The effect of adding an edge is quite similar and we have the following.

Observation 3.3

Let G be a graph admitting a barbell partition $\{R,W_1,W_2\}$, let $u \in R$, let $v \in W_{i}$ for $i \in \{1,2\}$, and let $e=\{u,v\} \not \in E(G)$. Then $G+e$ admits a barbell partition provided $\big | N_G(u) \cap W_{i} \big | \ge 2$.

The lollipop graph, $L_{n,l}$ for $n\ge 2$ and $l\ge 1$, is defined to be a complete graph $K_n$ together with a path $P_l$ such that a leaf of $P_l$ and a vertex of $K_n$ are adjacent, and no other extra edges between the vertices of $K_n$ and $P_l$ exist. In [12] it is shown that $L_{n,l} \in {\mathcal {G}}^\textrm{SSP}$.

Proposition 3.4

If the pendant vertex of the lollipop graph $L_{n,1}$ is duplicated without an edge (call the new graph G), and $A\in {\mathcal {S}}(K_n)$ then the SSP is preserved for $B \in {\mathcal {S}}(G)$ such that

$$\begin{aligned} B = \begin{bmatrix} A &{} \mathrm{\textbf{e}}_{n} &{} \mathrm{\textbf{e}}_{n}\\ \mathrm{\textbf{e}}_{n}^T &{} \mu _1 &{} 0\\ \mathrm{\textbf{e}}_{n}^T &{} 0 &{} \mu _2\\ \end{bmatrix}, \end{aligned}$$

where $\mu _1 \ne \mu _2 \in {\mathbb {R}}$ and $\mathrm{\textbf{e}}_n$ represents a standard basis vector with a 1 in the nth coordinate.

Proof

From the first two requirements of the SSP, symmetric X such that $B \circ X = O$ and $I \circ X = O$ yields that

$$\begin{aligned} X = \begin{bmatrix} O &{} {\textbf {x}}_1 &{} {\textbf {x}}_2\\ {\textbf {x}}_1^T &{} 0 &{} y\\ {\textbf {x}}_2^T &{} y &{} 0\\ \end{bmatrix}, \end{aligned}$$

where $y \in {\mathbb {R}}$ and the nth coordinate of ${\textbf {x}}_j$ is necessarily 0 for $j=1,2$. Then, the third condition yields $BX = XB$ where

$$\begin{aligned} BX= & {} \begin{bmatrix} A &{} {\textbf {e}}_{n} &{} {\textbf {e}}_{n}\\ {\textbf {e}}_{n}^T &{} \mu _1 &{} 0\\ {\textbf {e}}_{n}^T &{} 0 &{} \mu _2\\ \end{bmatrix} \begin{bmatrix} O &{} {\textbf {x}}_1 &{} {\textbf {x}}_2\\ {\textbf {x}}_1^T &{} 0 &{} y\\ {\textbf {x}}_2^T &{} y &{} 0\\ \end{bmatrix} = \begin{bmatrix} {\textbf {e}}_{n}{} {\textbf {x}}_1^T + {\textbf {e}}_{n}{} {\textbf {x}}_2^T &{} A{\textbf {x}}_1+y{\textbf {e}}_{n} &{} A{\textbf {x}}_2+y{\textbf {e}}_{n}\\ \mu _1{\textbf {x}}_1^T &{} {\textbf {e}}_{n}^T{\textbf {x}}_1 &{} {\textbf {e}}_{n}^T{\textbf {x}}_2+\mu _1y\\ \mu _2{\textbf {x}}_2^T &{} {\textbf {e}}_{n}^T{\textbf {x}}_1+\mu _2y &{} {\textbf {e}}_{n}^T {\textbf {x}}_2\\ \end{bmatrix}\\ XB= & {} \begin{bmatrix} O &{} {\textbf {x}}_1 &{} {\textbf {x}}_2\\ {\textbf {x}}_1^T &{} 0 &{} y\\ {\textbf {x}}_2^T &{} y &{} 0\\ \end{bmatrix}\begin{bmatrix} A &{} {\textbf {e}}_{n} &{} {\textbf {e}}_{n}\\ {\textbf {e}}_{n}^T &{} \mu _1 &{} 0\\ {\textbf {e}}_{n}^T &{} 0 &{} \mu _2\\ \end{bmatrix} = \begin{bmatrix} {\textbf {x}}_1{\textbf {e}}_{n}^T + {\textbf {x}}_2{\textbf {e}}_{n}^T &{} \mu _1{\textbf {x}}_1 &{} \mu _2{\textbf {x}}_2\\ {\textbf {x}}_1^TA+y{\textbf {e}}_{n}^T &{} {\textbf {x}}_1^T{\textbf {e}}_{n} &{} {\textbf {x}}_1^T{\textbf {e}}_{n}+\mu _2y\\ {\textbf {x}}_2^TA+y{\textbf {e}}_{n}^T &{} {\textbf {x}}_2^T{\textbf {e}}_{n}+\mu _1y &{} {\textbf {x}}_2^T{\textbf {e}}_{n}\\ \end{bmatrix}. \end{aligned}$$

Simplifying:

$$\begin{aligned} \begin{bmatrix} {\textbf {e}}_{n}{} {\textbf {x}}_1^T + {\textbf {e}}_{n}{} {\textbf {x}}_2^T &{} A{\textbf {x}}_1+y{\textbf {e}}_{n} &{} A{\textbf {x}}_2+y{\textbf {e}}_{n}\\ \mu _1{\textbf {x}}_1^T &{} 0&{} 0+\mu _1y\\ \mu _2{\textbf {x}}_2^T &{} 0+\mu _2y &{} 0\\ \end{bmatrix} = \begin{bmatrix} {\textbf {x}}_1{\textbf {e}}_{n}^T + {\textbf {x}}_2{\textbf {e}}_{n}^T &{} \mu _1{\textbf {x}}_1 &{} \mu _2{\textbf {x}}_2\\ {\textbf {x}}_1^TA+y{\textbf {e}}_{n}^T &{} 0&{} 0+\mu _2y\\ {\textbf {x}}_2^TA+y{\textbf {e}}_{n}^T &{} 0+\mu _1y &{} 0\\ \end{bmatrix}. \end{aligned}$$

Comparing the (2,3) blocks above we conclude that $y=0$. Further, ${\textbf {x}}_1{\textbf {e}}_{n}^T + {\textbf {x}}_2{\textbf {e}}_{n}^T = {\textbf {e}}_{n}{} {\textbf {x}}_1^T + {\textbf {e}}_{n}{} {\textbf {x}}_2^T$, together with $({\textbf {x}}_1)_{n}=({\textbf {x}}_2)_n=0$, imply $-({\textbf {x}}_1)_{j} = ({\textbf {x}}_2)_{j}$, where $1 \le j \le n$ and $j \ne i$. Hence ${\textbf {x}}_1$ is a multiple of ${\textbf {x}}_2$. Now comparing the (1,2) and the (1,3) blocks above we may conclude that ${\textbf {x}}_1= {\textbf {x}}_2=0$. Hence, $X = O$. $\square$

We next turn our attention to the duplication or removal of a vertex.

Observation 3.5

Let G be a graph admitting a barbell partition $\{R, W_1, W_2\}$, and let $S \subset V(G)$. If $S \subseteq R$, then $G-S$ admits a barbell partition.

The next observation is immediate because when a vertex and its neighborhood lie in the same element of the barbell partition none of the criteria are effected by removing the vertex. The subsequent observation follows since $\{ R\cup \{ v\}, W_1, W_2\}$ will be a barbell partition of H.

Observation 3.6

Let G be a graph admitting a barbell partition $\{R, W_1, W_2\}$, and suppose $G=H-v$. If $N_H(v) \subset X$ for some $X \in \{R,W_1,W_2\}$, then H admits a barbell partition.

Observation 3.7

Let G be a graph admitting a barbell partition $\{R, W_1, W_2\}$, and suppose $G=H-v$. If for each $i \in \{1,2\}$, $\big | N_H(v) \cap W_i \big | \ne 1$, then H admits a barbell partition.

Observation 3.8

Let G be a graph admitting a barbell partition $\{R, W_1, W_2\}$, and suppose $G=H-v$. If for some $i \in \{1,2\}$, we have that for every $u \in R \cap N_H(v)$, $\big | N_G(u) \cap W_i \big | \ge 2$ and $N_H(v) {\setminus } (R \cup W_i)=\emptyset$, then H admits a barbell partition.

Supposing without loss of generality that the i mentioned in the above observation is 1, then letting $W_1'=W_1 \cup \{v\}$ it follows that $\{R,W_1',W_2\}$ is a barbell partition of H.

Having considered the effect of adding or removing vertices or edges on the presence of barbell partitions of a graph, we now consider the more specific graph operation of vertex duplication and provide results establishing the interaction between barbell partitions and vertex duplication.

Theorem 3.9

Let G be a graph admitting a barbell partition and $v \in V(G)$. Let $H=dup(G,v)$ and let $K=jdup(G,v)$. Then both H and K admit barbell partitions, and in particular neither graph is a member of ${\mathcal {G}}^\textrm{SSP}$.

Proof

Let u be the duplication of v, and let $\{R,W_1,W_2\}$ be a barbell partition of G.

Case 1 $v \in R$.

Since $v \in R$, it follows that $\big |N_G(v) \cap W_i\big | \ne 1$ for each $i \in \{1,2\}$. Since $N_H(u)=N_G(v)$ and $N_K(u)=N_G[v]$, it follows that $\big |N_H(u) \cap W_i\big |=\big |N_K(u) \cap W_i\big | \ne 1$ for each $i \in \{1,2\}$. Thus, by Observation 3.7, H and K each have barbell partitions, specifically $\{R',W_1, W_2\}$ with $R'=R \cup \{u\}$.

Case 2 There exists $i \in \{1,2\}$ such that $v \in W_i$.

Without loss of generality, let $i=1$. So, $N_G[v] \cap W_2=\emptyset$. Again, since $N_H(u)=N_G(v)$, it follows that $N_H(u) \cap W_2=\emptyset$. Since $v \in W_1$, for every $r \in R \cap N_G(v)$, $\big | N_G(r) \cap W_1 \big | \ge 2$. So, for every $r \in R \cap N_H(u)$, $\big | N_H(r) \cap W_1 \big | \ge 3$. Thus, by Observation 3.8, H has a barbell partition, specifically $\{R,W'_1, W_2\}$ with $W_1'=W_1 \cup \{u\}$.

Since $N_K(u)=N_G[v]$, by similar reasoning K has a barbell partition. $\square$

Note: The converse of Theorem 3.9 is not true. For example, $K_{1,3}$ does not admit a barbell partition, but both duplicating and join-duplicating a leaf will yield a graph which admits a barbell partition. This observation inspires the following results.

We now explore a little further the connection between forts in a graph and barbell partitions, both concepts, of course, are of interest to the IEPG.

Lemma 3.10

Let G be a graph, let $v \in V(G)$, and let $G'$ be the graph yielded by (join) duplicating v. Then $\{v,v'\}$ is a fort of G.

Proof

Since no vertex outside of $N_G[v]$ is neighbors with $v'$ and vice versa, $\{v,v'\}$ is a fort of $G'$. $\square$

Lemma 3.11

Let G be a graph. G contains a fort F for which $N_G[F]$ is not a zero forcing set of G if and only if G admits a barbell partition.

Proof

First suppose $F \subset V(G)$ is a fort of G such that $N_G[F]$ is not a zero forcing set of G. By Theorem 2.3, $V(G) {\setminus } N_G[F]$ contains a fort of G, call it $F'$. Since $F' \subseteq V(G){\setminus } N_G[F]$, $F \cap F'=\emptyset$ and there do not exist vertices $v,v' \in V(G)$ such that $v \in F$, $v \in F'$, and $vv' \in E(G)$. So by Observation 2.5, $\{R,F,F'\}$ forms a barbell partition of G, where $R=V(G){\setminus } (F \cup F')$.

Now suppose $\{R,W_1,W_2\}$ is a barbell partition of G. By Observation 2.5, $\{W_1,W_2\}$ is a pair of separated forts. Since $W_1$ and $W_2$ are separated, $N_G[W_1] \cap W_2 =$. Thus $G {\setminus } N_G[W_1]$ contains a fort and by Theorem 2.3, $N_G[W_1]$ is not a zero forcing set of G. $\square$

Observation 3.12

Let G be a graph and H be a vertex induced subgraph of G. If $S \subsetneq V(H)$ does not contain a fort of H, then S does not contain a fort of G.

Theorem 3.13

Let G be a graph which does not admit a barbell partition. Let $v \in V(G)$, and let $G'$ be the graph yielded by (join) duplicating v. Then $G'$ admits a barbell partition if and only if $V(G) {\setminus } N_G[v]$ contains a fort of G.

Proof

First suppose $V(G){\setminus }N_G[v]$ contains a fort of G, call it F. Let $v'$ be the new vertex that duplicates v. Note, by Lemma 3.10, $\{v,v'\}$ is a fort of $G'$. Next, since $F \subseteq V(G) {\setminus } N_G[v]$ and $N_{G'}(v') \subseteq N_G[v]$, it follows that $N_{G'}[v'] \cap F=\emptyset$ and so F is a fort of $G'$ contained in $V(G'){\setminus }N_{G'}[\{v,v'\}]$. So by Theorem 2.3, $N_{G'}[\{v,v'\}]$ is not a zero forcing set of $G'$. Thus by Lemma 3.11, $G'$ admits a barbell partition.

Next, suppose $V(G){\setminus }N_G[v]$ does not contain a fort of G. If $G'$ does not have a pair of separated forts, then we are done, so, suppose that $G'$ has a pair of separated forts, $\{F_1,F_2\}$. Since $V(G) {\setminus } N_G[v]$ does not contain a fort of G, by Observation 3.12, $V(G') {\setminus } N_{G'}[\{v,v'\}]$ does not contain a fort of $G'$. So, any fort of $G'$ must contain a member of $N_{G'}[\{v,v'\}]$. Let $N=N_{G'}[\{v,v'\}]\setminus \{v,v'\}$, and note that $N=N_G(v)$.

Case 1 Either $F_1 \cap \{v,v'\} \ne \emptyset$ and $F_2 \cap N \ne \emptyset$ or $F_1 \cap N \ne \emptyset$ and $F_2 \cap \{v,v'\} \ne \emptyset$.

Then there exist vertices $u_1 \in F_1$ and $u_2 \in F_2$ such that $u_1u_2 \in E(G')$, and so $\{F_1,F_2\}$ is not a pair of separated forts of $G'$, a contradiction.

Case 2  $F_i \cap N \ne \emptyset$ and $F_i \cap \{v,v'\} = \emptyset$, for each $i \in \{1,2\}$.

Then $\{F_1,F_2\}$ is a pair of separated forts in $G'$ if and only if $\{F_1,F_2\}$ is a pair of separated forts in G. Since G does not admit a barbell partition, $\{F_1,F_2\}$ is not a pair of separated forts of $G'$, a contradiction.

Case 3 $F_i \cap \{v,v'\} \ne \emptyset$ and $F_i \cap N = \emptyset$, for each $i \in \{1,2\}$.

Let $F=(F_1 \cup F_2){\setminus }\{v,v'\}$. To reach our contradiction we will show that F is a fort contained in $G {\setminus } N_G[v]$. First, since $F_1 \cap F_2 = \emptyset$ but $F_i \cap \{v,v'\} \ne \emptyset$, for each $i \in \{1,2\}$, it must be that a unique element of $\{v,v'\}$ is a member of $F_1$ and that the other element is a member of $F_2$. Suppose without loss of generality that $v \in F_1$ and $v' \in F_2$. Since $\{F_1,F_2\}$ is a pair of separated forts of $G'$ it follows that no vertex in $V(G'){\setminus }(F_1 \cup F_2)$ is adjacent to exactly one element of either $F_1$ or $F_2$. Thus no vertex in $V(G') {\setminus } (F_1 \cup F_2)$ is adjacent to exactly one element of $F_1 \cup F_2$. Since $N_{G'}(u)=N_G(u)$ for every vertex $u \in V(G) {\setminus } N_G[v]$, $\big |N_G(u) \cap F\big | \ne 1$ for every vertex $u \in V(G) {\setminus } N_G[v]$. So, it simply remains to check the vertices in the set $N_G[v]$. Since $F_1 \cap N=\emptyset$ but each vertex of N is adjacent to v, each vertex of N must be neighbors with some vertex in $F_1{\setminus }\{v\}$. Likewise, each vertex of N must be neighbors with some vertex in $F_2 {\setminus } \{v'\}$. So each vertex in N must be neighbors with at least two vertices in $(F_1 \cup F_2){\setminus }\{v,v'\}$, and thus each vertex in $N_G(v)$ must be neighbors with at least two vertices in F. Finally, since $(F_1 \cup F_2) \cap N=\emptyset$, it follows that v is not neighbors with any vertex in F. So, for each vertex $u \in V(G) {\setminus } F$, $\big |N_G(u) \cap F\big | \ne 1$. Thus $G {\setminus } N_G[v]$ contains a fort, a contradiction.

In each case we reach a contradiction, and thus $G'$ does not have a pair of separated forts. So by Observation 2.5, $G'$ does not admit a barbell partition completing the proof. $\square$

Proposition 3.14

Let $n \ge 2$. Let $v \in V(P_n)$ be a pendant vertex. Let G be the graph yielded by join duplication of v. Then $G \in {\mathcal {G}}^\textrm{SSP}$.

Proof

If we join duplicate a pendant vertex of $P_n$, then we obtain a graph H with the property that $q(H)=|H|-1$. For this class of graphs it is known that $H \in {\mathcal {G}}^\textrm{SSP}$ (see [12]). $\square$

Theorem 3.15

Let G be a graph and suppose $v \in V(G)$ is a pendant vertex of G. Let $G'$ be the graph yielded by (join) duplicating v. Then $G' \in {\mathcal {G}}^\textrm{SSP}$ if and only if G is a path.

Proof

First, by Proposition 3.14 it follows that if G is a path, then $G' \in {\mathcal {G}}^\textrm{SSP}$.

Now suppose, G is not a path. Since v is a pendant vertex, we can let $N_G(v)=\{u\}$. Since G is not a path and v is a pendant vertex of G, it follows that either $G-v$ is a path and u is not an endpoint of $G-v$ or $G-v$ is not a path. In either case, $\{u\}$ is not a zero forcing set of $G-v$. Thus by Theorem 2.3$V(G-v){\setminus } \{u\}$ contains a fort of $G-v$, call it F. Since $N_G[v]=\{u,v\}$, it follows that F is a fort of G contained in $V(G){\setminus }N_G[v]$. Thus, by Theorem 3.13, $G'$ admits a barbell partition. Finally, it follows that $G' \not \in {\mathcal {G}}^\textrm{SSP}$. $\square$

4 Barbell Partitions, Vertex Sums, and Joins

In this section we consider barbell partitions associated with some standard graph operations (namely, vertex sums and joins), and we begin with the following result concerning a basic necessary condition for the existence of a barbell partition in a graph.

Lemma 4.1

Let G be a graph with no isolated vertices. If $\{R,W_1,W_2\}$ is a barbell partition of G, then $|W_1|,|W_2| \ge 2$.

Proof

Let $w_1 \in W_1$ and $w_2 \in W_2$. First suppose that the component of G containing $w_1$ contains no members of R. Since this means every vertex in this component is either in $W_1$ or $W_2$, it follows that every vertex in this component must be in $W_1$, otherwise there exists vertices u, v with $u \in W_1$, $v \in W_2$, and $uv \in E(G)$ which would imply that $\{R,W_1,W_2\}$ is not a barbell partition of G. Since G has no isolated vertices, there must be another vertex $w_1' \in W_1$ in this component. So, $|W_1| \ge 2$.

Now suppose the component of G containing $w_1$ contains at least one member of R. Since this component is connected and contains members of both R and $W_1$, there must exist a pair of vertices $r \in R$ and $w'_1 \in W_1$ such that $rw'_1 \in E(G)$. Since $\big | N_G(r) \cap W_1 \big | \ne 0$ and $\{R,W_1,W_2\}$ is a barbell partition of H, it follows that $\big | N_G(r) \cap W_1 \big | \ge 2$, and thus $|W_1| \ge 2$.

An identical argument shows that $|W_2| \ge 2$. $\square$

It is of course not necessary for a graph G to not have any isolated vertices for it to admit a barbell partition $\{R,W_1,W_2\}$ for which $|W_1|,|W_2| \ge 2$, as witnessed by the graph G with vertex set $V(G)=\{v_i\}_{i=1}^4$ and edge set $E(G)=\emptyset$. However, this can be viewed as establishing that this property occurs anytime a graph G possesses a barbell partition such that neither $W_1$ nor $W_2$ is a single isolated vertex. It also provides the following biconditional result concerning the interaction between the join of two graphs and barbell partitions.

Theorem 4.2

Let G and H each be graphs with no isolated vertices and $K=G \vee H$. Then K admits a barbell partition, if and only if either G or H admits a barbell partition $\{R,W_1,W_2\}$ for which $|W_1|,|W_2| \ge 2$.

Proof

First suppose $\{R,W_1,W_2\}$ is a barbell partition of H for which $|W_1|,|W_2| \ge 2$, and let $R'=R \cup V(G)$. We will show that $\{R',W_1,W_2\}$ is a barbell partition of K.

Claim 1

There do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$.

Proof of Claim 1

Note, for vertices $u,v \in V(H)$, $uv \in E(H) \Longleftrightarrow uv \in E(K)$. Since $\{R,W_1,W_2\}$ is a barbell partition of H, it follows that there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$. $\square$

Claim 2

For each $r \in R'$, $\big | N_K(r) \cap W_i \big | \ne 1$ for $i \in \{1,2\}$.

Proof of Claim 2

Again, for vertices $u,v \in V(H)$, $uv \in E(H) \Longleftrightarrow uv \in E(K)$. Since $\{R,W_1,W_2\}$ is a barbell partition of H, it follows that for every vertex $r \in R$ and each $i \in \{1,2\}$, $\big | N_K(r) \cap W_i\big | \ne 1$. Next, since $K=G \vee H$ and $W_1 \cup W_2 \subset V(H)$, every vertex $v \in V(G)$ is adjacent to every vertex in $W_1 \cup W_2$. Since $|W_1|,|W_2| \ge 2$ for each $v \in V(G)$ and each $i \in \{1,2\}$, $\big | N_K(v) \cap W_i \big | \ge 2$. Since $R'=R \cup V(G)$, it follows that for every vertex $r \in R'$ and for each $i \in \{1,2\}$, $\big | N_K(r) \cap W_i \big | \ne 1$. $\square$

Thus $\{R', W_1, W_2\}$ forms a barbell partition of $K=G \vee H$.

Next suppose $\{R,W_1,W_2\}$ is a barbell partition of $K=G \vee H$. Since for every pair of vertices $g \in V(G)$ and $h \in V(H)$, we have $gh \in E(K)$, it follows that for each $i \in \{1,2\}$,

$$\begin{aligned} W_i \cap V(G) \ne \emptyset \Longrightarrow W_{3-i} \subset V(G) \text { and } W_i \cap V(H) \ne \emptyset \Longrightarrow W_{3-i} \subset V(H). \end{aligned}$$

Since $W_1,W_2 \ne \emptyset$, it must be that either $W_1 \cup W_2 \subseteq V(G)$ or $W_1 \cup W_2 \subseteq V(H)$. Without loss of generality, suppose that $W_1 \cup W_2 \subseteq V(H)$. It thus follows that $V(G) \subseteq R$. Finally, since for vertices $u,v \in V(H)$, $uv \in E(H) \Longleftrightarrow uv \in E(K)$, it follows that there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(H)$ and for each $r \in R \cap V(H)$ and each $i \in \{1,2\}$, it also follows that $\big | N_H(r) \cap W_i\big | \ne 1$. Thus $\{R \cap V(H), W_1,W_2\}$ is a barbell partition of H. Finally, since H has no isolated vertices, by Lemma 4.1$|W_1|,|W_2| \ge 2$. $\square$

Corollary 4.3

Let G be a graph with no isolated vertices, and let H be the graph obtained from G by adding a dominating vertex v. If $\{R,W_1,W_2\}$ is a barbell partition of G, then $\{R \cup \{v\},W_1,W_2\}$ is a barbell partition of H.

Proof

Since $\{R,W_1,W_2\}$ is a barbell partition of G and given $u,v \in V(G)$, $uv \in E(H)$ if and only if $uv \in E(G)$, it follows that there do not exist vertices $w_1 \in W_1$, $w_2 \in W_2$ such that $w_1w_2 \in E(H)$. Similarly, it follows that for each $r \in R$, $\big |N_H(r) \cap W_i\big | \ne 1$ for each $i \in \{1,2\}$. Since G has no isolated vertices, by Lemma 4.1, it follows that $|W_1|,|W_2| \ge 2$. Furthermore, since v is adjacent to every vertex in $W_1 \cup W_2$ and $|W_1|,|W_2| \ge 2$, it follows that $\big |N_H(v) \cap W_i\big | \ne 1$ for each $i \in \{1,2\}$. Thus $\{R \cup \{v\},W_1,W_2\}$ is a barbell partition of H. $\square$

Let G and H be two graphs. The graph obtained from G and H by identifying a vertex v in both G and H is called the vertex sum of G and H at v and is denoted by $G \oplus _v H$. Observe that v is necessarily a cut vertex of $G \oplus _v H$. Along these lines, it follows as an immediate corollary of Theorem 4.3 and Corollary 2.4 in [12] that, for two path graphs $P_n$ and $P_m$, $P_n \oplus _v P_m$ admits a barbell partition if and only if $\deg _{P_n}(v)=\deg _{P_m}(v)=2$. The next result is concerned with the vertex sum of two graphs excluding paths.

Theorem 4.4

Let G and H be graphs which are not paths. Then $G \oplus _v H$, where v is any identified vertex of both G and H, admits a barbell partition.

Proof

Since G is not a path, it follows that $\{v\}$ cannot be a zero forcing set of G. Thus, by Theorem 2.3, $V(G) {\setminus } \{v\}$ must contain a fort $F_G$ of G. Likewise, since H is not a path, $V(H) {\setminus } \{v\}$ must contain a fort $F_H$ of H. Since v is the only vertex in H with neighbors in G, and vice versa, it follows that $\{F_G,F_H\}$ is a pair of separated forts of $G \oplus _v H$, completing the proof. $\square$

In [12] the following results concerning barbell partitions, trees, and unicyclic graphs were proven.

Corollary 4.5

[12] If a tree T has a vertex v with $\deg (v) \ge 4$ or two vertices u, v with $\deg (u),\deg (v) \ge 3$, then T admits a barbell partition. Hence $T \not \in {\mathcal {G}}^\textrm{SSP}$.

Corollary 4.6

[12] If a unicyclic graph G has a vertex v such that $\deg (v) \ge 4$, or a vertex u not contained in the cycle with $\deg (u) \ge 3$, then G admits a barbell partition. Hence $G \not \in {\mathcal {G}}^\textrm{SSP}$.

With these results in mind, we now present a result concerning cacti, where a cactus is defined to be a connected graph such that no edge is contained in more than one cycle.

Theorem 4.7

Let G be a cactus with at least two cycles. Then G has a barbell partition, and thus $G \not \in {\mathcal {G}}^\textrm{SSP}$.

Proof

We will prove the theorem by breaking into two cases, and then showing that in either case G has a barbell partition and thus $G \not \in {\mathcal {G}}^\textrm{SSP}$.

Case 1 There exists a vertex $v \in V(G)$ such that v is in two cycles C and $C'$.

Since G is a cactus, no edge in E(G) is in more than one cycle. As a result, every vertex of degree larger than two is a cut-vertex, and so in particular, v is a cut-vertex. Since v is a cut-vertex contained in two cycles, there exist induced subgraphs $H_1$ and $H_2$ of G each containing a cycle such that $G \cong H_1 \oplus _v H_2$. So by Theorem 4.4, G admits a barbell partition.

Case 2 There does not exist a vertex $v \in V(G)$ such that v is in two cycles.

Since G is a cactus containing at least two cycles, there exist vertices $v_1,v_2 \in V(G)$ such that $v_1$ is contained in a cycle C, $v_2$ is contained in a cycle $C'$, and the $v_1v_2$-path P in G contains no vertices which are incident to a cycle except for $v_1$ and $v_2$. As before, there exist induced subgraphs $H_1$ and $H_2$ of G each containing a cycle such that $G \cong H_1 \oplus _{v_1} H_2$. Specifically, $H_1$ contains C and $H_2$ contains $C'$, and thus by Theorem 4.4, G admits a barbell partition. $\square$

Theorem 4.8

Let G be a graph and H be a graph admitting a barbell partition. Then $K=G \oplus _v H$, where v is any identified vertex of both G and H, admits a barbell partition.

Proof

Let $\{R, W_1, W_2\}$ be a barbell partition of H.

Case 1 $v \in R$

Let $R'=R \cup V(G)$. We will show that $\{R',W_1,W_2\}$ is a barbell partition of $K=G \oplus _v H$.

Claim 1.1

$W_1,W_2 \not = \emptyset$ and there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $\{w_1,w_2\} \in E(K)$.

Proof of Claim 1.1

Since $\{R,W_1,W_2\}$ is a barbell partition of H, it follows that $W_1,W_2 \ne \emptyset$ and there are no edges between vertices in $W_1$ and $W_2$ in H. Furthermore, since $V(G) \subset R'$, there are no edges between $W_1$ and $W_2$ in K.

Claim 1.2

For each $r \in R'$ and $i \in \{1,2\}$, we have that $\big | N_{K}(r) \cap W_i \big | \ne 1$.

Proof of Claim 1.2

If $r \in R' \cap V(H)$, since $\{R,W_1,W_2\}$ is a barbell partition of H and $V(G) \subseteq R'$, for each $i \in \{1,2\}$, we have $\big | N_K(r) \cap W_i \big | = \big | N_H(r) \cap W_i \big | \not = 1$. If $r \notin R' \cap V(H)$, since no vertex in $V(G){\setminus }\{v\}$ is adjacent to a vertex in $V(H) {\setminus } \{v\}$, it follows that $\big | N_K(r) \cap W_i \big | =0$.

Thus $\{R',W_1,W_2\}$ is a barbell partition of $K=G \oplus _v H$.

Case 2 $v \in W_i$ for some $i \in \{1,2\}$

Without loss of generality suppose $v \in W_1$, and let $W_1'=W_1 \cup V(G)$. We will show that $\{R,W'_1,W_2\}$ is a barbell partition of $K=G \oplus _v H$.

Claim 2.1

$W'_1,W_2 \not = \emptyset$ and there do not exist vertices $w_1 \in W'_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$.

Proof of Claim 2.1

Since $W_1 \subset W_1'$, it follows that $W_1'$ and $W_2$ are nonempty. Since there are no edges between $W_1$ and $W_2$ and no vertex in $V(G){\setminus }\{v\}$ is adjacent to a vertex in $V(H) {\setminus } \{v\}$, it follows that there are no edges between $W_1'$ and $W_2$. $\square$

Claim 2.2

For each $r \in R$, we have that $\big | N_{K}(r) \cap W'_1 \big | \ne 1$ and $\big | N_{K}(r) \cap W_2 \big | \ne 1$.

Proof of Claim 2.2

Since $V(G) \subset W_1'$ and no vertex in $V(H){\setminus }\{v\}$ is adjacent to a vertex in $V(G){\setminus }\{v\}$, it follows that for each $r \in R$, we have that $\big | N_{K}(r) \cap W'_1 \big | \ne 1$ and $\big | N_{K}(r) \cap W_2 \big | \ne 1$. $\square$

Thus $\{R, W_1',W_2\}$ is a barbell partition of $K=G \oplus _v H$. $\square$

From the above results we have the following straightforward consequence.

Observation 4.9

We can conclude from Theorem 4.4 and 4.8 that if $G \oplus _v H\in {\mathcal {G}}^\textrm{SSP}$ then either $G \oplus _v H=P_n \oplus _v P_m$ (with $\deg (v) = 1$ for at least one of the graphs), or one of the graphs is a path and the other does not admit a barbell partition.

5 Barbell Partitions and Graph Products

We close the discussion on barbell partitions by considering such vertex partitions associated with some classical graph products. We begin by considering the corona product of two graphs.

Definition 5.1

Let G and H be graphs with $V(G)=\{g_i\}_{i=1}^k$ and $V(H)=\{h_j\}_{j=1}^m$. The corona product of G with H, denoted $G \circ H$ is the graph with vertex set $V(G \circ H)=\{g_i\}_{i=1}^k \cup \{h_{i,j}\}_{i=1,}^k{}_{j=1}^m$ and edge set $E(G \circ H)$ such that given $u,v \in V(G \circ H)$, we have $uv \in E(G \circ H)$ provided one of the following is true:

• $u,v \in \{g_i\}_{i=1}^k$ and $uv \in E(G)$

• $u = g_i$ and $v=h_{i,j}$ for some $i \in \{1,2,\ldots ,k\}$ and some $j \in \{1,2,\ldots ,m\}$

• $u=h_{i,j_1}$ and $u=h_{i,j_2}$ with $h_{j_1}h_{j_2} \in E(H)$.

Regarding the corona product we consider the special case of the complete graph $K_n$ with $K_1$, denoted by $K_n\circ K_1$, is called the corona of $K_n$.

Proposition 5.2

Let

$$\begin{aligned} B = \begin{bmatrix} A &{} D_{\mu }\\ D_{\mu } &{} D_{\lambda }\\ \end{bmatrix} \in {\mathcal {S}}(K_n\circ K_1) \end{aligned}$$

where $A \in {\mathcal {S}}(K_n)$, $D_{\mu }={\text {diag}}(\mu _1,\mu _2,\ldots ,\mu _n)$ and $D_{\lambda }={\text {diag}}(\lambda _1,\lambda _2,\ldots ,\lambda _n)$ with $\mu _i \ne 0$ for all $i \in [n]$. Then B has the SSP if $D_{\lambda } = \lambda I_n$, and $\mu _i \ne \pm \mu _j$ for all $i,j \in [n]$ with $i\ne j$.

Proof

Since $A \in {\mathcal {S}}(K_n)$, the corresponding block of the matrix X is the zero matrix. Let

$$\begin{aligned} X = \begin{bmatrix} O &{} X_{\mu }\\ X_{\mu }^T &{} Y_{\lambda }\\ \end{bmatrix} \end{aligned}$$

where $[X_{\mu }]_{i,j}=x_{i,n+j}$ and $[Y_{\lambda }]_{i,j}=x_{n+i,n+j}.$ If $BX = XB,$ then

$$\begin{aligned}&D_{\mu }X_{\mu }^T = X_{\mu }D_{\mu }, \end{aligned}$$

(1)

$$\begin{aligned}&AX_{\mu }+D_{\mu }Y_{\lambda } = X_{\mu }D_{\lambda }, \end{aligned}$$

(2)

$$\begin{aligned}&D_{\lambda }X_{\mu }^T = X_{\mu }^TA + Y_{\lambda } D_{\mu }, \ \, \text {and} \end{aligned}$$

(3)

$$\begin{aligned}&D_{\mu }X_{\mu }+ D_{\lambda }Y_{\lambda } = X_{\mu }^TD_{\mu }+ Y_{\lambda }D_{\lambda }. \end{aligned}$$

(4)

From Eq. (1) we obtain:

$$\begin{aligned} {[}D_{\mu }X_{\mu }^T - X_{\mu }D_{\mu }]_{i,j}= \mu _i x_{j, n +i} - \mu _j x_{i,n+j}=0 \text { or } x_{j n+i} = \frac{\mu _j x_{i, n+j}}{\mu _i} \end{aligned}$$

(5)

while from Eq. (4), we get:

$$\begin{aligned}{} & {} {[}X_{\mu }^TD_{\mu }+ Y_{\lambda }D_{\lambda } - (D_{\mu }X_{\mu }+ D_{\lambda }Y_{\lambda })]_{i,j} \\{} & {} \quad = \mu _j x_{j, n + i} - \mu _i x_{i, n + j} - (\lambda _i - \lambda _j) x_{n + i, n+j} = 0. \end{aligned}$$

Together, we yield:

$$\begin{aligned} \frac{(\mu _j - \mu _i) (\mu _j + \mu _i)}{\mu _i}x_{i, n+j} - (\lambda _i - \lambda _j) x_{n + i, n+j} = 0. \end{aligned}$$

(6)

Because $D_{\lambda } = \lambda I_n$, and $\mu _i \ne \pm \mu _j$ for all $i,j \in [n]$ with $i\ne j$, $X_{\mu }=O$. So the Eqs. (1) to (4) simplify to

$$\begin{aligned}&D_{\mu }Y_{\lambda } = O, \end{aligned}$$

(7)

$$\begin{aligned}&O = Y_{\lambda }D_{\mu }, \, \text {and} \end{aligned}$$

(8)

$$\begin{aligned}&\lambda Y_{\lambda } = \lambda Y_{\lambda } \end{aligned}$$

(9)

Equations (7) and (8) yield that $Y_{\lambda } = O$ since each $\mu _i \ne 0$ for all $i\in [n]$. $\square$

Considering the corona product of graphs each with more than one vertex leads to the next result connected to barbell partitions of the corona product.

Theorem 5.3

Let G and H be graphs each with at least two vertices. Then $G \circ H$ has a barbell partition.

Proof

Let $V(G)=\{g_i\}_{i=1}^k$, $V(H)=\{h_j\}_{j=1}^m$, and $V(G \circ H)=\{g_i\}_{i=1}^k \cup \{h_{i,j}\}_{i=1,}^k{}_{j=1}^m$ as in Definition 5.1. Since $\big |V(G)\big | \ge 2$, one can let $W_1=\{h_{1,j}\}_{j=1}^m$, $W_2=\{h_{2,j}\}_{j=1}^m$, and $R=V(G){\setminus }(W_1 \cup W_2)$. We will now show that $\{R,W_1,W_2\}$ is a barbell partition of $G \circ H$.

Next note that $W_1, W_2 \ne \emptyset$ and for each $i \in \{1,2\}$, given $v \in V(G \circ H) {\setminus } W_i$ and $w_i \in W_i$, we have $vw_i \in E(G \circ H)$ if and only if $v=g_i$. So there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(G \circ H)$. In addition, since $\big |V(H)\big | \ge 2$, it follows that for each $i \in \{1,2\}$, $\big |N_{G \circ H}(g_i) \cap W_i\big | \ge 2$. So for each $r \in R$ and each $i \in \{1,2\}$, $\big |N_{G \circ H}(r) \cap W_i\big | \ne 1$. Thus, $\{R, W_1, W_2\}$ is a barbell partition of $G \circ H$. $\square$

If $\big |V(G)\big |=1$ or $\big |V(H)\big |=1$, then it is possible that $G \circ H$ admits a barbell partition. In particular, if $\big |V(G)\big |=1$ and H is a graph which admits a barbell partition and has no isolated vertices, then by Corollary 4.3 it follows that $G \circ H$ admits a barbell partition. In addition, if $\big |V(H)\big |=1$ and G is a graph which admits a barbell partition, then it follows by repeated application of Observation 3.6 that $G \circ H$ admits a barbell partition.

Corollary 5.4

Let G and H be graphs each with at least two vertices. Then $G \circ H$ is not a member of ${\mathcal {G}}^\textrm{SSP}$.

We next turn to the standard definitions for the Cartesian product and tensor product of two graphs.

Definition 5.5

Let G and H be graphs. Then the Cartesian product of G and H denoted $G \Box H$ is the graph with vertex set $V(G \Box H)=V(G) \times V(H)$ and edge set $E(G \Box H)$ such that given $(g_1,h_1), (g_2,h_2) \in V(G \Box H)$, $(g_1,h_1)(g_2,h_2) \in E(G \Box H)$ provided either

• $g_1=g_2$ and $h_1h_2 \in E(H)$ or

• $h_1=h_2$ and $g_1g_2 \in E(G)$.

Definition 5.6

Let G and H be graphs. Then the tensor product of G and H denoted $G \times H$ is the graph with vertex set $V(G \times H)=V(G) \times V(H)$ and edge set $E(G \times H)$ such that given $(g_1,h_1), (g_2,h_2) \in V(G \times H)$, $(g_1,h_1),(g_2,h_2) \in E(G \times H)$ provided $g_1g_2 \in E(G)$ and $h_1h_2 \in E(H)$.

The next result represents a closure-type statement regarding the above graph products and graphs that admit barbell partitions.

Theorem 5.7

Let G be a graph and H be a graph admitting a barbell partition, then

• $L_1=G \Box H$ admits a barbell partition.

• $L_2=G \times H$ admits a barbell partition.

Proof

Let $\{R, W_1, W_2\}$ be a barbell partition of H, and let $R'$, $W_1'$, and $W_2'$ be defined as follows:

• $R'=\left\{ (g,h) \in V(G) \times V(H): h \in R\right\}$,

• $W_1'=\left\{ (g,h) \in V(G) \times V(H): h \in W_1\right\}$, and

• $W_2'=\left\{ (g,h) \in V(G) \times V(H): h \in W_2\right\}$.

We will show that $\{R', W_1', W_2'\}$ is a barbell partition of $L_j$ for each $j \in \{1,2\}$.

Claim 1

$W'_1,W'_2 \not = \emptyset$ and for each $j \in \{1,2\}$, there do not exist vertices $w_1 \in W'_1$ and $w_2 \in W'_2$ such that $w_1w_2 \in E(L_j)$.

Proof of Claim 1

Since $W_1$ and $W_2$ are nonempty, $W_1'$ and $W_2'$ are nonempty. Now, let $w_1 \in W_1'$ and $w_2 \in W'_2$ be arbitrary. So there exist $g_1,g_2 \in V(G)$, $h_1 \in W_1$, and $h_2 \in W_2$ such that $w_1=(g_1,h_1)$ and $w_2=(g_2,h_2)$. Since $h_1 \in W_1$ and $h_2 \in W_2$, it follows that $h_1 \ne h_2$ and $h_1h_2 \not \in E(H)$. Thus $w_1$ and $w_2$ are not adjacent in $L_j$ for each $j \in \{1,2\}$. Finally, since $w_1$ and $w_2$ were chosen arbitrarily, for each $j \in \{1,2\}$ there do not exist vertices $w_1 \in W'_1$ and $w_2 \in W'_2$ such that $w_1w_2 \in E(L_j)$. $\square$

Claim 2

For each $r \in R'$, $j \in \{1,2\}$, and $i \in \{1,2\}$, we have that $\big | N_{L_j}(r) \cap W'_i \big | \ne 1$.

Proof of Claim 2

Let $r \in R'$ and $i_0 \in \{1,2\}$ be arbitrary. Since $r \in R'$ there exist $h_r \in R$ and $g_r \in V(G)$ such that $r=(g_r,h_r)$. Now, let $k \in {\mathbb {Z}}$ such that $\big | N_H(h_r) \cap W_{i_0} \big | =k$. Since $\{R,W_1,W_2\}$ is a barbell partition of H, it follows that $k \ne 1$.

First consider $L_1$, and note that since $h_r \ne w_{i_0}$ for each $w_{i_0} \in W_{i_0}$, r is neighbors with $(g,w_{i_0}) \in W'_{i_0}$ if and only if $g=g_r$ and $h_r$ is neighbors with $w_{i_0}$ in H. So, it follows that

$$\begin{aligned} \big | N_{L_1}(r) \cap W_{i_0} \big | = k. \end{aligned}$$

Next consider $L_2$, and note that for each neighbor $w_{i_0} \in W_{i_0}$ of $h_r$, r has $\deg _G(g_r)$ many neighbors in $W'_{i_0}$, specifically the set of vertices

$$\begin{aligned} \big \{(g,w_{i_0}): g \in N_G(g_r)\big \}. \end{aligned}$$

So, it follows that

$$\begin{aligned} \big | N_{L_2}(r) \cap W_{i_0} \big | = k\cdot \deg _G(g_r). \end{aligned}$$

Since $k \ne 1$, it follows that $k\cdot \deg _G(g_r) \ne 1$. Finally, since $r \in R'$ and $i_0 \in \{1,2\}$ were arbitrary choices, for each $r \in R'$, $j \in \{1,2\}$, and $i \in \{1,2\}$, we have that $\big | N_{L_j}(r) \cap W'_i \big | \ne 1$. $\square$

Thus, $\{R', W_1', W_2'\}$ is a barbell partition of $L_j$ for each $j \in \{1,2\}$. $\square$

Corollary 5.8

Let G and H be graphs such that H admits a barbell partition. Then $G \Box H$ and $G \times H$ is not a member of ${\mathcal {G}}^\textrm{SSP}$.

Theorem 5.9

Let G and H be graphs each containing a pair of disjoint forts. Then $K=G \Box H$ admits a barbell partition.

Proof

Let $F_G^1, F_G^2$ be a pair of forts of G such that $F_G^1 \cap F_G^2=\emptyset$, and likewise let $F_H^1, F_H^2$ be a pair of forts of H such that $F_H^1 \cap F_H^2=\emptyset$. Let $W_1=\{(g,h): g \in F_G^1 \text { and } h \in F_H^1\}$, $W_2=\{(g,h): g \in F_G^2 \text { and } h \in F_H^2\}$, and $R=V(K) {\setminus } (W_1 \cup W_2)$. We will show that $\{R,W_1,W_2\}$ is a barbell partition of K.

Claim 1

$W_1,W_2 \not = \emptyset$ and there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$.

Proof of Claim 1

By construction $W_1,W_2 \ne \emptyset$. Furthermore, given $(g_1,h_1) \in W_1$ and $(g_2,h_2) \in W_2$, since $F_G^1 \cap F_G^2= \emptyset$ and $F_H^1 \cap F_H^2 =\emptyset$, it follows that $g_1 \ne g_2$ and $h_1 \ne h_2$. Thus $(g_1,h_1)(g_2,h_2) \not \in E(K)$. Furthermore, since $(g_1,h_1)$ and $(g_2,h_2)$ were chosen arbitrarily, there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$. $\square$

Claim 2

For each $r \in R$ and $i \in \{1,2\}$, we have that $\big | N_{K}(r) \cap W_i \big | \ne 1$.

Proof of Claim 2

First consider $W_1$. For each $r=(g,h) \in R$, either $g \not \in F_G^1$ or $h \not \in F_H^1$. First if $g \not \in F_G^1$ and $h \not \in F_H^1$, then $\big |N_K(r) \cap W_1\big |=0$. So without loss of generality suppose $g \not \in F_G^1$ and $h \in F_H^1$. Since $g \not \in F_G^1$, there exists $k \in {\mathbb {N}}$ such that $\big |N_G(g) \cap F_G^1\big |=k \ne 1$. Furthermore for each $g' \in F_G^1$, $r=(g,h)$ is neighbors with $(g',h) \in W_1$ if and only if g is neighbors with $g'$ in G. So, it follows that $\big | N_{K}(r) \cap W_1 \big | = k$. Thus, for each $r=(g,h) \in R$, $\big | N_{K}(r) \cap W_1 \big | \ne 1$. A similar argument shows that for each $r=(g,h) \in R$, $\big | N_{K}(r) \cap W_2 \big | \ne 1$. $\square$

Thus $\{R,W_1,W_2\}$ is a barbell partition of $K=G\Box H$. $\square$

Many graphs contain a pair of disjoint forts. Examples of graphs which contain a disjoint pair of forts, but which do not admit barbell partitions are complete graphs $K_n$, $n \ge 4$ and even cycles.

Corollary 5.10

Let $m,k \in {\mathbb {Z}}^+$ with $m,k \ge 4$. Then $G=K_m \Box K_k$ admits a barbell partition.

Corollary 5.11

Let $C_m$ and $C_k$ each be even cycles with $m,k\ge 4$. Then $G=C_m \Box C_k$ admits a barbell partition.

Path graphs and odd cycles are examples of graphs which do not contain a pair of disjoint forts. It is easy to check that $P_2 \Box P_3$ does not admit a barbell partition. However, while grid graphs do not seem to admit barbell partitions, the following theorem shows that certain torus grid graphs do admit barbell partitions, even when the cycles they are built from may be of odd length.

Theorem 5.12

Let $m,k \in {\mathbb {Z}}^+$ such that $k \ge 4$, then $K=C_k \Box C_{mk}$ admits a barbell partition.

Fig. 2

$C_4 \Box C_{8}$ (color figure online)

Proof

For $N \in \{k,mk\}$, enumerate the vertices of $C_N$ as $\{j\}_{j=1}^N$ such that given $j_1,j_2 \in V(C_N)$, we have that $j_1j_2 \in E(C_N)$ provided either $| j_1-j_2 |=1$ or $\{j_1,j_2\}=\{1,N\}$, and let $\{R,W_1,W_2\}$ be such that

• $W_1=\left\{ (j_1,j_2) \in V(C_k) \times V(C_{mk}): j_2=Mk+j_1 \text { with } 0\le M \le m-1\right\}$,

• $R=\Big \{(j_1,j_2) \in V(C_k) \times V(C_{mk}): j_2=Mk+j_1+1 \text { or } j_2=Mk+j_1+(k-1) \text { with } -1\le M \le m-1\Big \}$,

• $W_2=\Big \{(j_1,j_2) \in V(C_k) \times V(C_{mk}): j_2=Mk+j_1+N \text { with }-1\le M \le m-1 \text { and } 2 \le N \le k-2\Big \}$.

An example is shown in Fig. 2 where R is formed by the green vertices, $W_1$ is the set of red vertices, and $W_2$ is the set of blue vertices. We will now show that $\{R,W_1,W_2\}$ is a barbell partition of G.

Claim 1

$W_1,W_2 \not = \emptyset$ and there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$.

Proof of Claim 1

First, note that $\{R,W_1,W_2\}$ is a partition of V(G) and let $v \in W_1$ be arbitrary. We will show that $N_K(v) \subset R$ and thus, since $R \cap W_2 = \emptyset$, that there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$. Since $v \in W_1$ it follows that v is of the form $(j_1, j_2)$ with $j_2=Mk+j_1$ and $0\le M \le m-1$. To show that $N_K(v) \subset R$, we will show that there exist distinct values a, b such that $(j_1,a),(j_1,b) \in N_K(v) \cap R$ and distinct values c, d such that $(c,j_2),(d,j_2) \in N_K(v) \cap R$, and thus since K is 4-regular, that $N_K(v) \subset R$.

Case 1 $j_2 \not \in \{1,mk\}$

Since $j_2 \not \in \{1,mk\}$, it follows that $(j_1,j_2)(j_1,j_2+1),(j_1,j_2)(j_1,j_2-1) \in E(K)$. It now remains to argue that $(j_1,j_2-1),(j_1,j_2+1) \in R$. First, since $1< j_2 <mk$ and $1 \le j_1 \le k$, we have that $1 \le j_2-1 < j_2+1 \le mk$ and $1 \le j_1 \le k$. Since $j_2=Mk+j_1$ for some M with $0 \le M \le m-1$, $j_2+1=Mk+j_1+1$ and so $(j_1,j_2+1) \in R$. In addition, since $M \ge 0$, $j_2-1=Mk+j_1-1=(M-1)k+j_1+(k-1)$ with $M-1 \ge -1$ and so $(j_1,j_2-1) \in R$.

Case 2 $j_2=1$

Since $j_2=1$, it follows that $(j_1,j_2)(j_1,2),(j_1,j_2)(j_1,mk) \in E(K)$. It now remains to argue that $(j_1,2),(j_1,mk) \in R$. First note, $1 \le j_1 \le k$. Since $j_2=Mk+j_1=1$, we have that $M=0$ and $j_1=1$, so $2=Mk+j_1+1$ and thus $(j_1,2) \in R$. In addition, $mk=(m-1)k+j_1+(k-1)$ and thus $(j_1,mk) \in R$.

Case 3 $j_2=mk$

This case follows from similar lines of reasoning as in Case 2.

In any case, there exist distinct values a, b such that $(j_1,a),(j_1,b) \in N_K(v) \cap R$. It now remains to show that there exist distinct values c, d such that $(c,j_2),(d,j_2) \in N_K(v) \cap R$. Before considering the cases, note that if $x=j_2-Mk-1$ or $x=j_2-Mk-(k-1)$ with $-1 \le M \le m-1$, then $(x,j_2) \in R$.

Case 1 $j_1 \not \in \{1,k\}$

Since $j_1 \not \in \{1,k\}$, it follows that $(j_1,j_2)(j_1+1,j_2),(j_1,j_2)(j_1-1,j_2) \in E(K)$. It now remains to argue that $(j_1+1,j_2),(j_1-1,j_2) \in R$. First, since $1< j_1 <k$ and $1 \le j_2 \le mk$, we have that $1 \le j_1-1 < j_1+1 \le k$ and $1 \le j_2 \le mk$. Since $j_2=j_1+Mk$ for some M with $0 \le M \le m-1$, $j_1-1=j_2-Mk-1$ and so $(j_1-1,j_2) \in R$. In addition, $j_1+1=j_2-(M-1)k-(k-1)$ and since $M \ge 0$ we have $M-1 \ge -1$, and thus $(j_1+1,j_2) \in R$.

Case 2 $j_1=1$

Since $j_1=1$, it follows that $(j_1,j_2)(2,j_2),(j_1,j_2)(k,j_2) \in E(K)$. It now remains to argue that $(2,j_2),(k,j_2) \in R$. First note, $1 \le j_2 \le mk$. Since $j_2=j_1+Mk$ we have $j_2=Mk+1$ for some M with $0 \le M \le m-1$. So $2=j_2-(M-1)k-(k-1)$ and $k=j_2-(M-1)k-1$. Since $M \ge 0$, we have $M-1 \ge -1$, and thus $(2,j_2),(k,j_2) \in R$.

Case 3 $j_1=k$

This case follows from similar lines of reasoning as in Case 2 $\square$

Claim 2

For each $r \in R$ and $i \in \{1,2\}$, we have that $\big | N_K(r) \cap W_i \big | =2$.

Proof of Claim 2

Using techniques similar to those exhibited in Claim 1, the reader can check that for each $r \in R$ there exist values a, b, c, d such that $(j_1,a),(b,j_2) \in N_K(r) \cap W_1$ and distinct values c, d such that $(j_1,c),(d,j_2) \in N_K(r) \cap W_2$, with r of the form $(j_1,j_2)$. Thus since K is 4-regular it follows that for each $r \in R$ and each $i \in \{1,2\}$ we have $\big | N_K(r) \cap W_i \big | = 2$. $\square$

Thus, $\{R, W_1, W_2\}$ is a barbell partition of K. $\square$

Theorem 5.13

Let G be a graph which is not a complete graph and H be a graph with no pendant vertices such that $\big |V(H)| \ge 2$. Then $K=G \times H$ admits a barbell partition.

Proof

If G or H are disconnected, then $K=G \times H$ is disconnected in which case by Observation 2.6, K admits a barbell partition. So suppose both G and H are connected. Since H is connected and has no pendant vertices, it follows that $\delta (H) \ge 2$. Since G is not a complete graph there exist vertices $u,v \in V(G)$ such that $uv \not \in E(G)$. Let

$$\begin{aligned} W_1=\left\{ (u,h): h \in V(H)\right\} , W_2=\left\{ (v,h): h \in V(H)\right\} , \end{aligned}$$

and

$$\begin{aligned} R=\left\{ (g,h): g \in V(G){\setminus }\{u,v\} \text { and } h \in V(H)\right\} . \end{aligned}$$

We will show that $\{R,W_1,W_2\}$ is a barbell partition of K.

Claim 1

$W_1,W_2 \not = \emptyset$ and there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$.

Proof of Claim 1

Since $V(H) \ne \emptyset$, it follows that $W_1,W_2 \not = \emptyset$. Furthermore, since $uv \not \in E(G)$, there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$. $\square$

Claim 2

For each $r \in R$, $\big | N_G(r) \cap W_i \big | \ne 1$ for $i \in \{1,2\}$.

Proof of Claim 2

Let $r \in R$ be arbitrary. Since $r \in R$, there exists $g \in V(G) {\setminus } \{u,v\}$ and $h \in V(H)$ such that $r=(g,h)$. First, note that if $gu \not \in E(G)$, then r will have no neighbors in $W_1$. So suppose $gu \in E(G)$. Since H is such that $\delta (H)\ge 2$ there exists $h_1,h_2 \in V(H)$ such that $hh_1,hh_2 \in E(H)$. Since $gu \in E(G)$ and $hh_1,hh_2 \in E(H)$, r will be adjacent to both $uh_1$ and $uh_2$, each of which are members of $W_1$. So $\big | N_K(r) \cap W_1 \big | \ge 2$. In either case, for each $r \in R$ we have that $\big | N_K(r) \cap W_1 \big | \ne 1$. Likewise, for each $r \in R$, $\big | N_K(r) \cap W_2 \big | \ne 1$. $\square$

Thus $\{R, W_1, W_2\}$ forms a barbell partition of $K=G \times H$. $\square$

Example 5.14

The requirement in Theorem 5.13 that H has no pendant vertices may seem unnecessary. However, we observe, by example, a pair of graphs G and H where G is not complete, H contains at least two vertices (each pendant vertices), but the product $G \times H$ does not admit a barbell partition. This identifies that the criterion regarding pendant vertices is quite necessary (Fig. 3).

Assume $K_2\times H$ has a barbell partition. Now, assume vertex (3, a) is in R. Then, both (4, b) and (2, b) need to be either in R or (without loss of generality) in $W_1$. If they are both in R. Then note that both (5, a) and (2, a) are either in R or in $W_1$. In the first case, that would imply that (1, b) and (3, b) are in R as well as (4, a), (5, b) and finally (1, a), that is, the whole graph is in R, which is a contradiction. On the other hand if both (5, a) and (2, a) are in $W_1$, that would imply that (3, b) is not in $W_2$ and that (4, a) is either in R or $W_1$ (not in $W_2$), then (5, b) is not in $W_2$ and finally (1, a) would not be in $W_2$ either and $W_2 =\emptyset$, a contradiction. Now, let us assume that both (4, b) and (2, b) are in $W_1$. This implies that the only vertex that can be in $W_2$ is (3, b), a contradiction. Assuming that (3, a) is in $W_1$ we also find a contradiction. Thus $K_2\times H$ has no barbell partition.

Fig. 3

$K_2 \times H$ does not admit a barbell partition

Before we close the topic of tensor products we consider the tensor product of two path graphs and the tensor product of two complete graphs. First we have the following.

Theorem 5.15

Let $m,k \in {\mathbb {Z}}^+$ such that $m,k \ge 2$, then $G=P_k \times P_m$ admits a barbell partition.

Proof

G is disconnected, so it immediately admits a barbell partition. $\square$

On the other hand, results concerning complete graphs are a bit more nuanced. It can be checked by exhaustion that $K_3 \times K_3$ does not admit a barbell partition. However, as witnessed by the following theorem, there are instances in which $K_n \times K_m$ does admit a barbell partition (Fig. 4).

Theorem 5.16

Let $n,m \in {\mathbb {N}}$ with $n \ge 2$ and $m \ge 6$. Then $G=K_n \times K_m$ admits a barbell partition.

Fig. 4

$K_2 \times K_6$ (color figure online)

Proof

Enumerate the vertices of $K_n = \{u_i\}_{i=1}^n$ and the vertices of $K_m = \{v_j\}_{j=1}^m$. Let

$$\begin{aligned} R= & {} \left\{ (u_i,v): i> 1 \text { and }v \in V(K_m)\right\} ,\\ W_1= & {} \left\{ (u_1,v_j): j \le \Big \lceil \frac{m}{2} \Big \rceil \right\} , \text { and } W_2=\left\{ (u_1,v_j): j > \Big \lceil \frac{m}{2}\Big \rceil \right\} . \end{aligned}$$

We will show that $\{R,W_1,W_2\}$ is a barbell partition of G.

Claim 1

$W_1,W_2 \not = \emptyset$ and there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(G)$.

Proof of Claim 1

Since $m > 2$, $W_1,W_2 \not = \emptyset$. Furthermore, since $W_1 \cup W_2=\left\{ (u_1,v): v \in V(K_m)\right\}$, it follows that $W_1 \cup W_2$ is an independent set of vertices in $G=K_n \times K_m$. $\square$

Claim 2

For each $r \in R$, $\big | N_G(r) \cap W_i \big | \ne 1$ for $i \in \{1,2\}$. $\square$

Proof of Claim 2

Given $r \in R$, r is of the form $(u_i,v_j)$ with $i>1$. So r is adjacent to every member of $W_1 \cup W_2$ except for $(u_1,v_j)$, and since $m \ge 6$, it follows that

$$\begin{aligned} \big | N_G(r) \cap W_i \big | \ge \left\lfloor \frac{m}{2} \right\rfloor -1 \ge 2, \text { for each } i \in \{1,2\}. \end{aligned}$$

$\square$

Thus $\{R, W_1, W_2\}$ forms a barbell partition of $G=K_n \times K_m$. $\square$

We finish this section by considering one final graph product known as the strong product.

Definition 5.17

Let G and H be graphs. Then the strong product of G and H denoted by $G \boxtimes H$ is the graph with vertex set $V(G \boxtimes H)=V(G) \times V(H)$ and edge set $E(G \boxtimes H)$ such that given $(g_1,h_1), (g_2,h_2) \in V(G \boxtimes H)$, $(g_1,h_1)(g_2,h_2) \in E(G \boxtimes H)$ provided either

• $g_1=g_2$ and $h_1h_2 \in E(H)$ or

• $h_1=h_2$ and $g_1g_2 \in E(G)$ or

• $g_1g_2 \in E(G)$ and $h_1h_2 \in E(H)$.

Observation 5.18

For $m,n\ge 1$ the graph $K_n \boxtimes K_m$ is isomorphic to $K_{nm}$, and so does not admit a barbell partition.

Theorem 5.19

Let G be a graph which is not a complete graph and H be a graph with more than one vertex. Then $K=G \boxtimes H$ admits a barbell partition.

Proof

If G or H are disconnected, then $K=G \boxtimes H$ is disconnected in which case by Observation 2.6, K admits a barbell partition. So suppose both G and H are connected. Since G is not a complete graph there exist vertices $u,v \in V(G)$ such that $uv \not \in E(G)$. Let

$$\begin{aligned} W_1=\left\{ (u,h): h \in V(H)\right\} , W_2=\left\{ (v,h): h \in V(H)\right\} \end{aligned}$$

and

$$\begin{aligned} R=\left\{ (g,h): g \in V(G){\setminus }\{u,v\} \text { and } h \in V(H)\right\} . \end{aligned}$$

We will show that $\{R,W_1,W_2\}$ is a barbell partition of K.

Claim 1

$W_1,W_2 \not = \emptyset$ and there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$.

Proof of Claim 1

Since $V(H) \ne \emptyset$, it follows that $W_1,W_2 \not = \emptyset$. Furthermore, since $u \ne v$ and $uv \not \in E(G)$, there do not exist vertices $w_1 \in W_1$ and $w_2 \in W_2$ such that $w_1w_2 \in E(K)$. $\square$

Claim 2

For each $r \in R$, $\big | N_G(r) \cap W_i \big | \ne 1$ for $i \in \{1,2\}$.

Proof of Claim 2

Let $r \in R$ be arbitrary. Since $r \in R$, there exists $g \in V(G) {\setminus } \{u,v\}$ and $h \in V(H)$ such that $r=(g,h)$. First, note that if $gu \not \in E(G)$, then r will have no neighbors in $W_1$. So suppose $gu \in E(G)$. Since H is a connected graph on at least two vertices there exists $h' \in V(H)$ such that $hh' \in E(H)$. Since $gu \in E(G)$ and $hh' \in E(H)$, r will be adjacent to both uh and $uh'$, each of which are members of $W_1$. So $\big | N_K(r) \cap W_1 \big | \ge 2$. In either case, for each $r \in R$ we have that $\big | N_K(r) \cap W_1 \big | \ne 1$. Likewise, for each $r \in R$, $\big | N_K(r) \cap W_2 \big | \ne 1$. $\square$

Thus $\{R, W_1, W_2\}$ forms a barbell partition of $K=G \boxtimes H$. $\square$

Corollary 5.20

Let G be a graph which is not a complete graph and H be a graph of more than one vertex. Then $K=G \boxtimes H$ is not a member of ${\mathcal {G}}^\textrm{SSP}$.