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 - tough2 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 Zns,n,n ≥1,1 ;≤n ≥ and cyclic split graph denoted asCnKrk,n≥3,n≥3,k≥1.

GENERALISED PRISM GRAPH

2.1 Definition and Properties

Generalised prism graph Zn,sn 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 Zn,s induced by all the vertices of the form (1,j) and (2,j) are called the principal cycles. Prism graph Zn,1 is the cartesian product of cycle of lengthnand a path of length 1, (i.e.), Zn,1 =Cn ≥;*n ƒ1. Prism graphs can be considered as a mesh around a cylinder.

Figure 2.1.1: Generalised Prism Graphs Z5,1,Z5,2,Z5,3.

The following inferences are made from the construction of generalised prism graph Zn,n.

Proposition 2.1.1. The generalised prism graph Zn,s is an s+2 - regular graph with 2n vertices and n(s+2) edges.

Theorem 2.1.1. Prism graph Zn,1 is hamiltonian for all n.

Proof. The hamiltonian cycle c2n is constructed as follows:

Figure 2.1.2: Hamilton cycle of Zn,1

Step 1: Consider the Prism graph Zn,1
Step 2: Without loss of generality, let c21 be the origin of the hamilton cycle c2nn
Step 3: Continue the cycle through all the vertices in cn2 until the vertex c2n is reached
Step 4: From c2n trace the edge to c1n and then through all the vertices in cn1 until c11 is reached
Step 5: From n11 move to c21.
Step 6: Hence, the hamilton cycle is as follows:
c21,nc22,....,nc2n,nc1n,nc1(n-1),....,nc11,nc21

Theorem 2.1.2. The generalised prism graph Zn,s is hamiltonian for all n.

Proof: Zn,1/sub> is a spanning sub-graph of Zn,s for all s>1. Hence, Zn,sis hamiltonian for all n.

2.2 Literature Survey

Generalised prism graph is a regular graph constructed on the basis of twonordered cycles. Radio labelling which has wide applications in radio broadcasting has been investigated for generalised prism graph in10.

2.3 Toughness of Generalised Prism Graph

Result 2.3.1. Prism graph Zn,1 is atleast 1 - tough by theorem 1.1. Whennis even, Zn,1 is exactly 1 - tough and it is never 1- tough whennis odd. Nevertheless, it is always greater than 1.

Theorem 2.3.1. The toughness of Generalised Prism Graph Zn,s,S≥1,n≥3 is given by 2≤t(Zn,n)≤s+2/2 for all n.

Proof. As Zn,sis s+ 2 - regular, it is necessary to say that Zn,sis s+ 2 - connected. On removing s+ 2 vertices, Zn,sis disconnected into 2 components - a singleton graph and a large component with 2n + s +3 vertices. Therefore, Zn,sis atmosts+2/2 - tough.

Figure 2.3.1: Cut-set and components for toughness of Z6,3,n

Remark 2.3.2. The upper bound and lower bound for toughness of generalised prism graph Zn,2 are trivially equal to 2. As sincreases with respect to n, the toughness of Zn,salso 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 graphCnKrk has a complete graph Kr each of whose vertices is adjacent to vertices ofk cycles, each of order n, Cn. Hence,CnKrk comprises of 1 complete graph of order n andkn 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 andkn number of cycles Cn.

Figure 3.1.1: Cyclic Split Graph C3K32.

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 graphCnKrk,k≥1 is atleast 1/k+1 - tough, where n≥3,n≥2. Proof. Consider a vertex £vi of the complete graph krn, the removal of which disconnects the graph intok+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 kr can minimise this graph's toughness even without distorting its major clique pertaining tok+1 components.

Figure 3.3.1: Cut-set and components for toughness ofC4K41

Result 3.3.1. The toughness of cyclic split graph CnKkr,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 ask+1 components are obtained from removing just 1 vertex. But the fact is that thesek+1 components consists ofk disjoint cycles of ordernand one large componentCnKrk-1k.

CONCLUSION

In this paper, we have investigated the bound for toughness of a regular graph, generalised prism graph Zn,sand a non-regular graph, cyclic split graph. Furthur, we intend to study the toughness of hypercube related interconnection network networks.

REFERENCES

  1. 1. D. Bauer, S. L. Hakima, E. Schmeichel, "Recognising tough graphs is NP - hard", Discrete Applied Mathematics, 28, pp 191-195 (1990).
  2. V. Chvaital, "Tough graphs and hamiltonian circuits", Discrete Mathematics, 306, pp 910 - 917 (2006).
  3. Dieter Kratsch, Jeno Lehel, Haiko Mfiller, "Toughness, hamiltonicity and split graphs", Discrete Mathematics, 150, pp 231-245 (1996).
  4. Douglas Bauer, Hajo Broersma, Edward Schmeichel, "Toughness in graphs - a survey", Graphs and Combinatorics, 22, pp 1-35 (2006).
  5. Joseph A. Gallian, "A Dynamic Survey of Graph Labeling", The Electronic Journal of Combinatorics, 18, (2015).
  6. 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).
  7. 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).
  8. Jude Annie Cynthia, Sindiya Therese, "Path Packing of Certain Class of Cyclic Split Graphs", Proceedings of International Conference on Applicable Mathematics, pp 70 (2016).
  9. Jude Annie Cynthia, Sravya, "Antimagic Labeling of Cyclic Split Graphs", Proceedings of International Conference on Applicable Mathematics, pp 70 (2016).
  10. Paul Martinez, Juan Ortiz, Maggy Tomova, Cindy Wyels, "Radio Numbers of Generalised Prism Graphs", Discussiones Mathematicea, Graph Theory, 31, pp 45-62 (2011).
map1 map2 map3