| We use a graph G represent a model of communication network. When designingcommunication networks, the stability of them must be considered in order to avoid orminimize the loss caused by communication disruptions. Therefore, the designer shouldconsider the vulnerability of networks. Some vulnerability parameters such as connectivityand edge-connectivity give the minimum cost to destroy the network, but they do not takeinto account what remains after destruction. Recently, some new parameters have beenintroduced and studied such as toughness, integrity, edge-integrity, scattering numberand tenacity. Usually, for most of the above mentioned parameters, the correspondingcomputing problems is NP-hard. Therefore, giving the formula or algorithm to computingthese parameters for some special classes of graphs is very interesting and useful.In this paper, we discuss tenacity and rupture degree for the Mycielskian of a graph.Tenacity T (G) and rupture degree r(G) were presented by Cozzens and Li et.al[16,17].[17]The tenacity T (G) of an incomplete connected graph G is defined byand the tenacity of Knis defined as n.[16] The rupture degree of an incomplete connectedgraph G is defined byand the rupture degree of Knis defined as1n. Where ω(G S) and τ (G S) denote thenumber of components and the order of a largest component in G S, respectively.[25] Fora graph G=(V, E), the Mycielskian of G is the graph μ(G) with vertex set V∪V′∪{u},where V′={x′: x∈V} and edge set E∪{xy′: xy∈E}∪{y′u: y′∈V′}. The vertexx′is called the twin of the vertex x (and x is the twin of x′) and the vertex u is calledthe root of μ(G). For n≥2, μn(G) is defined iteratively by setting μn(G)=μ(μn1(G)).In this paper, we give several bounds for tenacity and rupture degree of the Mycielskian of a graph and compute tenacity and rupture degree for the Mycielskian of some specialclasses of graphs. |
