Electronic Journal of Graph Theory and Applications 12 .
, 343Ae362 Bounds for neighbor connectivity of Cayley graphs generated by trees and unicyclic graphs Mohamad Abdallah Department of Mathematics and Natural Sciences.
American University of Kuwait mkmabdall@gmail.
Abstract The neighbor connectivity refers to the minimum number of vertices whose removal, along with their neighbors, causes a previously connected graph to become disconnected.
In this paper we focus on Cayley graphs constructed from the symmetric group Sn .
We investigate the bounds of the neighbor connectivity for two cases: when the generating graph is a tree, and when it is a unicyclic graph with a unique cycle of length m, specifically considering cases where m = 3, m = n Oe 1, or m = n.
Keywords: neighbor connectivity.
Cayley graph, interconnection networks Mathematics Subject Classification : 05C40, 68R05, 05C90 DOI: 10.
5614/ejgta.
This is a numbered first-level section head An undirected graph G = (V.
E) is employed to represent an interconnection network, where V stands for the set of vertices, and E designates the set of edges.
Within this framework, processors are aligned with vertices, and communication links are depicted by edges.
The notion of graph connectivity is a subject extensively explored in graph theory and network analysis.
The connectivity of a graph G, denoted as (G), signifies the smallest number of vertices in G that, upon removal, result in the formation of a disconnected or trivial graph.
This measure serves as a straightforward gauge of the reliability and fault-tolerance of interconnection networks .
, 6, 18, .
Received: 24 May 2024.
Revised: 29 September 2024.
Accepted: 4 October 2024.
Bounds of neighbor connectivity of Cayley graphs Abdallah Gunter and Hartnell introduced the concept of neighbor connectivity in .
, 9, .
Their innovation involved extending the idea of connectivity by eliminating the closed neighborhood of a vertex rather than just removing the vertex itself.
In network terms, this corresponds to a scenario where the failure of a vertex implies the failure of all its adjacent vertices.
In the referenced paper .
, the authors opted for the term AusubversionAy in lieu of Aufailure.
Ay This choice was motivated by the graphAos application in modeling an underground resistance movement, where vertices symbolize agents and edges represent communication lines among them.
In the context of this model, when an agent is subverted, it results in the betrayal of all agents with whom they are in communication.
Consistently, this paper adopts the same terminology as used in .
to articulate the definition of neighbor connectivity.
Let G = (V.
E) be a simple connected graph.
The neighborhood of a vertex u of G is defined by N .
= .
OO V .
uv OO E}, and the closed neighborhood of u is defined by N .
= .
O N .
If H is a subgraph of G containing the vertex u, then NH .
= .
OO V (H).
uv OO E(H)}.
A vertex u of G is called subverted if the closed neighborhood N .
has been deleted from G.
A set of vertices U = .
1 , .
, un } is called a subverted strategy if each of the vertices u1 , .
, un has been subverted.
The survival subgraph of G for U , denoted by G On U , is the subgraph of G induced by V Oe N [U ].
The neighbor connectivity of G, denoted by N B (G), is the size of the minimum set U , such that U OI V and GOnU is disconnected, complete, or empty.
Such set U is called a vertex-cut strategy.
Consider a finite group A and a set OI containing elements of A, excluding the groupAos identity, and satisfying the property that for any u OO OI, its inverse uOe1 is also in OI.
The vertex set of the Cayley graph Cay(A.
OI) consists of all elements of A, with two vertices u and v being adjacent if and only if there exists an s OO OI such that u = vs.
Let Sn denote the symmetric group, representing permutations on .
= 1, 2, .
, n, and let T be a set of transpositions.
We define G(T ) as the transposition generating graph, where the vertex set of G(T ) is .
, and its edge set is {.
, .
, .
OO T }.
In this paper, the focus is on determining the neighbor connectivity of Cay(Sn .
T ), where G(T ) represents either a tree with n vertices or a graph with n vertices containing a unique cycle of length m = 3 or m = n Oe 1.
The examined graph families include well-known networks, such as the star graph, the bubble-sort graph, and the modified bubble-sort graph .
, 12, 7, 13, 20, .
The main results are provided in Theorem 3.
2 and Theorem 4.
The paperAos structure unfolds as follows: Section 2 presents various definitions.
In Section 3, we explore the neighbor connectivity of Cayley graphs generated by trees, subsequently deducing the neighbor connectivity of the star graph and the bubble-sort graph.
Moving on to Section 4, we determine the neighbor connectivity of Cayley graphs generated by unicyclic graphs and deduce the neighbor connectivity of the modified bubble-sort graph.
Section 5 serves as the conclusion, where we summarize our findings and propose a conjecture regarding the neighbor connectivity of the Cayley graph when the generating graph is a graph with n vertices and contains a unique cycle of length m where 4 O m O n Oe 2.
Preliminaries We will follow usual graph terminology, which can be found in .
Let G = (V.
E) be a graph with vertex set V = V (G) and edge set E = E(G).
The neighborhood of u OO V , denoted Bounds of neighbor connectivity of Cayley graphs Abdallah N .
, is the set of vertices adjacent to u.
The closed neighborhoodSof u OO V is defined by N .
= N .
O .
If H is a subset of V (G), we denote by N [H] = xOOH N .
The degree of a vertex v is the number of vertices of G adjacent to v.
The minimum degree is denoted by (G) and the maximum degree by OI(G).
A set of edges are called independent if no two of them have a common endpoint.
The graph G is k-regular if the degree of every vertex is k.
A vertex-cut in G is a set X of vertices of G such that G Oe X is disconnected.
The connectivity of a graph G, denoted by (G), is the least number of vertices of G whose removal results in a disconnected or trivial We say that the graph G is maximum connected if (G) = (G).
and G is superconnected if it is maximum connected and every minimum vertex-cut is composed of the neighborhood NG .
of a vertex u OO V .
Let A be a finite group, and let OI be a set of elements of A such that the identity of the group does not belong to OI.
The Cayley graph Cay(A.
OI) is the directed graph with vertex set consisting of the elements of G, and an arc is directed from u to v if and only if there is an s OO OI such that u = vs.
One of the main advantages of using Cayley graphs as models for interconnection networks is their vertex-transitivity, meaning that a graph viewed from any vertex looks the same.
however, its vertex connectivity may be low.
If whenever u OO OI, we also have its inverse uOe1 OO OI, then for every arc, the reverse arc is also in the graph, hence we can treat this Cayley graph as an undirected graph by replacing each pair of arcs by an edge.
In this paper, 1 2 a n we use .
1 p2 A A A pn ] to denote the permutation For example, the permutation p1 p2 A A A pn
1 2 3 4 5
= .
can be expressed in array form as = and its corresponding cycle 3 1 2 5 4 notation is = .
, 3, .
, .
A cycle .
, .
of length two is called transposition, and it swaps the numbers at positions i and j.
For example, .
1 p2 p3 A A A pnOe1 pn ].
, .
= .
1 pn p3 A A A pnOe1 p2 ].
Let Sn be the symmetric group, which is the set of permutations on .
= .
, 2, .
, .
, and let T be a set of transpositions.
We call G(T ) the transposition generating graph, where the vertex set of G(T ) is .
and its edge set is {.
, .
, .
OO T }.
We call G(T ) a transposition tree if G(T ) is a tree.
Neighbor connectivity of Cayley graphs generated by trees Let en denote the Cayley graph Cay(Sn .
T ), where G(T ) represents a transposition tree with n vertices.
As G(T ) has n Oe 1 edges, en is naturally .
Oe .
-regular and consists of n! vertices.
This family of Cayley graphs encompasses well-known examples, such as the star graph when G(T ) is isomorphic to K1,nOe1 , and the bubble-sort graph when G(T ) is isomorphic to Pn , a path with n vertices.
For a clearer understanding of en Aos structure, letAos simplify by assuming, without loss of generality, that n is a leaf in G(T ).
In the following proposition, we outline some fundamental characteristics of en .
Proposition 3.
, 17, .
Let en = Cay(Sn .
T ), where n Ou 4 and n is a leaf in G(T ).
(I) en consists of n vertex-disjoint subgraphs H1 .
H2 , .
Hn , where Hi is the subgraph induced by the vertex set {.
1 p2 A A A pnOe1 .
pj OO .
Oe .
, for j = 1, .
, n Oe .
Bounds of neighbor connectivity of Cayley graphs Abdallah (II) Hi O = enOe1 , where enOe1 = Cay(SnOe1 .
T A ) and G(T A ) is a transposition tree of nOe1 vertices.
If n is adjacent to t in G(T ), then .
, .
OO T and every vertex u OO V (Hi ) has exactly one neighbor, uA = u.
, .
, outside Hi .
The edge uuA is called a cross edge and the vertex uA is called outside neighbor of u.
(IV) Two distinct vertices in Hi have different outside neighbors.
(V) There are exactly .
Oe .
! cross edges between Hi and Hj , for 1 O i < j O n.
(VI) en is bipartite.
Lemma 3.
Let u and v be two distinct vertices of en , then u and v have at most two common Lemma 3.
Let u be a vertex in Hk for some k OO .
The maximum number of cross edges between Hi and Hj that are incident to NHi .
is n Oe 1.
Proof.
Consider the graph Cay(Sn .
T ), where G(T ) is a tree on n vertices.
Let .
, .
be an edge of this tree, where n is a leaf.
Without loss of generality, let u = () be in Hn , then the outside neighbor of u is in Hj .
Since n is a leaf, then j is a vertex of the tree and it is adjacent to another vertex k, hence .
, .
is a vertex in NHn .
, the closed neighborhood of u in Hn .
Moreover, .
, .
, .
= .
, n, .
which is a vertex in Hk .
As a result, u and the vertex .
, .
have different outside neighbors.
Since NHn .
contains n vertices, then the maximum number of cross edges between Hn and Hm that are incident to NHn .
is less than n, for m OO .
Oe .
Theorem 3.
Let n Ou 3, and let G be a Cayley graph obtained from a transposition generating graph A with m edges on .
, 2, .
, .
Then G is maximally connected.
Theorem 3.
1 leads to the following useful lemma.
Lemma 3.
For n Ou 3, .
n ) = n Oe 1.
Lemma 3.
Let n Ou 4 and U OI V .
n ), such that 1 O |U | O UO n2 UU Oe 1.
Then en On U is .
Oe 1 Oe .
U |)-connected.
Proof.
For n = 4, we find that |U | = 1, and e4 can be generated by either P4 or K1,3 .
We employed MathSage .
to confirm that, in both scenarios, e4 Oe N .
remains connected.
Since e4 is vertex transitive, we only had to remove the closed neighborhood of the vertex () = .
and examine the resulting graphAos connectivity.
For instance, in the case of the generating tree being K1,3 , we utilized the following code:
G=SymmetricGroup.
S=[.
] C=G.
cayley_graph.
enerators=S, simple=Tru.
U=C.
to_undirected() A=list(U.
neighbor_iterator(G(Ao()A.
, closed=Tru.
) delete_vertices(A) is_connected() Bounds of neighbor connectivity of Cayley graphs Abdallah We proceed with mathematical induction on n.
Assume that enOe1 On W is .
Oe 2 Oe .
W |)connected for every set W OI V .
nOe1 ), where 1 O |W | O UO nOe1 UU Oe 1.
Let U OI V .
n ), such that 1 O |U | O UO n2 UU Oe 1, and let F OI V .
n On U ), such that |F | O n Oe 2 Oe .
U |.
Our aim is to demonstrate that .
n On U ) Oe F is connected.
Define Ui = U O V (Hi ), ki = |N [U Oe Ui ] O V (Hi )|, and Fi = F O V (Hi ) for i OO .
We will consider cases based on the distribution of the vertices in U .
Case 1.
|U | = |Ui |, for some i OO .
Without loss of generality, suppose that i = 1.
Then all the vertices of U are in H1 and |Ui | = 0 for i OO .
Oe .
By Lemma 3.
Hi is .
Oe .
-connected and the maximum number of vertices in Hi O (N [U ] O F ) is |U | |F |, for i OO .
Oe .
Since |F | O n Oe 2 Oe .
U | and |U | Ou 1, then |U | |F | O n Oe 3, then by Lemma 3.
3 Hi Oe N [U ] Oe F is connected for i OO .
Oe .
Let i, j OO .
Oe .
such that i = j, then the number of cross edges between Hi Oe F and Hj Oe F is greater than .
Oe .
! Oe (|U | |F |) Ou .
Oe .
! Oe .
Oe .
Ou 1, for n Ou 5.
Therefore, there is a cross edge between Hi Oe F and Hj Oe F , hence the subgraph C induced by i=2 (V (Hi ) Oe N [U ]) Oe F is connected.
If (H1 Oe N [U ]) Oe F is connected, then .
n Oe N [U ]) Oe F is connected, since there are enough cross edges between (H1 Oe N [U ]) Oe F and In fact, when n Ou 5, using the inequality .
Oe .
! Oe |U | Ou .
Oe .
! Oe (UOn/2UU Oe .
Ou 5 for n Ou 5, the number of these cross edges between (H1 Oe N [U ]) Oe F and C is at least .
Oe .
! Oe .
Oe .
|U | Oe |F | Ou .
Oe .
Oe .
! Oe |U |] Oe |F | Ou 5.
Oe .
Oe |F | Ou 5n Oe 5 .
U | 2 Oe n Ou 4n Oe 3 .
U | Ou 4n Oe 1 Ou 19.
Suppose that (H1 Oe N [U ]) Oe F is not connected.
Let C1 be a connected component of (H1 Oe N [U ]) Oe F .
We want to show that there is a cross edge between C and C1 .
Subcase 1.
|V (C1 )| = 1.
Let V (C1 ) = .
, then x is an isolated vertex in (H1 Oe N [U ]) Oe F .
This can only happen if all the neighbors of x in H1 are adjacent to vertices of N [U1 ] O F1 .
Lemma 3.
1, a vertex of U can share at most two common neighbors with x, then degH1 .
O .
U | |F1 |, then n Oe 2 O .
U | |F1 |, so |F1 | Ou n Oe 2 Oe .
U |.
Then |F | = |F1 | and all the elements of F are in H1 .
By Proposition 3.
1, the outside neighbor of x does not belong to N [U ], and since |Fi | = 0 for i OO .
Oe .
, then the outside neighbor of x is in C.
Subcase 1.
|V (C1 )| Ou 2.
Let x and y be two adjacent vertices of C1 .
Since enOe1 is bipartite, then it contains no odd cycles, then |NC1 .
O NC1 .
| = 0.
The maximum number of vertices in N .
O N .
adjacent to N [U ] is .
U |.
in fact, if u OO U , then u can be adjacent to at most two vertices of x, and u cannot be adjacent to a vertex in N .
and to a vertex in N .
because this would create an odd cycle and this is not possible because en is bipartite.
The number of vertices Bounds of neighbor connectivity of Cayley graphs Abdallah in the subgraph induced by (N .
O N .
) Oe N [U ] is at least 2 2.
Oe .
Oe .
U | = 2n Oe 4 Oe .
U | = .
Oe .
Oe 2 Oe .
U |) Ou .
Oe .
|F | each of these .
Oe .
|F | vertices has an outside neighbor, then there are at least n Oe 2 outside neighbors in C adjacent to vertices in NH1 .
or NH1 .
As a result, there is always an edge between C1 and C, thus .
n On U ) Oe F is connected.
Case 2.
|Ui | O |U | Oe 1, for every i OO .
By the induction hypothesis, the subgraph induced by V (Hi ) Oe N [Ui ] is .
Oe 2 Oe .
Ui |)-connected.
We claim that (Hi Oe N [U ]) Oe F is connected, because if not, then ki |Fi | Ou n Oe 2 Oe .
Ui |, and since every vertex outside Hi may be adjacent to at most one vertex of Hi , then the maximum value of ki is |U | Oe |Ui |, and the maximum value of |Fi | is n Oe 2 Oe .
U |, then we have the inequality n Oe 2 Oe .
Ui | O |U | Oe |Ui | n Oe 2 Oe .
U |, and this implies that |U | O |Ui |, which is a contradiction.
In addition, since |U | O UO n2 UU Oe 1, then there exists j OO .
such that |Uj | = 0.
By Lemma 3.
2, when n Ou 5, the number of cross edges between (Hi Oe N [U ]) Oe F and (Hj Oe N [U ]) Oe F is at least .
Oe .
! Oe |F | Oe .
Oe .
|Ui | Ou .
Oe .
! Oe .
Oe 2 Oe .
U |) Oe .
Oe .
(|U | Oe .
Ou .
Oe .
! Oe n 2 Oe .
Oe .
|U | .
Oe .
Ou .
Oe .
! 1 Oe .
Oe .
|U | Ou1 Therefore, there is always a cross edge between (Hi Oe N [U ]) Oe F and (Hj Oe N [U ]) Oe F for every i OO .
Oe .
The maximum number of vertices of N [U ] O F removed from Hj is less than n Oe 2.
in fact |U | |F | O n Oe 2 Oe |U | O n Oe 3.
Then by Lemma 3.
3, the subgraph induced by (Hj Oe N [U ]) Oe F is connected.
Therefore .
n On U ) Oe F is connected.
By the previous lemma, we conclude that N B .
n ) Ou UO n2 UU.
We now give an upper bound for N B .
n ).
Lemma 3.
Let n Ou 4, then N B .
n ) O n Oe 1.
Proof.
Let x OO V .
n ), and let N .
= .
1 , x2 , .
, xnOe1 }.
Let U = .
1 , y2 , .
, ynOe1 } OI V .
n ) Oe N .
such that xi yi OO E.
n ), and yi = yj , for i, j OO .
Oe .
and i = j.
en does not contain odd cycles because it is bipartite, therefore x is not adjacent to yi for i OO .
Oe .
Then en Oe N [U ] is disconnected because x is an isolated vertex in it.
From the previous two lemmas, we deduce the following theorem.
Theorem 3.
Let n Ou 4, then UO n2 UU O N B .
n ) O n Oe 1.
Moreover, the bounds are tight.
Bounds of neighbor connectivity of Cayley graphs Abdallah Proof.
In .
, the authors proved that N B (Sn ) = n Oe 1, where Sn is the star graph.
Consider the bubble-sort graph Bn = Cay(Sn .
Pn ) where Pn is the path with vertex set V (Pn ) = .
and edge set E(Pn ) = {.
, i .
i OO .
Oe .
Without loss of generality, let u = () be the identity permutation, then N .
= {.
, i .
i OO .
Oe .
If n is even, then the set of vertices U = {.
, i .
Oe i, n Oe i .
i = 1, .
, n2 Oe .
O {( n2 , n2 .
, .
} is a vertex-cut strategy of size n2 .
Then U is a vertex-cut strategy.
If n is odd, let U = {.
, i .
(UO n2 UU i.
UO n2 UU i .
i = 1, .
UO n2 UU} is a vertex-cut strategy of size UO n2 UU.
Then N B (Bn ) O UO n2 UU, therefore N B (Bn ) = UO n2 UU.
Neighbor connectivity of Cayley graphs generated by unicyclic graphs In this section we consider Cayley graphs U Gn = Cay(Sn .
T ), where G(T ) is a unicyclic graph with vertex set .
Let Cn be the cycle of n vertices, and let Hn,p be the graph obtained by appending the cycle Cp to a pendant vertex of a path PnOep .
Hn,p is called lollipop graph.
The graph Hn,nOe1 consists of the cycle CnOe1 and one pendant vertex.
When G(T ) = Cn , then U Gn becomes the modified bubble-sort graph M Bn , and when G(T ) = Hn,nOe1 , then we will denote such graph by LGn .
Neighbor Connectivity of Modified Bubble-Sort Graph M Bn Suppose that the generating graph of M Bn .
G(T ) is Cn = .
, 2, .
n, .
Let T A = T Oe {.
, .
, .
Oe 1, .
}, then G(T A ) is a path of length n Oe 1, and Cay(SnOe1 .
T A ) is the .
Oe .
i be the subgraph of M Bn induced by the vertex set dimensional bubble-sort graph BnOe1 .
Let BnOe1 1 p2 .
pnOe1 .
pk OO .
Oe .
, for k = 1, .
, n Oe .
, then BnOe1 = BnOe1 .
Therefore.
M Bn can be decomposed into n vertex disjoint subgraphs BnOe1 , .
BnOe1 .
The following proposition includes some useful topological properties of M Bn .
Proposition 4.
Let M Bn be the n-dimensional modified bubble-sort graph, and let BnOe1 .
BnOe1 be the subgraphs defined above.
(I) M Bn is n-regular bipartite graph.
(II) If u OO V (BnOe1 ), then u has exactly two neighbors outside BnOe1 , called the outside neighbors of u.
The outside neighbors of BnOe1 are all different.
(IV) The outside neighbors of a vertex are located in different BnOe1 (V) There are exactly 2.
Oe .
! independent edges between BnOe1 and BnOe1 , for i, k OO .
and i = k.
Such edges are called cross edges.
Lemma 4.
Let u OO V (BnOe1 ) for some i OO .
, and let uA and uAA be its outside neighbors.
Then A AA u and u have no common neighbor in M Bn other than u.
Bounds of neighbor connectivity of Cayley graphs Abdallah Proof.
Without loss of generality, assume that u = (), then u OO V (BnOe1 Let uA = .
, .
and uAA = .
Oe 1, .
be the outside neighbors of u.
If there is a common neighbor for uA and uAA , then there exist two transpositions .
, .
, .
such that .
, .
, .
= .
Oe 1, .
, .
, equivalently .
, n Oe 1, .
, .
= .
, .
This situation occurs only if a, b OO .
, n Oe 1, .
, which means when .
, .
= .
, .
, .
= .
Oe 1, .
If .
, .
= .
, .
, then .
, .
= .
Oe 1, .
and the common vertex will be u = ().
If .
, .
= .
Oe 1, .
, then .
, .
= .
, n Oe .
, but this is not possible as .
, n Oe .
is not in the set of generating transpositions.
In the following lemma, we give an upper bound for N B (M Bn ).
Lemma 4.
Let n Ou 4, then N B (M Bn ) O UO n2 UO.
Proof.
Suppose that n is even, then the set of vertices U = {.
, i .
Oe i, n Oe i .
1, .
, n2 Oe.
O{( n2 , n2 .
, .
} is a vertex-cut strategy of size n2 because the vertex corresponding to the identity permutation () is isolated in M Bn On U .
Similarly, if n is odd, then U = {.
, i .
Oei, nOei .
i = 1, .
UO n2 UUOe.
O{(UO n2 UU.
UO n2 UU .
, .
, (UO n2 UU 1.
UO n2 UU .
(UO n2 UU 2.
UO n2 UU .
} is a vertex-cut strategy of size UO n2 UU 1 = UO n2 UO, because () becomes an isolated vertex in M Bn On U .
Therefore.
N B (M Bn ) O UO n2 UO.
Lemma 4.
Let n Ou 4 and u OO V (M Bn ).
Then M Bn On .
is connected.
Proof.
If u OO V (BnOe1 ), then by Theorem 3.
2 the graph BnOe1 On .
is connected, for n Ou 4.
Now O ) for some i OO .
Since BnOe1 let v OO V (M Bn ), then v OO V (BnOe1 = BnOe1 , then the graph induced by the vertices of BnOe1 OeN .
is connected.
By Proposition 4.
1, v has two outside neighbors v A and v AA in BnOe1 and BnOe1 respectively, where j, k OO .
Oe .
and j = k.
By Lemma 3.
BnOe1 Oe .
A } and BnOe1 Oe .
AA } are connected.
Since there are 2.
Oe .
! cross edges between every pair of the BnOe1 -subgraphs, then M Bn On .
is connected.
) for some i OO .
If u has its outside Lemma 4.
Let u OO V (M Bn ).
Suppose u OO V (BnOe1 A AA neighbors u and u in BnOe1 and BnOe1 for some j and k in .
Oe .
, then exactly .
Oe .
have their outside neighbors in BnOe1 of NM BnOe1 Proof.
Since M Bn is vertex transitive, then without loss of generality assume that u = () OO V (BnOe1 Then the outside neighbors of u are uA = .
, .
OO V (BnOe1 ) and uAA = .
Oe 1, .
OO nOe1 V (BnOe1 ).
The vertices corresponding to .
, .
, .
, .
Oe 2, n Oe .
are in NBnOe1 .
and they have their outside neighbors, .
, .
, .
, .
, .
, .
, .
, .
Oe 2, n Oe .
, .
, in BnOe1 .
Lemma 4.
Let n Ou 5 and U OI V (M Bn ), such that 2 O |U | O UO n2 UO Oe 1.
Then M Bn On U is .
Oe .
U |)-connected.
Proof.
Let F OI V (M Bn ), such that |F | O n Oe 1 Oe .
U |.
Our aim is to show that (M Bn On U ) Oe F is connected.
We consider cases depending on the distribution of the elements of U .
Let Ui = U O V (BnOe1 ), ki = |N [U Oe Ui ] O V (BnOe1 )|, and Fi = F O V (BnOe1 ), for i OO .
Case 1.
|U | = |U1 |.
For i OO .
Oe .
, |Fi | ki O .
Oe 1 Oe .
U |) |U | O n Oe 3 < deg(BnOe1 then by Lemma 3.
3, the subgraph induced by the vertices of (BnOe1 Oe N [U ]) Oe F is connected.
The number of cross edges between the subgraphs induced by (BnOe1 OeN [U ])OeF and (BnOe1 OeN [U ])Oe Bounds of neighbor connectivity of Cayley graphs Abdallah F , for 2 O i < j O n, is greater than 2.
Oe .
! Oe [.
Oe 1 Oe .
U |) .
U |] Ou 2.
Oe .
! Oe n 1 Ou 1, hence there is always a cross edge between these two subgraphs.
Then the subgraph C induced by Oe N [U ]) Oe F is connected, then ) Oe (N [U ] O F ) is connected.
If (BnOe1 the vertices of ni=2 V (BnOe1 the graph (M Bn On U ) Oe F becomes connected since there is at least one cross edge connecting a vertex from (BnOe1 Oe N [U ]) Oe F and a vertex from C.
Suppose that (BnOe1 Oe N [U ]) Oe F is not Let C1 be a connected component in (BnOe1 Oe N [U ]) Oe F .
A If C1 contains exactly one vertex u, then u must have an outside neighbor in C.
In fact, the maximum number of vertices in N [U ] O F adjacent to u is .
U | |F | = n Oe 1, and since degM Bn .
= n, then u must have at least one outside neighbor in C.
A If |C1 | Ou 2, then let u and v be two adjacent vertices in C1 .
Since M Bn contains no odd cycles, then |N .
O N .
| = 0.
The subgraph induced by (NBnOe1 .
O NBnOe1 .
) Oe (N [U ] O F ) contains at least 2nOe4Oe.
U |O.
F | vertices.
Since Oe.
U |O.
F | Ou 1Oen, then this subgraph contains at least n Oe 3 vertices.
On the other hand, |F | O n Oe 1 Oe .
U |, so |F | O n Oe 5.
Therefore, there must be a cross edge between C1 and C, and hence (M Bn On U ) Oe F is Case 2.
|Ui | O |U | Oe 1, for every i OO .
Oe N [U ]) Oe F is connected for every i OO .
Since |U | O Subcase 2.
Assume that (BnOe1 , for k OO .
, contain no elements of U , and UO 2 UO Oe 1, then at least half of the subgraphs BnOe1 therefore each such subgraph contains at most |U | .
Oe .
Oe .
U | O n Oe 3 vertices of N [U ] O F , then by Theorem 3.
1 these subgraphs are connected.
Without loss of generality, suppose that BnOe1 contains no elements of U , then U1 = OI.
For every i OO .
Oe .
, we want to show that there is a Oe N [U ]) Oe F , and hence (M Bn On U ) Oe F is Oe N [U ]) Oe F and (BnOe1 cross edge between (BnOe1 contribute to a maximum of By Lemma 4.
4, a vertex of Ui and its neighbors in BnOe1 n Oe 1 cross edges between BnOe1 and BnOe1 .
Then the maximum number of cross edges between BnOe1 and BnOe1 that are incident to elements of N [U ] O F is |F | .
Oe .
|U |, |F | .
Oe .
|U | O n Oe 1 Oe .
U | .
Oe .
|U | O n Oe 1 Oe .
Oe .
|U | O n Oe 1 Oe .
Oe .
(UOn/2UO Oe .
Given that the total number of cross edges is 2.
Oe.
! and it is greater than nOe1Oe.
Oe.
(UOn/2UOOe.
for n Ou 5, it follows that, for every i in .
Oe .
, there always exists a cross edge between (BnOe1 Oe N [U ]) Oe F and (BnOe1 Oe N [U ]) Oe F .
Consequently, (M Bn On U ) Oe F is connected.
Subcase 2.
Assume that there exists i OO .
for which (BnOe1 Oe N [U ]) Oe F is disconnected.
Without loss of generality, assume i = 1.
We have |U1 | O UO 2 UO Oe 2, and since UO n2 UO Oe 2 = UO nOe1 UU Oe 1.
Bounds of neighbor connectivity of Cayley graphs Abdallah then by Lemma 3.
BnOe1 Oe N [U1 ] is .
Oe 2 Oe .
U1 |)-connected, therefore |F1 | k1 Ou n Oe 2 Oe .
U1 | |F1 | |U | Oe |U1 | Ou n Oe 2 Oe .
U1 | |F1 | |U | Ou n Oe 2 Oe |U1 | |F1 | |U | > n Oe 2 Oe |U | |F1 | > n Oe 2 Oe .
U | |F1 | > |F | this is a contradiction, therefore (BnOe1 Oe N [U ]) Oe F is connected for every i OO .
, hence by Subcase 2.
1, (M Bn On U ) Oe F is connected.
Theorem 4.
Let n Ou 4, then N B (M Bn ) = UO n2 UO.
Proof.
Lemma 4.
3 and Lemma 4.
5 imply that N B (M Bn ) is greater than UO n2 UOOe1, then N B (M Bn ) Ou UO n2 UO.
By Lemma 4.
2, we have N B (M Bn ) O UO n2 UO, therefore N B (M Bn ) = UO n2 UO.
Neighbor Connectivity of LGn Suppose that the generating graph of LGn is G(T ) = Hn,nOe1 , which consists of the vertex set .
and edge set {.
, i .
, .
, nOe.
, .
, .
i = 1, .
, nOe.
Let T A = T Oe{.
, .
}, then G(T A ) is a cycle of length nOe1, and Cay(SnOe1 .
T A ) is the .
Oe.
-dimensional modified bubble-sort graph M BnOe1 .
Let M BnOe1 be the subgraph of LGn induced by the vertex set {.
1 p2 .
pnOe1 .
pk OO Oe .
, for k = 1, .
, n Oe .
, then M BnOe1 = M BnOe1 .
Therefore.
LGn can be decomposed , such that each one of them is isomorphic into n vertex disjoint subgraphs.
M BnOe1 , .
M BnOe1 to M BnOe1 .
Proposition 4.
Let LGn be the n-dimensional Cayley graph Cay(Sn .
Hn,nOe1 ).
(I) LGn is n-regular bipartite graph.
(II) If u OO V (M BnOe1 ), then u has exactly one neighbor outside M BnOe1 , called the outside neighbor of u.
The outside neighbors of M BnOe1 are all different.
(IV) There are exactly .
Oe .
! independent edges between M BnOe1 and M BnOe1 , for i, k OO .
and i = k.
Such edges are called cross edges.
Lemma 4.
Let u OO V (LGn ), for n Ou 4.
Suppose u OO V (M BnOe1 ) for some i OO .
If u has its A outside neighbor u in M BnOe1 for some j OO .
Oe .
, then exactly .
Oe .
vertices of NM BnOe1 .
have their outside neighbors in M BnOe1 .
Proof.
Since LGn is vertex transitive, then without loss of generality assume that u = ().
Then the outside neighbor of u.
uA = .
, .
, is in M BnOe1 The vertices corresponding to .
, .
, .
, .
Oe 2, n Oe .
are in NM BnOe1 .
and they have their outside neighbors in M BnOe1 Bounds of neighbor connectivity of Cayley graphs Abdallah Lemma 4.
Let n Ou 4 and U OI V (LGn ), such that 1 O |U | O UO n2 UO Oe 1.
Then LGn On U is .
Oe .
U |)-connected.
Proof.
Let F OI V (LGn ), such that |F | O n Oe 1 Oe .
U |.
Our aim is to show that (LGn On U ) Oe F is connected.
We consider cases depending on the distribution of the elements of U .
Let Ui = ), for i OO .
)|, and Fi = F O V (M BnOe1 ), ki = |N [U Oe Ui ] O V (BnOe1 U O V (M BnOe1 Case 1.
|U | = |U1 |.
For i OO .
Oe.
, |Fi | ki O .
Oe1Oe.
U |) |U | O nOe2 < deg(M BnOe1 then by Theorem 3.
1, the subgraph induced by the vertices of (M BnOe1 Oe N [U ]) Oe F is connected.
Oe The number of cross edges between the subgraphs induced by (M BnOe1 OeN [U ])OeF and (M BnOe1 N [U ]) Oe F , for 2 O i < j O n, is greater than .
Oe .
! Oe [.
Oe 1 Oe .
U |)] Ou .
Oe .
! Oe n 1 Ou 1, for n Ou 4, hence there is always the subgraph C Sn a crossi edge between these two subgraphs.
Then induced by the vertices of i=2 V (M BnOe1 ) Oe (N [U ] O F ) is connected.
If (M BnOe1 Oe N [U ]) Oe F is connected, then the graph (LGn On U ) Oe F becomes connected since there is at least one cross edge connecting a vertex from (M BnOe1 Oe N [U ]) Oe F and a vertex from C.
In fact, there are , if the closed neighborhood of a vertex .
Oe .
Oe .
! cross edges incident to vertices in M BnOe1 is removed from the graph, then this contributes to at most .
Oe .
cross edges.
Then the number of cross edges between (M BnOe1 Oe N [U ]) Oe F and C is .
Oe .
Oe .
! Oe (|F | .
Oe .
|U |) Ou .
Oe .
! Oe .
Oe 1 Oe .
U | .
Oe .
|U |) Ou .
Oe .
! Oe n 1 Oe .
Oe .
|U | Ou .
Oe .
! Oe n 1 Oe .
Oe .
Ou 3.
Oe N [U ]) Oe F is not connected.
Let C1 be a connected component in Suppose that (M BnOe1 (M BnOe1 Oe N [U ]) Oe F .
Subcase 1.
C1 contains exactly one vertex u.
The maximum number of vertices in N [U ] O F .
, then all the vertices of F must be in adjacent to u is .
U | |F | = n Oe 1 = degM BnOe1 M BnOe1 .
By Lemma 4.
2, a vertex of U cannot be adjacent to the outside neighbor of u, and since degLGn .
= n, then the outside neighbor of u must be in C.
Subcase 1.
C1 contains at least two vertices.
Let u and v be two adjacent vertices in C1 .
Since LGn contains no odd cycles, then |N .
O N .
| = 0.
The subgraph induced by (NM BnOe1 .
O NM BnOe1 .
)Oe(N [U ]OF ) contains at least 2nOe2Oe.
U |O.
F | vertices.
Since Oe.
U |O.
F | Ou 1Oen, then this subgraph contains at least n Oe 1 vertices.
A vertex in U can not have an outside neighbor that belongs to N [U ].
On the other hand, |F | O n Oe 1 Oe .
U |, so |F | O n Oe 5.
Therefore, there must be a cross edge between C1 and C, and hence (LGn On U ) Oe F is connected.
Case 2.
|Ui | O |U | Oe 1, for every i OO .
Subcase 2.
Assume that (M BnOe1 Oe N [U ]) Oe F is connected for every i OO .
Since |U | O UO 2 UO Oe 1, then at least half of the subgraphs M BnOe1 , for k OO .
, contain no elements of U .
Suppose that U1 = U2 = OI, it is easy to see that the subgraph C induced by V (M BnOe1 V (M BnOe1 ) is connected.
We want to show that there is always an edge between M BnOe1 and C, for i OO .
Oe .
, .
The number of cross edges between M BnOe1 and M BnOe1 is .
Oe .
! Oe .
Oe 1 Oe .
U | .
Oe .
|Ui | |U | Oe |Ui |).
We are removing all cross edges incident to vertices of F .
Bounds of neighbor connectivity of Cayley graphs Abdallah N [Ui ], and U Oe Ui .
This number is equal to .
Oe .
! Oe .
Oe 1 Oe |U | .
Oe .
|Ui |).
We have .
Oe .
! Oe .
Oe 1 Oe |U | .
Oe .
|Ui |) Ou .
Oe .
! Oe .
Oe 1 Oe |U | .
Oe .
(|U | Oe .
) Ou .
Oe .
! Oe .
Oe .
|U |) Ou2 then there is a an edge between C and M BnOe1 for every i OO .
Oe .
, .
, therefore (LGn On U ) Oe F is connected.
Oe N [U ]) Oe F is disconnected.
Subcase 2.
Assume that there exists i OO .
for which (M BnOe1 Without loss of generality, assume i = 1.
We have |U1 | O UO 2 UO Oe 2, and since UO n2 UO Oe 2 O UO nOe1 UO Oe 1, then by Lemma 4.
M BnOe1 Oe N [U1 ] is .
Oe 1 Oe .
U1 |)-connected, therefore |F1 | k1 Ou n Oe 1 Oe .
U1 | |F1 | |U | Oe |U1 | Ou n Oe 1 Oe .
U1 | |F1 | |U | Ou n Oe 1 Oe |U1 | |F1 | |U | > n Oe 1 Oe |U | |F1 | > n Oe 1 Oe .
U | |F1 | > |F | this is a contradiction, therefore (M BnOe1 Oe N [U ]) Oe F is connected for every i OO .
, hence by Subcase 2.
1, (LGn On U ) Oe F is connected.
In the following lemma, we determine the value of N B (LGn ).
Lemma 4.
Let n Ou 4, then N B (LGn ) = UO n2 UO.
Proof.
From Lemma 4.
7, we conclude that N B (LGn ) Ou UO n2 UO.
To show that N B (LGn ) O UO n2 UO, we will construct a vertex-cut strategy of size UO n2 UO.
Assume n is even, then the set of vertices U = {.
2, i .
Oe2Oei, nOe1Oe.
i = 1, .
, n2 Oe.
O{( n2 , n2 .
, .
, .
, .
Oe2, nOe.
, .
, .
, nOe.
} is a vertex-cut strategy of size n2 because the vertex corresponding to the identity permutation () is isolated in LGn On U .
Similarly, if n is odd, then U = {.
, i .
Oe 1 Oe i, n Oe .
2, .
, nOe1 Oe .
O {.
, .
( n 1 , n 1 .
, .
, n Oe .
( nOe1 , nOe1 .
, .
, .
, .
} is a vertex-cut strategy of size 2 = UO 2 UO, because () becomes an isolated vertex in LGn On U .
Therefore.
N B (LGn ) O UO n2 UO.
Neighbor Connectivity of Un Let Un = Cay(Sn .
T ) where G(T ) is not Cn nor Hn,nOe1 , then the generating graph G(T ) has always a vertex of degree 1, without loss of generality, let n be such vertex, and let j be the neighbor of n in G(T ).
Let T A = T Oe {.
, .
}, then T A is a set of transpositions of SnOe1 , and G(T A ) is a unicyclic graph on the vertex set .
Oe .
Let UinOe1 be the subgraph of Un induced by the set of vertices {.
1 p2 .
pnOe1 .
pk OO .
Oe .
for k = 1, .
, n Oe .
, then UinOe1 O = UnOe1 .
Therefore.
Un can be decomposed into n vertex disjoint subgraphs U1nOe1 , .
UnnOe1 .
The following proposition includes useful topological properties of Un .
Bounds of neighbor connectivity of Cayley graphs Abdallah Proposition 4.
Let Un = Cay(Sn .
T ) where G(T ) is a unicyclic graph of vertex set .
different from Cn and Hn,nOe1 , and let U1nOe1 , .
UnnOe1 be the subgraphs defined previously.
(I) Un is n-regular bipartite graph.
(II) If u OO V (UinOe1 ), then u has exactly one neighbor, uA , outside UinOe1 .
uA is called the outside neighbor of u, and uA = u.
, .
The outside neighbors of the vertices in UinOe1 are all different.
(IV) There are exactly .
Oe .
! independent edges between UinOe1 and UknOe1 , for i, k OO .
and i = k.
Such edges are called cross edges.
Lemma 4.
Let m be the length of the unique cycle in G(T ).
Let u and v be two distinct vertices of Un = Cay(Sn .
T ).
Then |N .
O N .
| O 3 if m = 3, and |N .
O N .
| O 2 if m Ou 4.
Lemma 4.
Let n Ou 4 and let Un = Cay(Sn .
T ), where G(T ) is a unicyclic graph on the vertex set .
and the length of its cycle is 3.
Suppose u OO V (UinOe1 ) for some i OO .
If u has its outside neighbor uA in UjnOe1 for some j OO .
Oe .
, then at most n Oe 3 vertices in NUinOe1 .
have their outside neighbors in UjnOe1 .
Proof.
Since Un is vertex transitive, then without loss of generality assume that u = ().
The generating graph G(T ) consists of a 3-cycle with edges corresponding to the transpositions .
, .
, .
, .
, and .
, .
At least one of the vertices 1, 2 or 3 belongs to a tree that does not include the other two vertices.
It is possible to have the following scenario.
, .
is an edge of G(T ) and vertices 2 and 3 are vertices that belong to disjoint trees.
Then every vertex of NUnOe1 .
, except the vertices corresponding to .
, .
, .
have their outside neighbors in U1nOe1 .
Lemma 4.
Let n Ou 4 and let Un = Cay(Sn .
T ), where G(T ) is a unicyclic graph on the vertex set .
and the length of its cycle is 3.
Let U OI V (Un ), such that 1 O |U | O UO n2 UU Oe 1.
Then Un On U is .
Oe 1 Oe .
U |)-connected.
Proof.
When n = 4, then U4 is the same as LG4 , then by Lemma 4.
7 the result holds.
We proceed by mathematical induction on n.
Suppose that UnOe1 OnW is .
Oe2Oe.
W |)-connected, for every set W OI V (UnOe1 ) such that 1 O |W | O UO nOe1 UU Oe 1.
Let U OI V (Un ), such that 1 O |U | O UO n2 UU Oe 1 and let F OI V (Un ), such that |F | O n Oe 2 Oe .
U |.
Our aim is to show that (Un On U ) Oe F is connected.
We consider cases depending on the distribution of the elements of U .
Let Ui = U O V (UinOe1 ), ki = |N [U Oe Ui ] O V (UinOe1 )|, and Fi = F O V (UinOe1 ), for i OO .
Case 1.
|U | = |U1 |.
For i Ou 2, |Fi | ki O .
Oe 2 Oe .
U |) |U | O n Oe 3 < (UinOe1 ), then by Theorem 3.
1, the subgraph induced by the vertices of (UinOe1 OeN [U ])OeF is connected.
The number of cross edges between the subgraphs induced by (UinOe1 Oe N [U ]) Oe F and (UjnOe1 Oe N [U ]) Oe F , for 2 O i < j O n, is greater than .
Oe .
! Oe [.
Oe 2 Oe .
U |) |U |] Ou .
Oe .
! Oe .
Oe .
Ou 1, for n Ou 5, hence there is always edge between these two subgraphs.
Then the subgraph C Sn a cross induced by the vertices of i=2 V (UnOe1 ) Oe (N [U ] O F ) is connected.
If (U1nOe1 Oe N [U ]) Oe F is Bounds of neighbor connectivity of Cayley graphs Abdallah connected, then the graph (Un On U ) Oe F becomes connected since there is at least one cross edge connecting a vertex from (U1nOe1 Oe N [U ]) Oe F and a vertex from C.
In fact, the number of cross edges between (U1nOe1 Oe N [U ]) Oe F and C is .
Oe .
Oe .
! Oe (|F | .
Oe .
|U |) Ou .
Oe .
! Oe .
Oe 2 Oe .
U | .
Oe .
|U |) Ou .
Oe .
! Oe n 2 Oe .
Oe .
|U | Ou .
Oe .
! Oe n 2 Oe .
Oe .
Ou 4.
Suppose that (U1nOe1 Oe N [U ]) Oe F is not connected.
Let C1 be a connected component in (U1nOe1 Oe N [U ]) Oe F .
Subcase 1.
C1 contains exactly one vertex u, then u is isolated in U1nOe1 .
The maximum number of vertices of NU1nOe1 .
that are adjacent to N [U1 ] is 3 2(|U | Oe .
, then 3 2(|U | Oe .
|F1 | Ou degU1nOe1 .
U | 1 |F1 | Ou n Oe 1 |F1 | Ou n Oe 2 Oe .
U | |F1 | Ou |F | In this situation |Fi | = 0 for every i OO .
Oe .
, then the outside neighbor of u is a vertex in C, therefore there is an edge between C1 and C.
Subcase 1.
C1 contains more than one vertex.
Let u, v OO V (C1 ) such that u and v are adjacent in C1 .
Since Un is bipartite, then it does not contain an odd cycle, therefore u and v have no common neighbors.
The subgraph induced by (N .
ON .
)OV (U1nOe1 ) contains 2nOe2 vertices.
A vertex of U can not be adjacent to a neighbor of u and a neighbor of v at the same time because this would create an odd cycle.
Then the maximum number of vertices of NU1nOe1 .
O NU1nOe1 .
that are in N [U1 ] is 3 3 2(|U |Oe.
= .
U | 2.
Then there are at least .
nOe.
Oe.
U | .
= 2nOe.
U | vertices in the subgraph induced by [(N .
O N .
) O V (U1nOe1 )] Oe N [U ].
Since |F | < 2n Oe .
U |, then there exists at least one cross edge incident to a vertex of C1 and a vertex of C.
Case 2.
|Ui | O |U | Oe 1, for i OO .
We have |Ui | O UO n2 UU Oe 2, then at least two of the UinOe1 subgraphs contain no elements of U , for i OO .
Let U1nOe1 and U2nOe1 be these subgraphs.
By Theorem 3.
U1nOe1 and U2nOe1 are .
Oe .
-connected.
The maximum number of vertices of N [U ] O F in U1nOe1 is |U | |F | O n Oe 2 Oe |U | O n Oe 2, then (U1nOe1 On U ) Oe F is connected.
Since |UnOe1 | O UO n2 UU Oe 2 O UO nOe1 UU Oe 1, for n Ou 5, then by the induction hypothesis.
UinOe1 is .
Oe 2 Oe .
Ui |)-connected.
On the other hand, |F | N [U Oe Ui ] O n Oe 2 Oe .
U | |U | Oe |Ui | O n Oe 2 Oe |U | Oe |Ui | O n Oe 2 Oe |Ui | Oe 1 Oe |Ui | O n Oe 3 Oe .
Ui | < n Oe 2 Oe .
Ui | Bounds of neighbor connectivity of Cayley graphs Abdallah then (UinOe1 On U ) Oe F is connected, for i OO .
Oe .
, .
By Proposition 4.
3, there are .
Oe .
! cross edges between UinOe1 and U1nOe1 , for i OO .
Oe .
, .
If x OO Ui , then by Lemma 4.
10 NUinOe1 .
contributes to at most n Oe 2 cross edges between UinOe1 and U1nOe1 .
When n Ou 5, we have .
Oe .
! Oe .
Oe .
|Ui | Oe |F | Ou .
Oe .
! Oe .
Oe .
(|U | Oe .
Oe .
Oe 2 Oe .
U |) Ou .
Oe .
! Oe .
U | Ou .
Oe .
! Oe n(UOn/2UU Oe .
Ou1 then there exists at least one cross edge between (UinOe1 On U ) Oe F and (U1nOe1 On U ) Oe F for i OO .
Oe .
, .
, and since there are enough edges between (U1nOe1 On U ) Oe F and (U2nOe1 On U ) Oe F , then (Un On U ) Oe F is connected.
The previous lemma implies that when the length of the cycle in G(T ) is 3, then the value of N B (Un ) is greater than UO n2 UU Oe 1.
The next lemma provides an upper bound for N B (Un ) when the length of the cycle in G(T ) is 3.
Lemma 4.
Let n Ou 4 and let Un = Cay(Sn .
T ), where G(T ) is a unicyclic graph on the vertex set .
, where the length of the cycle in G(T ) is 3.
Then UO n2 UU O N B (Un ) O n Oe 2.
Proof.
By Lemma 4.
11, we have N B (Un ) Ou UO n2 UU.
Let {.
, .
, .
, .
, .
, .
} be the edges of the 3cycle of G(T ).
The vertex () is adjacent to .
, .
, .
, .
, .
, .
and n Oe 3 other vertices corresponding to the remaining edges of G(T ).
Let u1 , .
, unOe3 be these vertices, and let uAi be a vertex adjacent to ui such that uAi = (), for i = 1, .
, nOe3.
If U consists of {.
, 2, .
, uAi .
for i = 1, .
nOe.
then the vertex () is isolated in Un On U because .
, 2, .
is adjacent to .
, .
, .
, .
, .
, .
, and uAi is adjacent to ui for i = 1, .
n Oe 3.
Therefore N B (Un ) O n Oe 2.
Now we will show that bounds of N B (Un ) are tight.
In the next lemma, we find a generating graph for which the lower bound of N B (Un ) is attained.
Lemma 4.
Let n Ou 4 and let Un = Cay(Sn .
T ), where G(T ) is the graph consisting of vertex set .
and edge set {.
, .
, .
, .
, .
, .
, .
, i .
for i = 3, .
, n Oe .
Then N B (Un ) = UO n2 UU.
Proof.
We want to construct a vertex-cut strategy U such that |U | O UO n2 UU.
Case 1.
n is even.
Let U = {.
, 2, .
, n2 1, n2 2 .
, .
, .
3, i .
Oe1Oei, nOe.
for i = 0, .
, n2 Oe .
The vertex () is isolated in Un On U , and |U | = 2 n2 Oe 2 = n2 .
Case 2.
n is odd.
Let U = {.
, 2, .
, .
3, i .
n 3 i, n 5 i .
for i = 0, .
, nOe5 nOe5 nOe1 The vertex () is isolated in Un On U , and |U | = 1 2 1 = 2 = UO 2 UU.
Then N B (Un ) = UO 2 UU when G(T ) is the graph of vertex set .
and edge set {.
, .
, .
, .
, .
, .
, .
, i .
for i = 3, .
, n Oe .
Lemma 4.
Let n Ou 4 and let Un = Cay(Sn .
T ), where G(T ) is the graph consisting of vertex set .
and edge set {.
, .
, .
, .
for i = 2, .
, .
Let x OO V (UinOe1 ), for some i OO .
Then NUinOe1 .
= .
1 , .
, xiOe1 , xi 1 , .
, xn }, where xj has its outside neighbor xAj in UjnOe1 , for j OO .
Oe .
Moreover, if the outside neighbor of x, xA , is in UknOe1 , for k OO .
Oe .
, then .
, xA , xAk , xk , .
is a 4-cycle.
Bounds of neighbor connectivity of Cayley graphs Abdallah Proof.
Since Un is a Cayley graph, then it is vertex transitive.
Without loss of generality, assume that x = () is a vertex in UnnOe1 , then NU1nOe1 .
= {.
, .
, .
, .
, .
, .
, .
, .
, n Oe .
Let x1 = .
, .
and xi = .
, .
, for i OO .
Oe .
Oe .
The outside neighbor of x1 is xA1 and it corresponds to the permutation .
, .
, .
which is a vertex in U1nOe1 .
The outside neighbor of xi is xAi and it corresponds to the permutation .
, .
, .
= .
, n, .
which is a vertex in UinOe1 , for i OO .
Oe .
In addition, the outside neighbor of x is the vertex xA in U1nOe1 , and xA = .
, .
It is easy to see that .
, xA , xA1 , x1 , .
is a 4-cycle.
Lemma 4.
Let n Ou 4 and let Un = Cay(Sn .
T ), where G(T ) is the graph consisting of vertex set .
and edge set {.
, .
, .
, .
for i = 2, .
, .
Let U OI V (Un ), such that 1 O |U | O n Oe 3.
Then Un On U is .
Oe 2 Oe |U |)-connected.
Proof.
When n = 4, then |U | = 1 and the case is the same as the base case of the proof of Lemma 4.
We proceed using mathematical induction.
Suppose that UnOe1 On U A is .
Oe 3 Oe |U A |)connected, where UnOe1 = Cay(SnOe1 .
T A ), and G(T A ) is the graph consisting of vertex set .
Oe .
and edge set {.
, .
, .
, .
for i = 2, .
, n Oe .
, and U A OI V (UnOe1 ) such that 1 O |U A | O n Oe 4.
Let F OI V (Un ), such that |F | O n Oe 3 Oe |U |.
We want to show that (Un On U ) Oe F is connected.
We consider cases depending on the distribution of the elements of U .
Let Ui = U O V (UinOe1 ), ki = |N [U Oe Ui ] O V (UinOe1 )|, and Fi = F O V (UinOe1 ), for i OO .
Case 1.
|U1 | = |U |.
For i OO .
Oe .
, |Fi | ki O n Oe 3 Oe |U | |U | O n Oe 3.
Then (UinOe1 Oe N [U ]) Oe F is connected for i OO .
Oe .
The number of cross edges between UinOe1 and UjnOe1 is .
Oe .
!, for i, j OO .
Oe .
and i = j, at most |F | |U | of these edges are incident to vertices of F or to vertices of N [U ].
Since |F | |U | O n Oe 3 and .
Oe .
! > n Oe 3 for n Ou 5, then there is always between (UinOe1 OeN [U ])OeF and (UjnOe1 OeN [U ])OeF .
Let C be the graph Sn a cross edge induced by i=2 (V (UinOe1 ) Oe N [U ]) Oe F , then C is connected.
If (U1nOe1 Oe N [U ]) Oe F is connected, then the number of cross edges between (U1nOe1 OeN [U ])OeF and C is .
Oe.
Oe.
!Oe.
U | |F |).
for n Ou 5, we have .
U | |F | O .
U | n Oe 3 Oe |U | O .
Oe .
|U | .
Oe .
O .
Oe .
Oe .
Oe .
O n.
Oe .
< .
Oe .
! then there is always a vertex in (U1nOe1 Oe N [U ]) Oe F having its outside neighbor in C, therefore (Un Oe N [U ]) Oe F is connected.
Suppose that (U1nOe1 Oe N [U ]) Oe F is not connected, we will show that there is a cross edge between every connected component of (U1nOe1 Oe N [U ]) Oe F and C.
Let C1 be a connected component in (U1nOe1 Oe N [U ]) Oe F .
Subcase 1.
|V (C1 )| = 1.
C1 consists of one vertex u that is isolated in (U1nOe1 Oe N [U ]) Oe F , |U | 2 |F1 | Ou degU1nOe1 .
|F1 | Ou n Oe 3 Oe |U | |F1 | Ou |F | Bounds of neighbor connectivity of Cayley graphs Abdallah then |F | = |F1 |, therefore the outside neighbor of u is not in F and by Lemma 4.
3 u is not in N [U ], then it must be in C, and hence there is a cross edge between C1 and C.
Subcase 1.
|V (C1 )| > 1.
Let x and y be two adjacent vertices in C1 .
Since Un is bipartite, then it does not contain odd cycles, therefore x and y have no common neighbor in Un .
The subgraph induced by NU1nOe1 .
O NU1nOe1 .
contains 2n Oe 2 vertices.
A vertex of N [U ] can not be adjacent to a vertex in NU1nOe1 .
and a vertex in NU1nOe1 .
since this will create an odd cycle.
The adjacent to x that are adjacent to vertices of N [U ] is |U | 2.
maximum number of vertices in UnOe1 Similarly, the maximum number of vertices in U1nOe1 adjacent to y that are adjacent to vertices of N [U ] is |U | 2.
There is at most two vertices in U such that, one of them is adjacent to three neighbors of x and the other is adjacent to three neighbors of y, and every other element of U can be adjacent to at most one neighbor of x or to at most one neighbor of y.
Then the maximum number of vertices of NU1nOe1 .
ONU1nOe1 .
that are in N [U ] is 6 (|U |Oe.
= |U | 4 O n 1.
Then the subgraph induced by (NU1nOe1 .
O NU1nOe1 .
) Oe N [U ] contains at least 2n Oe 2 Oe .
= n Oe 3 vertices, and since |F | < n Oe 3, then there is always a vertex in C1 that has an outside neighbor in C, hence there is a cross edge between C and C1 in (Un OeN [U ])OeF .
As a result (Un OeN [U ])OeF is connected.
Case 2.
|Ui | < |U | for every i OO .
By the induction hypothesis.
UinOe1 On Ui is .
Oe 3 Oe |Ui |)connected, for i OO .
If (UinOe1 Oe N [U ]) Oe F is connected for every i OO .
, then (Un Oe N [U ]) Oe F is connected.
Suppose that (UinOe1 Oe N [U ]) Oe F is disconnected for some i OO .
Without loss of generality, suppose that i = 1, then |F1 | (|U | Oe |U1 |) Ou n Oe 3 Oe |U1 |, then |F1 | |U | Ou n Oe 3, then |F1 | Ou n Oe 3 Oe |U | Ou |F |, therefore |F1 | = |F |.
Then all the elements of F are in U1nOe1 and |Fi | = 0 for i OO .
Oe .
Let C1 be a connected component of (U1nOe1 Oe N [U ]) Oe F .
Subcase 2.
|C1 | = 1.
Let C1 = .
, where x is an isolated vertex in U1nOe1 Oe (N [U ] O F ).
Then, |F1 | (|U1 | .
k1 Ou n Oe 1 k1 Ou n Oe 1 Oe |F1 | Oe |U1 | Oe 2 k1 Ou n Oe 3 Oe |F1 | Oe |U1 | k1 Ou |U | Oe |U1 | then k1 = |U | Oe |U1 |, which means that every element of U Oe U1 has its outside neighbor in NU1nOe1 .
However.
By Lemma 4.
14 this can only happen if no two vertices of U Oe U1 belong to the same UinOe1 -subgraph.
Then |Ui | O 1 for i OO .
Oe .
, and by the induction hypothesis UinOe1 On Ui is .
Oe .
-connected.
Since |U1 | < |U |, then |U1 | O n Oe 4.
There could be at most one subgraph of UinOe1 On Ui for i OO .
, say U2nOe1 On U2 , that is disconnected.
Let C be the SnOe .
subgraph induced by the vertices of i=3 (UnOe1 Oe N [U ]) Oe F , then C is connected.
Let xA be the outside neighbor of x.
If xA is in C, then the case is done.
Suppose that xA is in U2nOe1 Oe N [U ], since |U2 | O 1, then U2 contains at most one vertex a which has its outside neighbor in NU1nOe1 .
, and a cannot be adjacent to a neighbor of xA , because if this is the case then we will have a 5-cycle.
By Lemma 4.
14, all the neighbors of xA except one .
hich is xA2 , the outside neighbor of x2 ) are in (U2nOe1 Oe N [U ]) Oe F , then xA has a neighbor that has its outside neighbor in C, therefore there exists a path from x to C in (Un On U ) Oe F .
Bounds of neighbor connectivity of Cayley graphs Abdallah Subcase 2.
|C1 | > 1.
let x and y be two vertices of C1 such that x and y are adjacent.
Let H be the subgraph induced by the vertices of (NU1nOe1 .
O NU1nOe1 .
) Oe (N [U ] O F ).
H has at least .
n Oe .
Oe (|U1 | .
Oe |F | vertices.
Suppose that there exists i OO .
Oe .
such that (UinOe1 Oe N [U ]) Oe F is not connected.
Without loss of generality, suppose that (U2nOe1 Oe N [U ]) Oe F is not connected, then k2 Ou n Oe 3 Oe |U2 |, then |U | Oe |U2 | Ou n Oe 3 Oe |U2 |, then |U | Ou n Oe 3, hence |U | = n Oe 3 and |F | = 0.
We have the following inequalities k1 Ou n Oe 3 Oe |U1 | and k2 Ou n Oe 3 Oe |U2 |, then k1 k2 Ou 2.
Oe .
Oe (|U1 | |U2 |) Ou .
U | Oe |U | Ou |U | this means Sn that k1i k2 = |U |, and ki = 0 for i OO .
Oe .
, .
Let C be the graph induced by the i=3 V (UnOe1 ) Oe (N [U ] O F ).
Since |Fi | ki = 0, then by the induction hypothesis (UinOe1 Oe N [U ]) Oe F is connected for i OO .
Oe .
, .
, and hence C is connected.
Since |F | = 0, then H has at least n Oe 2 vertices because .
n Oe .
Oe (|U1 | .
Oe |F | > .
n Oe .
Oe (|U | .
Oe |F | Ou 2n Oe 2 Oe |U | Oe 4 Ou 2n Oe 6 Oe .
Oe .
Ou n Oe 3.
For n Ou 5.
H contains at least three vertices and by Lemma 4.
14 at most two of them can be in U2nOe1 , then a vertex of H has outside neighbor in C.
The same approach can be used to show that for every connected component of (UnOe2 Oe N [U ]) Oe F there exists an edge .
r pat.
connecting a vertex of C1 with a vertex in C.
Lemmas 4.
11, 4.
13, and 4.
15 provide the following result.
Theorem 4.
Let n Ou 4 and let Un = Cay(Sn .
T ), where G(T ) is a unicyclic graph on n where the length of the cycle in G(T ) is 3.
Then UO n2 UU O N B (Un ) O n Oe 2.
Moreover, the bounds are Conclusion In this paper, we determined the neighbor connectivity of Cay(Sn .
T ), where G(T ) is a tree with n vertices, a unicyclic graph with n vertices where the unique cycle is of length 3, n Oe 1, or n.
The methods employed to derive the outcomes presented in this paper can be extended to determine the neighbor connectivity in cases where the length of the cycle in a unicyclic graph falls between 3 and n Oe 1.
We put forth the following conjecture.
Conjecture 1.
Let n Ou 6 and let Un = Cay(Sn .
T ), where G(T ) is a unicyclic graph on the vertex set .
Let m be the length of the cycle in G(T ) such that 4 O m O n Oe 1.
Bounds of neighbor connectivity of Cayley graphs Abdallah If n Ou 2m Oe 4, then UOn/2UO O N B (Un ) O n Oe m 2 If n < 2m Oe 4, then UOn/2UO O N B (Un ) O n Oe m 2 UO 2mOenOe4 Moreover, the bounds are tight.
References