Connectivity of the Generalised Mycielskian of Digraphs

详细信息    查看全文

• 作者：S. Francis Raj (1) (2)
  
• 关键词：Mycielskian ; Generalised Vertex ; connectivity ; Arc ; connectivity ; Digraph ; 05C40
• 刊名：Graphs and Combinatorics
• 出版年：2013
• 出版时间：July 2013
• 年：2013
• 卷：29
• 期：4
• 页码：893-900
• 全文大小：142KB
• 参考文献：1. Balakrishanan R., Francis Raj S.: Connectivity of the Mycielskian of a graph. Discret. Math. 308, 2607-610 (2007) CrossRef
  2. Balakrishnan R., Ranganathan K.: A Textbook of Graph Theory. Springer, New York (2000) CrossRef
  3. Caramia M., Dell’Olmo P.: A lower bound on the chromatic number of Mycielski graphs. Discret. Math 235, 79-6 (2001) CrossRef
  4. Chang G.J., Huang L., Zhu X.: Circular chromatic number of Mycielski's graphs. Discret. Math 205, 23-7 (1999) CrossRef
  5. Cropper M., Gyárfás A., Lehel J.: Hall ratio of theMycielski graphs. Discret. Math. 306, 1988-990 (2006) CrossRef
  6. Fisher D.C., McKena P.A., Boyer E.D.: Hamiltonicity, diameter, domination, packing and biclique partitions of the Mycielski’s graphs. Discret. Appl. Math. 84, 93-05 (1998) CrossRef
  7. Guo L., Guo X.: Connectivity of the Mycielskian of a digraph. Appl. Math. Lett 22, 1622-625 (2009) CrossRef
  8. Lam, P.C.B.,Gu, G., Lin,W., Song, Z.: Some properties of generalized Mycielski’s graphs (manuscript)
  9. Lam P.C.B., Gu G., Lin W., Song Z.: Circular chromatic number and a generalization of the construction of Mycielski. J. Combin. Theory Ser. B 89, 195-05 (2003) CrossRef
  10. Larsen M., Propp , J. , Ullman D.: The fractional chromatic number of Mycielski’s graphs. J. Graph Theory 19, 411-16 (1995) CrossRef
  11. Lin W., Wu J., Lam P.C.B., Gu G.: Several parameters of generalised Mycielskians. Discret. Appl. Math. 154, 1173-182 (2006) CrossRef
  12. Mycielski J.: Sur le colouriage des graphes. Colloq. Math 3, 161-62 (1955)
  
• 作者单位：S. Francis Raj (1) (2)
  
  1. Department of Mathematics, Bharathidasan University, Tiruchirappalli, 620024, India
  2. Department of Mathematics, Pondicherry University, Puducherry, 605014, India
  
• ISSN：1435-5914

文摘

In a search for triangle-free graphs with arbitrarily large chromatic number, Mycielski developed a graph transformation that transforms a graph G into a new graph?μ(G), which is called the Mycielskian of G. A generalisation of this transformation is the generalised Mycielskian?μ m (G), m a positive integer. This paper investigates the vertex-connectivity κ and arc-connectivity κ-of the generalised Mycielskian of strongly connected digraphs D. We show that κ (μ m (D)) = min{δ(μ m (D)), (m?+?1)κ (D) + 1} and κ-(μ m (D)) = δ(μ m (D)) where δ(μ m (D)) denotes the minimum degree of the generalised Mycielisian?μ m (D). This turns out to be a generalisation of the results due to Guo and Guo (Appl. Math. Lett. 22:1622-625, 2009).