### A Study on the Toughness of Certain Graphs

**V. Jude Annie Cynthia and N. R. Swathi**

Department of Mathematics,Stella Maris College, Chennai - 86, INDIA.

email: swathibindu201@gmail.com

(Received on: November 1, Accepted: November 5, 2017)

**ABSTRACT**

Toughness is the measure of tightness of a graph, denoted as t(G) or t. It is the ratio of the number of vertices, whose removal increases the number of components of the graph, to the number of components of the graph. In this paper, we investigate the bound for toughness of the generalised prism graph and cyclic split graph.

**Keywords:**Toughness, Generalised prism graphs, Cyclic split graphs.

**INTRODUCTION**

Toughness is the measure of tightness of a graph (i.e.), it enhances on how tightly various components of the graph are binded together. This measure shows the strength of connectivity of the graph. Connectivity of a graph focuses only on the vertices of the minimum cut-set, wherein there is always an ambiguity in the number of components. Hence, a stronger concept over connectivity was introduced which ensures the stability of the graph with respect to its cut-set and the corresponding number of components.

This concept plays an important role in the stability of an interconnection network as it defines how tightly each of its components are binded together. An interconnection network, whose toughness is high, is a strong network. Toughness is the ratio of the number of vertices to the number components (at least two) obtained by the removal of those vertices. Hence, for an interconnection network to be strong, it requires to remove a large number of vertices to disconnect it into at least two components. Toughness has adverse applications on the reliability of an interconnection network as this value depends not just on the cut-sets but also on the components the network is distorted into.

Toughness is a better measure when compared to connectivity as toughness characterises the graph over all possible and varied cut-sets and their corresponding number of components obtained, while connectivity depends on the minimum cut-set without taking the corresponding number of components into consideration. This betterment over connectivity helps in studying and characterising the tightness and stability of a graph more effectively.

A graph G is said to be t - tough^{2} if t is the largest real number such that for any subset S of the vertices of G, the number of vertices in S is at least t times the number of components of G on deletion of the vertices in S, provided that there are at least two components. A graph G, for a real number t, is said to be t- tough if tw(G-S)≤|S|, ranging over all possible cutsets S of G (i.e.), w(G-S)>1.Toughness t of a graph G is a range of bounded values as it varies with the cardinality of the corresponding cut-set. Hence, toughness t comprises of a range of cutset's cardinalities and a range of their corresponing number of components. We infer the following on this range of values:

**Proposition 1.1.**G is highly tough if cardinality of the cut-set is always greater than it's corresponding number of components.

Usually, finding the upper bound for the toughness of a graph is difficult. Naturally, we always look for the lowest bound of toughness of a graph. While computing the toughness of an interconnection network, it is necessary to investigate the lower bound. Hence, toughness t of a graph G can be defined as t=min{|s|w(G-S),w(G-S)>1}, where S ⊂ V ranges over all possible cut-sets of V.

The relation between toughness and hamilton cycles of graphs has been studied as follows:

**Theorem 1.1 [2]:** Every hamiltonian graph is 1 - tough.

It is shown that every hamilton graph is necessarily 1 - tough because if a graph is hamiltonian, then each of its vertex lies on a hamilton cycle which implies that it is necessary to remove at least 2 vertices to disconnect the graph into atleast 2 components.

In this paper, we discuss the bound for toughness of the generalised prism graph denoted as *Z _{ns}*,n,n ≥1,1 ;≤n ≥ and cyclic split graph denoted asC

_{n}K

_{r}

*k*,n≥3,n≥3,

*k*≥1.

**GENERALISED PRISM GRAPH**

**2.1 Definition and Properties**

Generalised prism graph *Z _{n,s}*n has vertex set (i,j)|i=1,2 and j=1,2,......,n. Each vertex (i,j) is adjacent to (i,n-±1). In addition, each (1,j) is adjacent to (1,j+σ) for each σ in {|s-1/2|,.....,0,......,|s/2|}. The two n-cycle subgraphs of

*Z*induced by all the vertices of the form (1,j) and (2,j) are called the principal cycles. Prism graph

_{n,s}*Z*,1 is the cartesian product of cycle of length

_{n}*n*and a path of length 1, (i.e.),

*Z*=Cn ≥;*n ƒ1. Prism graphs can be considered as a mesh around a cylinder.

_{n,1}**Figure 2.1.1: Generalised Prism Graphs Z_{5,1},Z_{5,2},Z_{5,3}.**

The following inferences are made from the construction of generalised prism graph *Z _{n}*,n.

**Proposition 2.1.1.** The generalised prism graph *Z _{n,s}* is an s+2 - regular graph with

_{2n}vertices and n(s+2) edges.

**Theorem 2.1.1.** Prism graph *Z _{n,1}* is hamiltonian for all n.

**Proof.** The hamiltonian cycle c_{2n} is constructed as follows:

**Figure 2.1.2: Hamilton cycle of Z_{n,1}**

Step 1: Consider the Prism graph *Z _{n,1}*

Step 2: Without loss of generality, let c

_{21}be the origin of the hamilton cycle c

_{2n}n

Step 3: Continue the cycle through all the vertices in c

_{n}2 until the vertex c

_{2n}is reached

Step 4: From c

_{2n}trace the edge to c

_{1n}and then through all the vertices in c

_{n}1 until c

_{11}is reached

Step 5: From n11 move to c

_{21}.

Step 6: Hence, the hamilton cycle is as follows:

c

_{21},nc

_{22},....,nc

_{2n},nc

_{1n},nc

^{1(n-1)},....,nc

_{11},nc

_{21}

**Theorem 2.1.2.** The generalised prism graph *Z _{n,s}* is hamiltonian for all n.

**Proof:** *Z _{n,1/sub>}* is a spanning sub-graph of

*Z*for all s>1. Hence,

_{n,s}*Z*,

_{n}*s*is hamiltonian for all n.

**2.2 Literature Survey**

Generalised prism graph is a regular graph constructed on the basis of two*n*ordered cycles. Radio labelling which has wide applications in radio broadcasting has been investigated for generalised prism graph in^{10}.

**2.3 Toughness of Generalised Prism Graph**

**Result 2.3.1.** Prism graph *Z _{n,1}* is atleast 1 - tough by theorem 1.1. When

*n*is even,

*Z*is exactly 1 - tough and it is never 1- tough when

_{n,1}*n*is odd. Nevertheless, it is always greater than 1.

**Theorem 2.3.1.** The toughness of Generalised Prism Graph *Z _{n,s}*,S≥1,n≥3 is given by 2≤t(

*Z*,n)≤s+2/2 for all n.

_{n}**Proof.** As *Z _{n}*,

*s*is

*s*+ 2 - regular, it is necessary to say that

*Z*,

_{n}*s*is

*s*+ 2 - connected. On removing

*s*+ 2 vertices,

*Z*,

_{n}*s*is disconnected into 2 components - a singleton graph and a large component with 2n + s +3 vertices. Therefore,

*Z*,

_{n}*s*is atmosts+2/2 - tough.

**Figure 2.3.1: Cut-set and components for toughness of Z _{6,3},n**

**Remark 2.3.2.** The upper bound and lower bound for toughness of generalised prism graph *Z _{n,2}* are trivially equal to 2. As

*s*increases with respect to n, the toughness of

*Z*,

_{n}*s*also increases and is at most s+2/2 .

Our investigation on generalised prism graphs revealed that regularity has a direct impact on toughness. Hence, we focus on a non - regular graph, namely, cyclic split graph and investigate it's toughness.

**CYCLIC SPLIT GRAPH**

**3.1 Definition and Properties**

Cyclic split graphC_{n}K_{r}*k* has a complete graph Kr each of whose vertices is adjacent to vertices of*k* cycles, each of order n, Cn. Hence,C_{n}K_{r}*k* comprises of 1 complete graph of order n and*k*n cycles of order n. The lines joining the complete graph and cycles are called spokes, the removal of which results in a disjoint union of the complete graph and*k*n number of cycles Cn.

**Figure 3.1.1: Cyclic Split Graph C _{3}K_{3}^{2}.**

Cyclic split graph is a 1 - connected graph. The efficiency of this graph is to play the role of an interconnection network that transmits and receives data which can be studied using its toughness. Moreover, cyclic split graph is a non - regular and a non - hamiltonian graph. Hence, properties of the vertices in the cycles varies from those of the complete graph which in turn impacts the toughness of this graph.

**3.2 Literature Survey**

Cyclic split graph is a well-defined architecture. An application to network discovery such as local metric dimension was studied for cyclic split graph in6. Cordial labelling and antimagic labelling for graphs, which has a range of applications in coding theory, was studied for this graph in7 and9 respectively. Path packing of certain classes of cyclic split graphs was studied in8, which shows the strong construction of this graph.

**3.3 Toughness of Cyclic Split Graph**

**Theorem 3.3.1.** Cyclic split graphC_{n}K_{r}*k*,*k*≥1 is atleast 1/*k*+1 - tough, where n≥3,n≥2.
Proof. Consider a vertex £v_{i} of the complete graph k_{r}n, the removal of which disconnects the graph into*k*+1 components. The value of toughness corresponding to this cut-set and the obtained number of components is 1/*k*+1. Considering 1/*k*+1, the only possible way to minimise the toughness beneath 1/*k*+1 is by increasing the components by removing more vertices of the complete graph, which in turn enlarges the cut-set, thereby increasing the ratio for the graph's toughness. Moreover, this cut-set comprising of exactly one vertiex of k_{r} can minimise this graph's toughness even without distorting its major clique pertaining to*k*+1 components.

**Figure 3.3.1: Cut-set and components for toughness ofC4K41**

**Result 3.3.1.** The toughness of cyclic split graph C_{n}K^{k}_{r},n≥3,n≥2,*k*&lge;1 does not depend on n, the length of the cycle Cn as the cardinality of the cut-set simultaneously increase with the number of components while trying to distort them. Moreover, a cut-set consisting of only the vertices of the cycles is not preferable for attaining the minimum toughness because each of them are adjoined to a vertex of the complete graph which is a major clique in this graph.

**Result 3.3.2.**The toughness of cyclic split graph portrays that this graph is a weak graph as*k*+1 components are obtained from removing just 1 vertex. But the fact is that these*k*+1 components consists of*k* disjoint cycles of order*n*and one large componentC_{n}K_{r}^{k}-1*k*.

**CONCLUSION**

In this paper, we have investigated the bound for toughness of a regular graph, generalised prism graph *Z _{n}*,

*s*and a non-regular graph, cyclic split graph. Furthur, we intend to study the toughness of hypercube related interconnection network networks.

**REFERENCES**

- 1. D. Bauer, S. L. Hakima, E. Schmeichel, "Recognising tough graphs is NP - hard",
*Discrete Applied Mathematics*, 28, pp 191-195 (1990). - V. Chvaital, "Tough graphs and hamiltonian circuits",
*Discrete Mathematics*, 306, pp 910 - 917 (2006). - Dieter Kratsch, Jeno Lehel, Haiko Mfiller, "Toughness, hamiltonicity and split graphs",
*Discrete Mathematics*, 150, pp 231-245 (1996). - Douglas Bauer, Hajo Broersma, Edward Schmeichel, "Toughness in graphs - a survey",
*Graphs and Combinatorics*, 22, pp 1-35 (2006). - Joseph A. Gallian, "A Dynamic Survey of Graph Labeling",
*The Electronic Journal of Combinatorics*, 18, (2015). - Jude Annie Cynthia, Ramya, "The Local Metric Dimension of Cyclic Split Graph",
*Annals of Pure and Applied Mathematics*, Vol. 8, No. 2, pp 201-205 (2014). - Jude Annie Cynthia, Ramya, Kavitha, "On Cordial Labelling of Cyclic Split Graph",
*International Journal of Pure and Applied Mathematics*, Vol. 101, No. 6, pp 1063-1071 (2015). - Jude Annie Cynthia, Sindiya Therese, "Path Packing of Certain Class of Cyclic Split Graphs",
*Proceedings of International Conference on Applicable Mathematics*, pp 70 (2016). - Jude Annie Cynthia, Sravya, "Antimagic Labeling of Cyclic Split Graphs",
*Proceedings of International Conference on Applicable Mathematics*, pp 70 (2016). - Paul Martinez, Juan Ortiz, Maggy Tomova, Cindy Wyels, "Radio Numbers of Generalised Prism Graphs",
*Discussiones Mathematicea, Graph Theory*, 31, pp 45-62 (2011).